欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-16 17:26:43
...

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();
    return 0;
}

4、优化

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

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

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