基数排序（桶式排序）--桶的真正作用是什么？

一.前言

??在以往我们学习的排序方法中都是基于比较来进行排序，其效率要么是二次方，要么是对数级。而桶排序是基于容器的排序，主要分为：计数排序和基数排序。本文讲述基数排序的知识。
??基数排序的思想分为两个部分：分配与收集。

二.分配与收集图解分析

分配思想：
??采用最高位优先或者最低位优先（个、十、百、千、万……），根据某个关键字值遍历数组将数据分到对应的桶中。
??此处将数据分配到0~9十个桶中，因为任何一个数据的某一位的范围都是在0 ~9这个范围。
收集思想：
??将分配到桶中的值依次放回到数组中。要按照先进桶的先出（先进先出)。

分配与收集图解：
??现有如下一组数据，采用基数排序对其进行升序排序：

第一次分配与收集：

??此时数据的个位就是从小到大进行排序。

第二次分配与收集：

??现在数据的十位就是从小到大进行排序。

第三次分配与收集：

??同样数据的百位就是从小到大进行排序。
第四次分配与收集：

??当按千位的分配与收集完成后，数据将会变得有序，排序也就完成。

三.基数排序算法的难点

??对于基数排序的思想大家都很容易理解。但是代码的实现并不是像我们所描述的一样将数据真正的放到桶中。而是借助桶的思想通过先统计各个桶中将会存放几个数据，再对桶中的数据个数实现累加。通过最后累加的结果，得出原数组中的数据将会拷贝到辅助数组的何位置，从而完成收集。
??也就是说桶的真正作用是计算位置，不是用于存放数据。
??所以我们的桶将会是一个容量为10的一个一维数组，初始化为零。通过一系列的计算，得出原数组数据将会拷贝到辅助数组的何处。

四.基数排序算法设计

??结合上述的分析，给出算法中的一次分配过程，应该是如下的状态

??我们借助桶中的记录，将原数组中的数据拷贝到辅助数组。那是如何计算位置的？按降序遍历数组下标，根据数据检索桶的编号，桶中的记录个数减1即为该数据在辅助数组中的位置。当收集好一个数据后该桶中的记录个数要减一。
??比如上述例子中，先遍历原数组下标为6的位置，该位置数据为79，按个位其对应的桶编号是9号桶，9号桶中的记录为7，那么该数据在辅助数组中的位置就是7-1=6号位置。当我们确定了一个数据的位置后，需要将该桶中的记录减1。所以9号桶中的记录变为6。依次数组下标为5……

??分配次数是由什么决定的？ 分配次数是由该组数据中数据最大的数来决定的。

基数排序的算法应该包含这几个部分：
?· 计算这组数据中的最大值，来确定分配次数；
?· 计算各个桶中所存放的数据个数；
?· 将桶中的数据更新为累计个数；
?· 根据桶中的记录来确定数据将会收集到辅助数组中的哪一个位置；
?· 将辅助数组中的数据拷贝回原数组。

五.基数排序算法实现

??基于以上的分析，我们来实现基数排序的算法。

void radixSort(int array[], int size)
{
    int max = array[0];//用于标记这组数据的最大值int base = 1;//标记除数int* tempAry = (int*)malloc(sizeof(int) * size);//辅助数组，用于临时存储数据if (!tempAry)exit(-1);//开辟空间失败，返回-1for (int i = 1; i < size; i++)//遍历找出这组数据的最大值{
    if (array[i] > max){
    max = array[i];}}while (max / base > 0)//进行分配与收集，分配次数由最大的数据来决定{
    int bucket[10] = {
     0 };//申请10个桶初始化为零，用于记录个数int number;//用于标记桶的号码int pos;//用于标记辅助数组的位置for (int i = 0; i < size; i++)//统计各个桶中的数据个数{
    number = array[i] / base % 10;//计算出桶的编号bucket[number]++;//该桶中的数据个数增加一个}for (int i = 1; i < 10; i++)//累加更新桶中的记录{
    bucket[i] += bucket[i - 1];}for (int i = size - 1; i >= 0;i--)//逆序将数据拷贝到辅助数组{
    number = array[i] / base % 10;//计算桶的编号pos = bucket[number] - 1;//计算需要拷贝到辅助数组的什么位置tempAry[pos] = array[i];//进行拷贝bucket[number]--;//记录个数减一}for (int i = 0; i < size; i++)//将数据拷贝会原数组{
    array[i] = tempAry[i];}base *= 10;//每分配和收集一次，除数扩大10倍}free(tempAry);//释放临时数组
}

测试主函数：

int main()
{
    int array[]{
     234,453,454,234,656,6,567,65,9,34,4,45,2,5,0,1 };int size = sizeof(array) / sizeof(int);radixSort(array, size);for (int i = 0; i < size; i++){
    std::cout << " " << array[i];}std::cout << char(10);system("pause");return 0;
}

测试结果：

六.总结

??基数排序时间复杂度是O(N)，空间复杂度O(N)，是一种稳定的排序。但是其应用范围有限，需要样本的数据状况满足桶的划分。
??本次分享到这里，希望对大家有所帮助。

??我是老胡，感谢阅读！！ ?? ??