问题提出：

将以下数据：

6, 8, 2, 3, 4, 0, 9, 1, 5，1

按从小到达排列。

---

桶排序原理：

桶排序也叫计数排序，简单来说，就是将数据集里面所有元素按顺序列举出来，然后统计元素出现的次数。最后按顺序输出数据集里面的元素。

排序过程如下：

一、初始化桶的大小

把数据集里面每一个元素当作一个桶，由上面问题看出，原始数据范围在0--9之间，因此我就需要有10个桶，如下图

第一行为初始化计数为0，第二行为各个元素。

二、计数

接下来读入第一原始数据为6,则在下标为6的桶中增加1,如下图：

再读入下一个原始数据为8,则在下标为8的桶中增加1,如下图： 

以此类推，最后遍历完所有原始数据时，10个桶的计数如下图：

三、输出数据

在完成原始数据的遍历计数后，接下来遍历各个桶，输出数据：

元素0计数为1,则输出0,

元素1计数为2,则输出1 1,

元素2计数为1,则输出2,

元素3计数为1,则输出3,

元素4计数为1,则输出4,

元素5计数为1,则输出5,

元素6计数为1,则输出6,

元素7计数为0,则不输出元素,

元素8计数为1,则输出8,

元素9计数为1,则输出9,

最后结果输出为：0, 1, 1, 2, 3, 4, 5, 6, 8, 9

---

 

代码实现

由上述原理可以看出，桶排序需要以下三个步骤：

1.申请一个包含所有元素的数组，并初始化。

2.遍历原始数据，并计数。

3.遍历计数完成后的各个数组元素，输出数据。

以下是python代码的实现：

1 #!/usr/bin/env python 2 #-*- coding:utf8 -*- 3  4 class BucketSort(object): 5     ''' 6     self.datas:       要排序的数据列表 7     self.bucketSize:  水桶的大小(数据集的范围，如bucketSize=10, 8                       则表示数据集的范围为0-9) 9     self.result:      保存排序后的结果10     self.bucket:      代表水桶，指数据集内的所有元素11     _sort():          排序函数12     show():           输出结果的函数13 14     用法：15     BucketSort(datas, size)   或者BucketSort(datas)，size的默认值为10016 17     BucketSort(datas)._sort() 这样就是开始排序18     BucketSort(datas).show()  这样就可以把排序后的结果输出19     '''20     def __init__(self, datas, size=100):21         self.datas = datas22         self.bucketSize = size23         self.result = [0 for i in range(len(datas))]24         self.bucket = [0 for i in range(self.bucketSize)]25 26     def _sort(self):27         # 读入各个元素，并在对应的位置统计，当bucket里的元素不为028         # 就保存到result里面29         for num in self.datas:30             self.bucket[num] += 131         j = 032         for i in range(self.bucketSize):33             while(self.bucket[i]):34                 self.result[j] = i35                 self.bucket[i] -= 136                 j += 137 38     def show(self):39         print "Resutl is:",40         for i in self.result:41             print i,42         print ''43 44 45 if __name__ == '__main__':46     try:47         size = raw_input("Please input size(default=100):")48         if size:49             size = int(size)50         datas = raw_input('Please input some number:')51         datas = datas.split()52         datas = [int(datas[i]) for i in range(len(datas))]53     except Exception:54         pass55     if size:56         bks = BucketSort(datas, size)57     else:58         bks = BucketSort(datas)59     bks._sort()60     bks.show()

---

总结：

1.桶排序的优点就是特别快，真的是特别快！特别快！特别块！

2.缺点就是特别耗资源，如果数据取值的范围是0---10¹⁰, 就要申请一个大小为10¹⁰的数组，想想这得多耗内存空间。阔怕！

3.我上面写的程序也只是一个演示性的，漏洞挺多，目前只能排序大于零的整数。

---

最后有兴趣的同学可以关注我的微信公众号，可以随时及时方便看我的文章。*^_^*

扫码关注或者搜索微信号：King_diary