算法过程

什么是桶排序呢？听起来挺不好懂的，但是实际上，我们生活中就会用到。

桶自然是装东西的东西，我们生活中都会洗衣服，洗衣服也是有顺序的，先洗什么（媳妇儿的），后洗什么（自己的），这个过程实际上就是桶排序的过程！这个就相当有我们拿到所有要洗的衣服，将衣服中先洗的放入桶【1】，后洗的放入桶【2】。这样我们就完成了 “排序” ，接下来洗衣服，我们就先把桶【1】的衣服放入洗衣机，洗完了，再放桶【2】。

桶排序就是这样的过程，比如我们在学校，班级里面考试，满分是5分，所有同学来考试，分数只能是整数的分数，同学们的考试成绩分别为：

考试成绩.png

我们想要给这些同学根据他们的考试成绩来在班内排名。此时，因为考试成绩是 0~5 所以我们找出 6 个 “桶” 来装这些成绩：

分数桶.png
然后我们对号入座，把相应的成绩的同学放入相应的桶里，此时桶内的元素分别为：

入桶后的元素.png

我们依次从0~5的桶内取出各个成绩的同学，这样我们就得到了全部同学按照成绩的排名：

依次取出桶内元素之后.png

发散
这就是简单的桶排序。如果班里考试成绩是0 ~ 100分呢？我们可以使用10个桶，0 ~ 10、11 ~ 20……。这样的话，我们把成绩装到相应空间的桶里，每个桶里的元素都是不相同的，可能每个桶里的元素就是无序的了，此时我们可以通过前面的算法，对每个桶里进行快速排序，这样达到的结果是，我们缩小了之前的问题规模，把全班同学的成绩通过桶分成了10份，分别对每一小份进行排序，然后再依次取出桶中的成绩，这也是一种大事化小的思想！

算法实现

如果要实现发散版本的桶排序，只需每个桶所装的数据是一个区间，然后每个桶内做一次快速排序或者其他排序，让每个桶有序。

#coding:utf-8

import numpy as np

# 桶排序，这里我们约定一共有6个桶 0~5 ，来表示分数
def bucket_sort(datas):
    # 简单粗暴，6个桶
    buckets = [[], [], [], [], [], []]

    # 放入桶中
    for data in datas:
        # 因为这里分数是0~5，桶的序号跟分数一样，简单粗暴
        buckets[data].append(data)
    
    # 拿出所有数据
    sorted_data = []
    for bucket in buckets:
        sorted_data.extend(bucket)
    
    return sorted_data


datas = list(np.random.randint(0, 6, 20))
print("排序之前的数据：{}".format(datas))
sorted_datas = bucket_sort(datas)
print("排序之后的数据：{}".format(sorted_datas))

结果是: