你有没有什么好方法编写一段程序?排序算法详解

前言

我们生活的世界充满了分类的东西。排队时会按身高排序,考试的排名需要按分数排序,网购时会按价格排序,邮件里的邮件会按时间排序。简而言之,很多东西都需要排序,可以说排序无处不在。. 现在我们举一个具体的例子来介绍排序算法。

桶排序

最先出现的是我们的主角小恒,上面的萌娃。期末考试结束后,老师将学生的分数从高到低排序。小恒班里只有5个学生,这5个学生分别考了5分、3分、5分、2分和8分。哎,考试真惨(满分10分)。接下来,将分数从大到小排序,排序后为 8 5 5 3 2。有没有什么好办法写一个程序,让电脑随机读取5个数字,然后从大到小输出这5个数字?请在往下看之前至少考虑 15 分钟 (*^__^*)。

我们可以在这里借助一维数组来解决这个问题。在你往下看之前,请确保你真的仔细考虑过。首先我们需要申请一个大小为11的数组int a[11]。好的,现在你有11个变量,编号从a[0]~a[10]。一开始,我们将a[0]~a[10]初始化为0,表示目前还没有人获得这些分数。例如,如果 a[0] 等于 0,则表示没有人得 0 分。同样,如果a[1]等于0,则表示没有人得1分。10分以上。

让我们开始处理每个人的分数。第一人得5分。我们将对应的 a[5] 值在原来的基础上增加 1 ,即将 a[5] 的值从 0 变为 1 ,表示出现了 5 个点。

第二个人的得分是3分计算机上的m+是什么意思,我们将a[3]的对应值在原来的基础上加1,即a[3]的值从0变为1,表示3分出现过一次。

注意力!第三人的分数也是5分,所以需要在此基础上将a[5]的值加1,即a[5]的值由1变为2,表示已经出现5分两次。

像刚才那样处理第四个人和第五个人的分数。最终结果如下图。

你发现没有,a[0]~a[10]里面的值其实就是从0到10每个score出现的次数。接下来我们只需要打印出已经出现的scores计算机上的m+是什么意思,打印几次,如下。

a[0]为 0,表示“0”没有出现过,不打印。 
a[1]为 0,表示“1”没有出现过,不打印。 
a[2]为 1,表示“2”出现过 1 次,打印 2。 
a[3]为 1,表示“3”出现过 1 次,打印 3。 
a[4]为 0,表示“4”没有出现过,不打印。 
a[5]为 2,表示“5”出现过 2 次,打印 5 5。 
a[6]为 0,表示“6”没有出现过,不打印。 
a[7]为 0,表示“7”没有出现过,不打印。 
a[8]为 1,表示“8”出现过 1 次,打印 8。 
a[9]为 0,表示“9”没有出现过,不打印。 
a[10]为 0,表示“10”没有出现过,不打印。 

图片[1]-你有没有什么好方法编写一段程序?排序算法详解-老王博客

最终画面输出“2 3 5 5 8”,完整代码如下。

#include  
int main() 
{ 
    int a[11],i,j,t; 
    for(i=0;i<=10;i++) 
        a[i]=0;  //初始化为0 
     
    for(i=1;i<=5;i++)  //循环读入5个数 
    { 
        scanf("%d",&t);  //把每一个数读到变量t中 
        a[t]++;  //进行计数 
    } 
 
    for(i=0;i<=10;i++)  //依次判断a[0]~a[10] 
        for(j=1;j<=a[i];j++)  //出现了几次就打印几次 
            printf("%d ",i); 
 
    getchar();getchar();  
    //这里的getchar();用来暂停程序,以便查看程序输出的内容 
    //也可以用system("pause");等来代替 
    return 0; 
}

输入数据为:

5 3 5 2 8

仔细观察的同学会发现,刚刚实现的东西是从小到大排序的。但是我们要求从大到小排序,怎么办?或者在往下看之前自己考虑一下。

这真的很容易。你只需要设置 for(i=0;i=0;i--) 就可以了,我们试试看。

我们暂时称这种排序方法为“桶排序”。因为其实真正的桶排序比这复杂的多,我们后面会详细讨论。目前,该算法可以满足我们的需求。

这个算法就像有 11 个桶,从 0 到 10 编号。每出现一个数字,就在桶中放一个对应数字的小标志,最后只计算每个桶有多少个小标志。比如2号桶有一个小flag,表示2出现了一次;3号桶有一个小flag,表示3出现了一次;5号桶有2个小flag,表示5出现了两次;8号枪管有一个小标志,表示8号出现一次。

现在您可以尝试输入 0 到 1000 之间的 n 个整数,并将它们从大到小排序。提醒一下,如果我们需要对 0~1000 的数据范围内的整数进行排序,我们需要 1001 个桶来表示每个数字在 0 到 1000 之间的出现次数。这个大家一定要注意。另外这里每个bucket的作用其实就是“标记”每个数字出现的次数,所以我喜欢把前面的数组a改成更合适的名字book(book这个词的意思是记录和标记),代码实现如下。

#include  
 
int main() 
{ 
    int book[1001],i,j,t,n; 
    for(i=0;i<=1000;i++) 
        book[i]=0;  
    scanf("%d",&n);//输入一个数n,表示接下来有n个数 
    for(i=1;i<=n;i++)//循环读入n个数,并进行桶排序 
    { 
        scanf("%d",&t);  //把每一个数读到变量t中 
        book[t]++;  //进行计数,对编号为t的桶放一个小旗子 
    } 
    for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶 
        for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次 
             printf("%d ",i); 
 
    getchar();getchar(); 
    return 0; 
}

可以输入以下数据进行验证。

10 
8 100 50 22 15 6 1 1000 999 0

运行的结果是:

1000 999 100 50 22 15 8 6 1 0

最后,让我们谈谈时间复杂度。代码中第6行的循环一共循环了m次(m为桶的个数),第9行的代码循环了n次(n为要排序的数),第14行和第15行循环了共 m+n 次。所以整个排序算法总共执行了 m+n+m+n 次。我们用大写字母O来表示时间复杂度,所以这个算法的时间复杂度是O(m+n+m+n)或者O(2*(m+n))。说到时间复杂度我们可以忽略更小的常数,桶排序的最终时间复杂度是O(m+n)。还有一点就是在表达时间复杂度的时候,n和m通常用大写字母写,也就是O(M+N)。

这是一种非常快速的排序算法。桶排序从 1956 年就开始使用,算法的基本思想是由 EJ Issac 和 RC Singleton 提出的。之前说过,其实这不是真正的桶排序算法,真正的桶排序算法比这个复杂。但考虑到这是算法讲解的第一部分,我觉得越简单易懂越好,后面会讨论真正的桶排序。需要注意的是,我们目前学习的桶排序算法的简化版并不能算是真正意义上的排序算法。为什么?例如,以下示例不起作用。

现在有5个人的名字和分数:呼呼5分,哈哈3分,喜喜5分,恒恒2分,高手8分。请按照分数从高到低输入他们的名字。也就是要输出高手、呼呼、喜喜、哈哈、恒恒。

发现问题了吗?如果我们只使用桶排序算法的简化版本,我们只需对分数进行排序。最终输出的只是分数,人本身并没有排序。也就是说,我们现在不知道排序后的分数原来对应的是哪个人!这个怎么做?下一篇将介绍——冒泡排序。

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享
评论 抢沙发

请登录后发表评论