2018/5/18 15:03:19当前位置推荐好文程序员浏览文章

1、栗子

期末成绩出来了,大白考了第4名,得了6 分,总分10分,回家妈妈打他了一顿:你看邻居家的孩子考得多好呀!


第四名

家长会上,老师要求大家成绩从低到高排序,前三名奖励小红花,大家如何排队呢?

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);        //等待输入,避免最终结果一闪而过    get);get);    return 0;}

4、优化

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

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

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

网友评论