计数排序(C语言版本)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

让我们来谈谈数的排序思维：

计数排序假定待排序的全部元素都是介于0到K之间的整数。计数排序使用一个额外的数组countArray。当中第i个元素是待排序数组array中值等于i的元素的个数。然后依据数组countArray来将array中的元素排到正确的位置。

算法的步骤例如以下：

找出待排序的数组中最大和最小的元素
统计数组中每一个值为i的元素出现的次数，存入数组countArray的第i项
对全部的计数累加（从countArray中的第一个元素開始，每一项和前一项相加）
反向填充目标数组：将每一个元素i放在新数组的第countArray[i]项。每放一个元素就将countArray[i]减去1

稳定性和复杂度：

计数排序是稳定的排序算法；平均时间复杂度、最优时间复杂度和最差时间复杂度都为O(n+k)，空间复杂度为O(n+k)。当中，n为待排元素个数，k为待排元素的范围(0~k)。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>

#define RANDMAX 1000000
#define RANDMIN 900000

void getRandArray(int array[], int size);
void countSort(int array[], int size);
void isSorted(int array[], int size);

int main(int argc, char const *argv[])
{
    int size = 0;
    scanf("%d", &size);
    assert(size > 0);

    int *array = (int *)calloc(size, sizeof(int));
    getRandArray(array, size);

    clock_t begin;
    clock_t end;

    begin = clock();
    countSort(array, size);
    end = clock();
    //打印排序所花费的时间。在linux下单位为ms
    printf("%ld\n", (end - begin) / 1000);

    isSorted(array, size);
    free(array);

    return 0;
}


//利用伪随机数填充数组array。伪随机数的范围在RANDMIN~RANDMAX-1之间
void getRandArray(int array[], int size)
{
    assert(array != NULL && size > 0);

    srand((unsigned) time(NULL));
    int i = 0;
    for (i = 0; i < size; ++i) {
        array[i] = rand() % (RANDMAX - RANDMIN) + RANDMIN ;
    }
}

//从小到大进行排序
void countSort(int array[], int size)
{
    assert(array != NULL && size > 0);

    //计数数组，用于统计数组array中各个不同数出现的次数
    //由于数组array中的数属于0...RANDMAX-1之间，所以countArray的大小要够容纳RANDMAX个int型的值
    int *countArray = (int *) calloc(RANDMAX, sizeof(int));
    //用于存放已经有序的数列
    int *sortedArray = (int *) calloc(size, sizeof(int));

    //统计数组array中各个不同数出现的次数，循环结束后countArray[i]表示数值i在array中出现的次数
    int index = 0;
    for (index = 0; index < size; ++index) {
        countArray[array[index]]++;
    }

    //统计数值比index小的数的个数。循环结束之后countArray[i]表示array中小于等于数值i的元素个数
    for (index = 1; index < RANDMAX; ++index) {
        countArray[index] += countArray[index - 1];
    }

    for (index = size - 1; index >= 0; --index) {
        //由于数组的起始下标为0。所以要减一
        sortedArray[countArray[array[index]] - 1] = array[index];
        //这里减一是为了保证当有多个值为array[index]的元素时，后出现的值为array[index]的元素
        //放在后面，也就是为了保证排序的稳定性
        --countArray[array[index]];
    }

    memcpy(array, sortedArray, size * sizeof(int));
    free(sortedArray);
    free(countArray);
}

//推断数组array是否已经是有序的
void isSorted(int array[], int size)
{
    assert(array != NULL && size > 0);

    int unsorted = 0;
    int i = 0;
    for (i = 1; i < size; ++i) {
        if (array[i] < array[i - 1]) {
            unsorted = 1;
            break;
        }
    }

    if (unsorted) {
        printf("the array is unsorted!\n");
    } else {
        printf("the array is sorted!\n");
    }
}

计数排序是非比較的排序算法，据说其排序速度要快于不论什么的比較排序算法（我还未验证，可是在排序100000000个10000以内的数时花费为606毫秒，而C语言的qsort函数则为10802毫秒，由此可见一斑），因为计数排序须要一个计数数组以及一个存放有序数列的数组。故计数排序对内存的要求比較高。

------------------------------------------------------------------更新------------------------------------------------------------------

2014年10月20日

以上的实现有两个问题：

1、比較耗费内存：假设元素值的范围在9百万~1千万之间。上面的实现中countArray的大小须要1千万，而实际出现的不同值的元素就仅仅有1千万-9百万=1百万，也就是说用上面的实现会导致countArray中有90%的空间没有被利用，这个是非常浪费内存空间的！

尽管这个样例比較极端可是在详细应用面前还是须要注意！

2、不能出现负数：假设元素值中有负数。就不能用上面的实现方法了，由于counArray的下标是待排数组的元素值，所以上面的实现不能排序包括负数的数列。

解决方法：

1、第一个问题好解决：仅仅要首先一次遍历待排数组。找出最大值和最小值（眼下我所知的比較快的方法是时间复杂度为O(1.5n)的方法）。然后分配大小为（max-min+1）*sizeof(int)的空间给countArray即可了。至于统计的方法就得改变一点点了：

//从小到大进行排序，节省空间的版本号
void countSort2(int array[], int size)
{
    assert(array != NULL && size > 0);

    int min;
    int max;
    getMinAndMax(array, size, &min, &max);
    // printf("max - min + 1 = %d\n", max - min + 1);
    int countArraySize = max - min + 1;

    //计数数组，用于统计数组array中各个不同数出现的次数
    int *countArray = (int *) calloc(countArraySize, sizeof(int));
    //用于存放已经有序的数列
    int *sortedArray = (int *) calloc(size, sizeof(int));

    //统计数组array中各个不同数出现的次数。循环结束后countArray[i]表示数值i+min在array中出现的次数
    int index = 0;
    for (index = 0; index < size; ++index) {
        countArray[array[index] - min]++;
    }

    //统计数值比index小的数的个数。循环结束之后countArray[i]表示array中小于等于数值i+min的元素个数
    for (index = 1; index < countArraySize; ++index) {
        countArray[index] += countArray[index - 1];
    }

    for (index = size - 1; index >= 0; --index) {
        //由于数组的起始下标为0。所以要减一
        sortedArray[countArray[array[index] - min] - 1] = array[index];
        //这里减一是为了保证当有多个值为array[index]的元素时。后出现的值为array[index]的元素
        //放在后面，也就是为了保证排序的稳定性
        --countArray[array[index] - min];
    }

    memcpy(array, sortedArray, size * sizeof(int));
    free(sortedArray);
    free(countArray);
}

//待优化
void getMinAndMax(int array[], int size, int *min, int *max)
{
    assert(array != NULL && size > 0);
    if (size == 1) {
        *min = *max = array[0];
        return ;
    }

    *min = array[0];
    int index;
    for (index = 1; index < size; ++index) {
        if (array[index] < *min) {
            *min = array[index];
        }
    }
    *max = array[0];
    for (index = 1; index < size; ++index) {
        if (array[index] > *max) {
            *max = array[index];
        }
    }
}

这样的方法能够改进在元素值范围比較小的数列的排序时间（在大部分情况时间较短）和空间复杂度。因为仅仅是为了验证想法的可行性，就没有在查找最值的函数上下功夫优化。等以后有时间了。再进一步优化。

2、第二个问题：刚刚在洗漱的时候忽然想到了一个可行的方法：先一次遍历待排数组，找出负数中的最大值和最小值。正数中的最大值和最小值。创建两个计数数组，negativeCountArray用来统计待排数组中各个不同负数的出现个数，positiveCountArray用来统计待排数组中各个正数出现的个数，先统计总的负数的个数。然后再统计各个不同正数的个数，然后在往sortedArray中放元素的时候对正数和负数差别对待。这样就能让计数排序对包括负数的数列进行排序了。

代码例如以下：

//从小到大进行排序。节省空间,可排序负数的版本号
void countSort3(int array[], int size)
{
    assert(array != NULL && size > 0);

    int negativeMin;
    int negativeMax;
    int positiveMin;
    int positiveMax;
    _getMinAndMax(array, size, &negativeMin, &negativeMax, &positiveMin, &positiveMax);
    int positiveCountArraySize = positiveMax - positiveMin + 1;
    int negativeCountArraySize = negativeMax - negativeMin + 1;

    //计数数组，用于统计数组array中各个不同数出现的次数
    int *positiveCountArray = (int *) calloc(positiveCountArraySize, sizeof(int));
    int *negativeCountArray = (int *) calloc(negativeCountArraySize, sizeof(int));
    //用于存放已经有序的数列
    int *sortedArray = (int *) calloc(size, sizeof(int));

    //统计数组array中各个不同的数出现的次数，循环结束后positiveCountArray[i]表示数值i+positiveMin>=0在array中出现的次数
    //negativeCountArray[i]表示数值i+negativeMin<0在array中出现的次数
    int index = 0;
    for (index = 0; index < size; ++index) {
        if (array[index] < 0) {
            negativeCountArray[array[index] - negativeMin]++;
        } else {
            positiveCountArray[array[index] - positiveMin]++;
        }
    }

    //统计数值比index+negativeMin小的负数的个数。循环结束之后negativeCountArray
    for (index = 1; index < negativeCountArraySize; ++index) {
        negativeCountArray[index] += negativeCountArray[index - 1];
    }
    int negativeCount = negativeCountArray[index - 1];//负数的总数

    //统计数值比index小的非负数数的个数，循环结束之后positiveCountArray[i]表示array中小于等于数值i的值为非负数的元素个数
    for (index = 1; index < positiveCountArraySize; ++index) {
        positiveCountArray[index] += positiveCountArray[index - 1];
    }

    for (index = size - 1; index >= 0; --index) {
        if (array[index] < 0) {
            sortedArray[negativeCountArray[array[index] - negativeMin] - 1] = array[index];
            --negativeCountArray[array[index] - negativeMin];
        } else {
            //因为非负数总是比负数来的大，所以在把正数放到sortedArray时要在下标上加上负数的总个数
            sortedArray[positiveCountArray[array[index] - positiveMin] - 1 + negativeCount] = array[index];
            --positiveCountArray[array[index] - positiveMin];
        }
    }

    memcpy(array, sortedArray, size * sizeof(int));
    free(sortedArray);
    free(positiveCountArray);
    free(negativeCountArray);
}

//待优化
void _getMinAndMax(int array[], int size, int *negativeMin, int *negativeMax, int *positiveMin, int *positiveMax)
{
    assert(array != NULL && size > 0);
    if (size == 1) {
        *negativeMin = *negativeMax = *positiveMin = *positiveMax = array[0];
        return ;
    }

    int firstNegative = 0;
    int firstPositive = 0;
    int index;
    for (index = 0; index < size; ++index) {
        if (array[index] < 0) {
            firstNegative = array[index];
        }
    }
    for (index = 0; index < size; ++index) {
        if (array[index] > 0) {
            firstPositive = array[index];
        }
    }

    *negativeMin = firstNegative;
    *positiveMin = firstPositive;
    for (index = 0; index < size; ++index) {
        if (array[index] < 0 && array[index] < *negativeMin) {
            *negativeMin = array[index];
        }
        if (array[index] > 0 && array[index] < *positiveMin) {
            *positiveMin = array[index];
        }
    }
    *negativeMax = firstNegative;
    *positiveMax = firstPositive;
    for (index = 0; index < size; ++index) {
        if (array[index] < 0 && array[index] > *negativeMax) {
            *negativeMax = array[index];
        }
        if (array[index] > 0 && array[index] > *positiveMax) {
            *positiveMax = array[index];
        }
    }
}

因为仅仅是为了验证想法的可行性，就没有在查找最值的函数上下功夫优化，等以后有时间了。再进一步优化。

其它八种排序算法的博客：

通用9内部排序的类型(C语言)

鲜花

握手

雷人

路过

鸡蛋

该文章已有0人参与评论

请发表评论

全部评论

专题导读

More+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

C#Random()函数详解发布时间：2022-07-13

c++jsoncpp解析json发布时间：2022-07-13

剪的笔顺,诠释剪的笔画,认识剪的部首

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19254|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：10005|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8335|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8703|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8650|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9675|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8635|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：8008|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8671|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7542|2022-11-06

客服电话

电子邮件

计数排序(C语言版本)

请发表评论

全部评论

上一篇：

下一篇：

librespeed/speedtest: Self-hosted Speedt

avehtari/BDA_m_demos: Bayesian Data Anal

四维彩超怎么看性别？四维看男孩女孩诀窍

CVE-2022-34520

medfreeman/markdown-it-toc-and-anchor: m

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053