本文主要是介绍内部排序之五：计数排序、基数排序和桶排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
最后三种排序算法了，由于都不是基于比较的排序，因此这三种排序算法可以以线性时间运行。但是因为限制条件的特殊性，因此应用面没有基于元素比较的排序算法广，但是在很多特定的情况下还是蛮有用途的，而且效率极高。
计数排序
计数排序是建立在这样的前提条件下的：假设n个输入元素的每一个都是0到k区间内的一个整数，其中k为某个整数。因此我们后面所写的程序也只是针对0到k之间的元素进行排序，换句话说，排序元素中不能有负数。
计数排序的基本思想是：对一个输入元素x，先确定所有输入元素中小于x的元素个数，那么排序后x所在的位置也就明确了。比如，所有的输入元素中有10个元素小于x，那么排好序后x的位置序号就应该是11。当然，如果有相同元素，自然要放到相邻的位置上。
算法导论上给出了计数排序的很详细的伪代码，我们根据此伪代码，并设数组arr为输入数组，arr中的每个元素值在0到k之间，brr为排序后的输出数组，crr记录arr中每个元素出现的次数。写出代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | /* 第一种形式实现计数排序 计数排序后的顺序为从小到大 arr[0...len-1]为待排数组，每个元素均是0-k中的一个值 brr[0...len-1]为排序后的输出数组 crr[0...k]保存0...k中每个值在数组arr中出现的次数 */ void Count_Sort( int *arr, int *brr, int *crr, int len, int k) { int i,j=0; //数组crr各元素置0 for (i=0;i<=k;i++) crr[i] = 0; //统计数组arr中每个元素重复出现的个数 for (i=0;i<len;i++) crr[arr[i]]++; //求数组arr中小于等于i的元素个数 for (i=1;i<=k;i++) crr[i] += crr[i-1]; //把arr中的元素放在brr中对应的位置上 for (i=len-1;i>=0;i--) { brr[crr[arr[i]]-1] = arr[i]; //如果有相同的元素，则放在下一个位置上 crr[arr[i]]--; } } |
很明显上面代码的时间复杂度为O（n+k），但用到了brr来保存排序结果，我们可以它做些改进，使排序原地进行，如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /* 第二种形式实现计数排序 计数排序后的顺序为从小到大 arr[0...len-1]为待排数组，每个元素均是0-k中的一个值 crr[0...k]保存0...k中每个值在数组arr中出现的次数 */ void Count_Sort( int *arr, int *crr, int len, int k) { int i,j=0; //数组crr各元素置0 for (i=0;i<=k;i++) crr[i] = 0; //统计数组arr中每个元素重复出现的个数 for (i=0;i<len;i++) crr[arr[i]]++; //根据crr[i]的大小，将元素i放入arr适当的位置 for (i=0;i<=k;i++) while ((crr[i]--)>0) { arr[j++] = i; } } |
采用如下代码测试：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | int main() { int i; //待排序数组，每个元素均在0-8之间 int arr[] = {2,1,3,8,6,0}; int brr[6]; int crr[9]; Count_Sort(arr,brr,crr,6,8); printf ( "计数排序后的结果为：" ); for (i=0;i<6;i++) printf ( "%d " ,brr[i]); printf ( "n" ); return 0; } |
测试结果如下：
最后我们稍微总结下计数排序的特点：
1、不是基于比较的排序，因此可以达到线性排序时间；
2、采取空间换时间的思想，需要brr和crr等辅助空间，但是时间复杂度仅为O（n+k）；
3、稳定性好，这也是计数排序最重要的一个特性。
在实际工作中，当k=O（n）时，我们一般才会采取计数排序，如果k很大，则不宜采取该算法，尤其在如下情形下：
待排序元素为：1、3、8、5、10000000，这样会造成很大的资源浪费。
基数排序
基数排序的排序时间也可以达到线性，尤其在k和d（后面介绍该参数）很小的情况下。
基数排序采取的是多关键字比较的策略，且每个关键字对排序的影响不同，根据关键字影响的主次，有两种排序方法：
1、先根据影响最大的关键字来排序，而后在该关键字相同的情况下，再根据影响次之的关键字来排序，依此类推，直到最后按照影响最小的关键字排序后，序列有序。我们称这个为先高位后低位。
2、先根据影响最小的关键字来排序，而后再对全部的元素根据影响次小的关键字来排序，依此类推，直到最后按照影响最大的关键字排序后，序列有序。我们称这个为先低位后高位。
这有点抽象，我们用具体的例子来说明。比如，我们希望用三个关键字（年、月、日）来对日期进行排序，按照基数排序的思想，则：
采取第一种方法排序的思路是这样的：先比较年，形成一个按照年有序排列的序列，而后对年相等的日期，在比较月，对月相等的日期，再比较日，最后得到有序序列。
采取第二种方法排序的思路是这样的：先对所有元素按照日排序，再对所有元素按照月排序，最后对所有元素按照年排序，得到有序序列。
我们一般采用第二种方法来进行排序，比如如下的数字序列：
217，125，362，136，733，522
先对个位上的数字进行排序，得到：
362，522，733，125，136，217
再对十位上的数字进行排序，得到：
217，522，125，733，136，362
最后对百位上的数字进行排序，得到：
125，136，217，362，522，733
很明显，高位数字比低位数字对排序的影响大，该方法的正确性很容易证明，这里不再说明。
我们注意到，这里每一步都需要对各个位上的数进行排序。而为了保证基数排序的正确性（稳定性），我们对每个位上的数进行排序时可以选用计数排序。算法导论上给的伪代码太粗略了，直接贴出自己写的完全代码（包括测试代码），如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | /******************************* 基数排序 Author:兰亭风雨 Date:2014-03-03 Email:zyb_maodun@163.com ********************************/ #include<stdio.h> #include<stdlib.h> /* 在第一种计数排序的实现形式上做了些修改 计数排序后的顺序为从小到大 arr[0...len-1]为待排数组，我们这里采用三位数 brr[0...len-1]为排序后的有序数组 w[0...len-1]用来保存取出的每一位上的数，其每个元素均是0-k中的一个值 crr[0...k]保存0...k中每个值出现的次数 */ void Count_Sort( int *arr, int *brr, int *w, int *crr, int len, int k) { int i; //数组crr各元素置0 for (i=0;i<=k;i++) crr[i] = 0; //统计数组w中每个元素重复出现的个数 for (i=0;i<len;i++) crr[w[i]]++; //求数组w中小于等于i的元素个数 for (i=1;i<=k;i++) crr[i] += crr[i-1]; //把arr中的元素放在brr中对应的位置上 for (i=len-1;i>=0;i--) { brr[crr[w[i]]-1] = arr[i]; //如果有相同的元素，则放在下一个位置上 crr[w[i]]--; } //再将brr中的元素复制给arr，这样arr就有序了 for (i=0;i<len;i++) { arr[i] = brr[i]; } } /* 基数排序后的顺序为从小到大 其中参数d为元素的位数 */ void Basic_Sort( int *arr, int *brr, int *w, int *crr, int len, int k, int d) { int i,j,val=1; //从低位到高位依次进行计数排序 for (i=1;i<=d;i++) { //w中保存的是arr中每个元素对应位上的数 //范围在0-k之间 for (j=0;j<len;j++) w[j] = (arr[j]/val)%10; //对当前位进行计数排序 Count_Sort(arr,brr,w,crr,len,k); val *= 10; } } int main() { int i; //待排序数组，每个元素的每一位均在0-7之间 int arr[] = {217,125,362,136,733,522}; int brr[6]; //用来保存每次计数排序后的结果 int w[6]; //每次循环时，保存该位上的数 int crr[8]; //每次循环时，保存该位上的数出现的次数 Basic_Sort(arr,brr,w,crr,6,7,3); printf ( "计数排序后的结果为：" ); for (i=0;i<6;i++) printf ( "%d " ,arr[i]); printf ( "n" ); return 0; } |
测试结果如下：
最后我们同样对基数排序稍微做下总结：
1、同样不是基于比较的排序，因此可以达到线性排序时间；
2、同样采取空间换时间的思想，需要额外的辅助空间，但是时间复杂度仅为O（d(n+k)）；
3、基数排序的稳定性同样也很好。
吐槽一下：写Basic_Sort的时候，每一次的val应该是10的i-1次方，手误，打成了10*（i-1）， 跟踪调试了一下午，每次循环w数组中的值都是个位数，就在那几行代码找问题，但尼玛我偏偏就是没看出来。
桶排序
桶排序假设输入数据服从均匀分布，平均情况下它的时间复杂度为O（n）。与计数排序类似，因为对输入数据作了某种假设，桶排序的速度也很快。
桶排序将输入元素按照一定的区间划分为若干个桶，因为假设了输入的数据在总的区间范围内是均匀分布的，因此一般不会出现很多个元素落在同一个桶中的情况。我们可以先对每个桶中的元素排序，而后按照桶的序号，依次把各个桶中的元素列出来即可。
在进行桶排序时，我们需要一个辅助数组来存放每个桶，而每个桶中的元素最好用链表串起来，这样操作起来比较方便。一个很普遍的展示图例如下：
桶排序了解思想即可，代码我们就不再实现了，因为它的实现不具备普遍性，要根据不同的情况来划分不同个数的桶，以及桶所规定的区间。
2014校招时创新工厂下的涂鸦移动有一道这样的面试题：
一个字符数组，里面的字符可能是a-z、A-Z、0-9.现在要求对数组进行排序，要求所有小写字符放在最前面，所有大写字符放在中间，所有数字放在最后。而且各部分内部分别有序。
这个很明显用桶排序来实现效果最佳，尤其在数据量非常大的情况下。
再比如，如下情况也是用桶排序的最佳时机（摘自百度百科）
海量数据
一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，你把这500 万元素的数组排个序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。
这篇关于内部排序之五：计数排序、基数排序和桶排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
