第1节、一个萝卜一个坑——计数排序

无处不在的排序

上学时考试成绩从高到低排序,前几名会获得小花花;
淘宝剁手时,销量从高到低排序,买销量高的,群众的眼睛是雪亮的,大家的选择总没错,或者价格从低到高排序,便宜才是硬到底!
Windows系统和OS系统文件按照文件名称、时间排序同样离不开!
第1节、一个萝卜一个坑——计数排序

1、栗子

期末成绩出来了,大白考了第4名,得了6 分,总分10分,回家妈妈打他了一顿:你看邻居家的孩子考得多好呀!
第1节、一个萝卜一个坑——计数排序
家长会上,老师要求大家成绩从低到高排序,前三名奖励小红花,大家如何排队呢?

2、准备工作

一个萝卜一个坑,首先要准备很多个坑,之后把对应的萝卜放进去,之后数一下那个坑里有萝卜就OK了!

我们可以使用一个一维数组解决这个问题。

数组的长度为分数的范围,这里就是从0到10,等看完了就知道为什么要这样了。

首先申请一个长度为11的数组a[11],数据范围为a[0]~a[10],将数组全部初始化为0,表示这里没有人得过。

int a[11]={0};

开始读取每个人的分数(6,9,8,7,5),第一个人的分数为6,将a[6]设置为1,表示有一个人得了6分,同理将a[9]设置为1,表示有一个人得了9分……其他同理

每个人的分数处理完成之后,遍历下这个数组,如果数据a[i]为0,表示没有人得i分,否认就有,输出i就可以了。

3、代码

这里是完整代码,使用C语言

//输入:6 9 8 7 5
//输出:9 8 7 6 5
#include <stdio.h> 
int main()
{
    int a[11], i, j, t;
    //数组初始化为0
    for (i = 0;i <= 10;i++)
        a[i] = 0; 

    //计数排序,计算每个数出现的次数,之后排序
    for (i = 1;i <= 5;i++)
    {
        scanf("%d", &t);
        a[t]++; 
    }

    //输出结果
    for (i = 0;i <= 10;i++)
        for (j = 1;j <= a[i];j++)
            printf("%d ", i);
    
    //等待输入,避免最终结果一闪而过
    getchar();getchar();
    return 0;
}

4、优化

该算法于1954年由 Harold H. Seward 提出,距今已经N多年了,时间上只需要对数组进行一次遍历,复杂度O(n),时间表现很优秀;

空间上需要分配0~最大数据的空间,如果输入数据为(1,2,3,10000),只有4个数,却要分配a[10001],这么多的空间!

计数排序就是用空间换时间!大量的空间占用当然就存在优化的空间!

相关推荐