简单的桶排序

问题

对n个0~1000的数进行排序。

解决问题的思想

可以用一个长度为1001的列表中的每一个位置表示一个桶，每个桶用来标记每个数出现的次数。最后从前往后遍历每一个桶，每个桶标记的次数是多少，这个桶的下标就打印多少次，输出结果即为升序排列。

Paste_Image.png

python代码实现

#!/usr/bin/python
# encoding: utf-8

import random

# 简单的桶排序算法

# 生成一百个0~1000的随机数
source = [random.randint(0,1000) for i in range(0, 101)]

# 构造空桶(长度为1001的列表，每个列表的值初始化为0)
bucket = [0 for i in range(0, 1001)]

# 进行计数，每出现一个数，对应的桶的值加一
for i in source:
    bucket[i] += 1

# 从第一个桶遍历到最后一个桶
for i in range(0, 1001, 1):
    # 这个桶的值出现多少次，就打印多少次
    for j in range(1, bucket[i] + 1):
        print(i),

运行结果

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

时间复杂度

• 构造空桶循环了m次（m为桶的个数），进行计数循环了n次（n为待排序数的个数），最后遍历输出循环了m+n次，所以总共执行了2（m+n）次。所以时间复杂度为O(n)

桶排序的缺点：

• 如果排序树的范围在0~10000000,那就需要这么大的list作为空桶，可能排序数的长度只有几十个，显然用桶排序很消耗空间。
  复杂的桶排序：可以考虑每个桶装有不同的值，分配完桶后，对每个桶中的数据进行排序算法即可。

*参考资料：《啊哈！算法》 *