<h4>需求</h4>
現(xiàn)在給我們5個(gè)數(shù)字. (0~10之間), 實(shí)現(xiàn)從大到小的排序. (5, 3, 5, 2, 8)
<h4>實(shí)現(xiàn)思路</h4>
現(xiàn)在假如我們有11個(gè)桶, 編號(hào)從0~10,每出現(xiàn)一個(gè)數(shù), 就在對(duì)應(yīng)編號(hào)的桶中放一個(gè)小旗子, 最后只要數(shù)數(shù)每個(gè)桶中有幾個(gè)小旗子就 OK 了. 例如2號(hào)桶中有1個(gè)小旗子, 表示 2 出現(xiàn)一次; 3號(hào)桶中有一個(gè)小旗子, 表示3出現(xiàn)了一次; 5 號(hào)桶中有 2 個(gè)小旗子, 表示 5 出現(xiàn)了兩次; 8 號(hào)桶中有 1 個(gè)小旗子, 表示8 出現(xiàn)了一次.
<h4>案例實(shí)踐</h4>
現(xiàn)在嘗試輸入 n 個(gè) 0 ~ 1000 之間的整數(shù), 將它們從大到小排序. 提醒一下,如果需要對(duì)數(shù)據(jù)范圍在 0 ~1000 之間的整數(shù)進(jìn)行排序, 我們需要 1001 個(gè)桶, 來表示 0 ~ 1000 之間每一個(gè)數(shù)出現(xiàn)的次數(shù), 這一點(diǎn)一定要注意.
代碼實(shí)現(xiàn)如下:
<b>//這里的getchar();用來暫停程序,以便查看程序輸出的內(nèi)容
//也可以用system("pause");等來代替</b>
可以輸入以下數(shù)據(jù)進(jìn)行驗(yàn)證:
運(yùn)行結(jié)果是:
<h4>最后</h4>
<b>最后來說下時(shí)間復(fù)雜度的問題, 代碼中第6行的循環(huán)一共循環(huán)了 m 次(m 為桶的個(gè)數(shù)), 第9行的代碼循環(huán)了 n 次(n 為待排序的數(shù)的個(gè)數(shù)), 第14行和15行一共循環(huán)了 m+n 次, 所以整個(gè)排序算法一共執(zhí)行了 m+n+m+n 次, 我們用大寫字母 O 來表示時(shí)間復(fù)雜度, 因此該算法的時(shí)間復(fù)雜度是 O(m+n+m+n) 即 O(2*(m+n)). 我們?cè)谡f時(shí)間復(fù)雜度的時(shí)候可以忽略較小的常數(shù), 最終桶排序的時(shí)間復(fù)雜度為 O(m+n), 還有一點(diǎn), 在表示時(shí)間復(fù)雜度的時(shí)候, n 和 m 通常為大寫字母即 O(M+N).</b>
這是一個(gè)非郴叮快的排序算法. 桶排序從1956年就開始被使用, 該算法的基本思想是由 E.J.Issac 和 R.C.Singleton 提出來的. 其實(shí)這不是真正的桶排序算法, 真正的桶排序算法要比這個(gè)更加復(fù)雜.
