计数排序算法

01 计数排序原理

假设输入n个元素，每个元素在区间0~k内的一个整数，区间k是最大值和最小值之间的区间。假如输入元素最大值是5，最小值是2，那么区间k=5 - 2 + 1 = 4。

计数排序算法思想：对于每一个输入元素x，确定小于等于元素x的个数，按照小于等于元素x的个数确定元素x在输出序列的索引。当有相同元素时，相同的元素要依次排列。

02 计数排序实现

现有序列[6, 3, 6, 1, 9, 5]，采用计数排序算法对序列进行排序。为了方便充分理解计数排序算法思想，我们做了如下图，详细表示计数排序过程，原始序列如下图所示。

求出序列最大值max和最小值min，进而求出序列元素所在区间k = max - min + 1，再求出小于等于元素x的个数。

小于元素x的个数正是元素x在输出序列中对应的索引（索引从0开始），考虑到序列可有相同的元素，同时又要保持Q(n)的时间复杂度，新建一个k大小的缓冲区，依次保存各个元素对应的索引值，如下图所示。

图中-1的索引表示无效索引，最后遍历原始序列，按照各个元素的对应的索引存放在输出序列中，相同元素依次排列，对应k区间内的保存的索引值加1。最终输出序列如下图所示。

计数排序算法实现代码如下：

void count_sort(int *input, int input_length, int *output, int output_length){
    if(input == NULL || output == NULL || output_length < input_length){
        return;
    }

    int k = 0, max, min;
    int i = 0;

    min = input[0];
    max = input[0];
    //找出最大值和最小值
    for(i = 0; i < input_length; i++){
        if(input[i] < min){
            min = input[i];
        }
        if(input[i] > max){
            max = input[i];
        }
    }
    k = max - min + 1; //求出数值区间
    int *temp = (int *)malloc(sizeof(int) * k);
    int *index = (int *)malloc(sizeof(int) * k);
    if(temp == NULL){
        return;
    }
    memset(temp, 0, sizeof(int) * k);
    memset(index, -1, sizeof(int) * k);
    int count = 0;
    for(i = 0; i < input_length; i++){
        temp[input[i] - min]++; //统计input里每个元素的个数
    }

    for(i = 0; i <= k; i++){
        count = temp[i];
        if(i > 0){
            temp[i] = temp[i] + temp[i - 1]; //统计input小于等于各个元素值的个数
        }
        if(count > 0){
            index[i] = temp[i] - count; //求出各个元素在输出序列中对应的索引值
        }
    }
    for(i = input_length - 1; i >= 0; i--){
        output[index[input[i] - min]] = input[i]; //将原始序列中的元素存放在输出序列对应索引中
        index[input[i] - min]++; //相同的数据相邻放置
        temp[input[i] - min]--;
    }
    free(temp);
    free(index);
}

写一个小程序验证计数排序算法的正确性。

#include <stdio.h>
#include "count_sort.h"

#define MAX_LENGTH 10

int main() {
    int input[MAX_LENGTH] = {1, 2, -3, 6, 7, 9, 3, 5, 4, 2};
    int output[MAX_LENGTH] = {0};

    count_sort(input, MAX_LENGTH, output, MAX_LENGTH);
    int i = 0;
    printf("计数排序输出结果\n");
    for(i = 0; i < MAX_LENGTH; i++){
        printf("%d ", output[i]);
    }
    printf("\n");

    return 0;
}

编译运行输出如下：

计数排序输出结果
-3 1 2 2 3 4 5 6 7 9

算法完全正确。