手写计数排序算法

举报
实力程序员 发表于 2021/07/27 09:34:03 2021/07/27
【摘要】 计数排序算法的思想为:待排序的数列中,先找出最小值min和最大值max,形成一个值区间[min, max]。然后建立一个存储空间,存储空间中的每个位置,对应值区间[min, max] 中的一个值,形成一对一的关系。每个位置上,存储这个值出现的次数,​叫做计数。初始计数值都为0。然后遍历待排序的数列,对每个值,将这个值对应的存储空间上​对应位置的计数值加一。遍历完成后,存储空间上每个位置对应的...

计数排序算法的思想为:
待排序的数列中,先找出最小值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.

2021-07-27_01.jpg

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

2021-07-27_02.jpg

根据桶内数据的值和计数,就能形成最终的​排好序数列:
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);
}


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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。