手写计数排序算法

计数排序算法的思想为：
待排序的数列中，先找出最小值min和最大值max，形成一个值区间[min, max]。
然后建立一个存储空间，存储空间中的每个位置，对应值区间[min, max] 中的一个值，形成一对一的关系。每个位置上，存储这个值出现的次数，​叫做计数。初始计数值都为0。
然后遍历待排序的数列，对每个值，将这个值对应的存储空间上​对应位置的计数值加一。
遍历完成后，存储空间上每个位置对应的值和计数，就形成了最终排好序的数列。

计数排序算法，本质上是一种桶排序，只是每个桶的大小为1，每个桶用一个值来计数。

用个例子来说明：
待排序数列为：
3 1 6 4 1

我们先找到最小值min为1， 最大值max为6。
那么就可以建立 max - min + 1 = 6 - 1 + 1 = 6 个桶，每个桶的初始计数都为0.

然后将待排序数列中的每个值，放入到对应的桶中，每放入一次，对应桶的计数加1​ ：

根据桶内数据的值和计数，就能形成最终的​排好序数列：
1，1， 3， 4， 6

计数排序算法，​用C语言实现的代码如下：

void counting_sort(int* parr, int count) {
    // 1. find min and max value
    int min = parr[0];
    int max = parr[0];
    for (int i = 1; i < count; i++) {
        if (parr[i] < min) {
            min = parr[i];
        } else if (parr[i] > max) {
            max = parr[i];
        }
    }

    // 2. alloc space for counting
    int n = max - min + 1;
    int* pbuf = (int*)malloc(n * sizeof(int));
    memset(pbuf, 0, n * sizeof(int));

    // 3. counting
    for (int i = 0; i < count; i++) {
        pbuf[parr[i] - min]++;
    }

    // 4. generate sorting array
    int idx = 0;
    for (int i = 0; i < n; i++) {
        if (pbuf[i] < 1) continue;
​
        for (int k = 0; k < pbuf[i]; k++) {
            parr[idx++] = min + i;
        }
    }

    // 5. free space
    free(pbuf);
}

​

我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。