目录
1、前言
2、计数排序
3、基数排序
4、使用场景
1、前言
常见的排序算法有很多，例如归并排序、堆排序、快速排序还有插入排序等等，以上排序有一个共同点，队列中的元素需要通过比较来计算元素的位置，它们被统称为比较排序。
比较排序是有效率极值存在的。比较排序过程可以被抽象为决策树模型，决策树模型是一个二叉树。每个元素的位置根据二叉树最终决定自己的位置。
image.png
在最坏情况下，任何比较排序算法至少需要做N*lgN次比较
此定理的详细推导过程请参照算法导论。
比较排序算法是有效率极值存在的。本文中介绍的两种算法非比较排序算法，它们都需要满足一定的条件，它们的效率值均为N。
1、计数排序
如果一个数组中的最大值已知，且数组中最大值减去最小值的差不大的话，则可以使用计数排序。计数排序，顾名思义，统计数组中每个元素出现的次数，然后计算出小于或等于p的元素个数q，那么p在数组中的位置应该是q-1（数组从0开始，所以要减1）。
计数排序需要使用额外的内存空间，一个待排序数组的等长数组，一个计数数组。
/**
* @param arrayA 待排序数组
* @param arrayB 返回的正确排序的数组
* @param k 数组A中的元素最大值
*/
public static int[] countSort(int[] arrayA, int[] arrayB, int k){
int value = 0;
int pos = 0;
int size = arrayA.length;
int[] arrayC = new int[k + 1];
for (int i = 0; i <= k; i++) {
arrayC[i] = 0;
}
//数组a中每一个value出现的个数，存储在c中，因为c中长度为k+1
//而a中元素最大值为k，所以可以存下这些值
for (int i = 0; i < size; i++) {
arrayC[arrayA[i]]++;
}
//数组C[i]中存放的是a中i元素出现的个数，所以C[i]+C[i-1],则是不大于i的元素的个数
for (int i = 1; i <= k; i++) {
arrayC[i] = arrayC[i] + arrayC[i-1];
}
//从数组c中取出a数组中元素不大于自己的个数，然后放入新数组b中，则排序已完成
for (int i = size-1; i >= 0; i--) {
value = arrayA[i];
pos = arrayC[value];
arrayB[pos-1]=value;
arrayC[value]--;
}
return arrayB;
}
2、基数排序
计数排序的使用条件有点尴尬，必须找到数组中的最大值，找最大值至少也要lgN的时间。基数排序，可理解为对计数排序的完美使用方式。
基数排序，将数组中的元素按照个十百千位分门别类，分别先后对个们、十位、百位、千位等排序，那么最后结果肯定也是有序的。假如针对所有元素的个位排序，由于个位上的最大值为9，非常符合计数排序的条件。由此，基数排序的算法就是，针对个、十、百等位置上使用计数排序。
public static int[] countSort2(int[] arrayA, int index){
int value = 0;
int pos = 0;
//个、十、百等位置上最大值为9
int k = 9;
int size = arrayA.length;
int[] arrayB = new int[size];
int[] arrayC = new int[k + 1];
for (int i = 0; i <= k; i++) {
arrayC[i] = 0;
}
//数组c中存的是数组a某个具体数位上的值的出现次数
for (int i = 0; i < size; i++) {
arrayC[getBitData(arrayA[i], index)]++;
}
for (int i = 1; i <= k; i++) {
arrayC[i] = arrayC[i] + arrayC[i-1];
}
//注意b中存放的是数组a中的值。
for (int i = size-1; i >= 0; i--) {
value = getBitData(arrayA[i], index);
pos = arrayC[value];
arrayB[pos-1]=arrayA[i];
arrayC[value]--;
}
return arrayB;
}
public static int[] radixSort(int[] arrayA,int index){
for (int i = 0; i < index; i++) {
arrayA = countSort2(arrayA, i);
}
return arrayA;
}
基数排序，非常适合比较时间大小等，以后遇到时间的排序应该第一时间想到基数排序。
本文中代码已上传到本人的github空间，欢迎访问
