手写计数排序算法

实力程序员

关注

发布于: 11 小时前

计数排序算法的思想为：

待排序的数列中，先找出最小值 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);}

复制代码

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

发布于: 11 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/3b304dad929969a154ef17131】。

实力程序员

关注

实力程序员，用实力说话！ 2021.05.24 加入

超过20年一线产品研发和技术管理的实力程序员

发布

暂无评论

创作场景

手写计数排序算法

实力程序员

评论