桶排序的基本定义是什么？桶排序算法要求该怎么理解？

桶排序

举个栗子，我们的任务是将 40 个 100 以内的数字排序。我们可以这么做：

将0~~20以内的数字放入第一个桶内

将21~~40以内的数字放入第二个桶内

依次反复直到将这40个数字放入 5 个桶内

利用某种排序方法(本文用的快速排序)将桶内元素排序

从桶内按照顺序将数字取出依次放入一个原数组

经过以上操作，原数组是不是已经变得有序了呢?

我们可以将桶排序与快速排序对比，快速排序是将集合拆分为两个值域，这里称为两个桶，再分别对两个桶进行排序，最终完成排序。桶排序则是将集合拆分为多个桶，对每个桶进行排序，则完成排序过程。两者不同之处在于，快排是在集合本身上进行排序，属于原地排序方式，且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间，在额外空间上对桶进行排序，避免了构成桶过程的元素比较和交换操作，同时可以自主选择恰当的排序算法对桶进行排序。

桶排序算法要求

桶排序算法要求，数据的长度必须完全一样，程序过程要产生长度相同的数据，使用下面的方法：Data=rand()/10000+10000上面提到的，每次下一次的扫描顺序是按照上次扫描的结果来的，所以设计上提供相同的两个桶数据结构。前一个保存每一次扫描的结果供下次调用，另外一个临时拷贝前一次扫描的结果提供给前一个调用。

数据结构设计：链表可以采用很多种方式实现，通常的方法是动态申请内存建立结点，但是针对这个算法，桶里面的链表结果每次扫描后都不同，就有很多链表的分离和重建。如果使用动态分配内存，则由于指针的使用，安全性低。所以，笔者设计时使用了数组来模拟链表(当然牺牲了部分的空间，但是操作却是简单了很多，稳定性也大大提高了)。共十个桶，所以建立一个二维数组，行向量的下标0—9代表了10个桶，每个行形成的一维数组则是桶的空间。

平均情况下桶排序以线性时间运行。像基数排序一样，桶排序也对输入作了某种假设， 因而运行得很快。具 体来说，基数排序假设输入是由一个小范围内的整数构成，而桶排序则 假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。 桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列出来即可。