计数排序、基数排序

目录

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空间，欢迎访问