問題
對n個0~1000的數(shù)進行排序。
解決問題的思想
可以用一個長度為1001的列表中的每一個位置表示一個桶，每個桶用來標記每個數(shù)出現(xiàn)的次數(shù)。最后從前往后遍歷每一個桶，每個桶標記的次數(shù)是多少，這個桶的下標就打印多少次，輸出結(jié)果即為升序排列。
Paste_Image.png
python代碼實現(xiàn)
#!/usr/bin/python
# encoding: utf-8
import random
# 簡單的桶排序算法
# 生成一百個0~1000的隨機數(shù)
source = [random.randint(0,1000) for i in range(0, 101)]
# 構(gòu)造空桶(長度為1001的列表，每個列表的值初始化為0)
bucket = [0 for i in range(0, 1001)]
# 進行計數(shù)，每出現(xiàn)一個數(shù)，對應的桶的值加一
for i in source:
bucket[i] += 1
# 從第一個桶遍歷到最后一個桶
for i in range(0, 1001, 1):
# 這個桶的值出現(xiàn)多少次，就打印多少次
for j in range(1, bucket[i] + 1):
print(i),
運行結(jié)果
0 7 12 18 19 31 49 52 63 64 68 74 90 93 98 114 114 119 131 133 138 140 160 162 166 193 201 205 238 254 257 266 277 285 287 306 307 310 322 362 368 373 374 396 415 424 430 439 442 463 463 465 467 481 494 508 529 545 553 569 571 572 593 602 608 619 624 644 645 645 662 663 669 674 680 683 686 691 714 765 766 778 784 786 797 802 813 835 840 841 842 887 888 897 905 929 930 943 945 973 975
時間復雜度
- 構(gòu)造空桶循環(huán)了m次（m為桶的個數(shù)），進行計數(shù)循環(huán)了n次（n為待排序數(shù)的個數(shù)），最后遍歷輸出循環(huán)了m+n次，所以總共執(zhí)行了2（m+n）次。所以時間復雜度為O(n)
桶排序的缺點：
- 如果排序樹的范圍在0~10000000,那就需要這么大的list作為空桶，可能排序數(shù)的長度只有幾十個，顯然用桶排序很消耗空間。
復雜的桶排序：可以考慮每個桶裝有不同的值，分配完桶后，對每個桶中的數(shù)據(jù)進行排序算法即可。
*參考資料：《啊哈！算法》 *
