老青菜

计数排序

2019-05-12

计数排序(CountingSort)属于非比较类排序,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。

和其他排序不同,计数排序要求输入的数据必须是整数。


算法思路

  1. O(n)的时间扫描一下整个序列A,获取最小值min 和最大值 max
  2. 开辟一块新的空间创建新的数组B,长度为 (max - min + 1)
  3. 数组B中index的元素记录的值是A中某元素出现的次数
  4. 遍历数组B,输出相应元素以及对应的个数

代码实现

void countSort(int* array, int length) {
    if (length<=1) return ;
    // 获取最大最小值
    int maxValue = array[0];
    int minValue = array[0];
    for (int i=1; i<length; i++) {
        int tmpValue = array[i];
        maxValue = MAX(tmpValue, maxValue);
        minValue = MIN(tmpValue, minValue);
    }
    // 新建数组
    int newSize = maxValue - minValue + 1;
    int *newArray = malloc(sizeof(int)*newSize);
    for (int i = 0; i<newSize; i++) {
        newArray[i] = 0;
    }
    // 把 源数组元素 对应到 新数组 index中。
    for (int i = 0; i<length; i++) {
        int tmpValue = array[i];
        int valueIndex = tmpValue - minValue;
        int valueCount = newArray[valueIndex];
        newArray[valueIndex] = (valueCount + 1);
    }
    // 更新源数组【可选】
    int oldIndex = -1;
    for (int i = 0; i<newSize; i++) {
        int valueCount = newArray[i];
        if (valueCount == 0) continue;
        int value = minValue + i;
        for (int j=0; j<valueCount; j++) {
            oldIndex ++;
            array[oldIndex] = value;
        }
    }
    free(newArray);
}

算法分析

计数排序是一个稳定的排序算法,其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。。当输入的元素是 naa+k 之间的整数时:
时间复杂度是O(n+k)
空间复杂度是O(n+k)

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章