第 1 章 一大波数正在靠近——排序

第 1 章 一大波数正在靠近——排序

第 1 节 最快最简单的排序——桶排序

在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总之很多东东都需要排序,可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。

首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。小哼的班上只有5个同学,这5个同学分别考了5分、3分、5分、2分和8分,哎,考得真是惨不忍睹(满分是10分)。接下来将分数进行从大到小排序,排序后是8 5 5 3 2。你有没有什么好方法编写一段程序,让计算机随机读入5个数然后将这5个数从大到小输出?请先想一想,至少想15分钟再往下看吧(*^__^*)。

我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下看哦。

首先我们需要申请一个大小为11的数组int a[11]。OK,现在你已经有了11个变量,编号从a[0]~a[10]。刚开始的时候,我们将a[0]~a[10]都初始化为0,表示这些分数还都没有人得过。例如a[0]等于0就表示目前还没有人得过0分,同理a[1]等于0就表示目前还没有人得过1分……a[10]等于0就表示目前还没有人得过10分。

{%}

下面开始处理每一个人的分数,第一个人的分数是5分,我们就将相对应的a[5]的值在原来的基础增加1,即将a[5]的值从0改为1,表示5分出现过了一次。

{%}

第二个人的分数是3分,我们就把相对应的a[3]的值在原来的基础上增加1,即将a[3]的值从0改为1,表示3分出现过了一次。

{%}

注意啦!第三个人的分数也是5分,所以a[5]的值需要在此基础上再增加1,即将a[5]的值从1改为2,表示5分出现过了两次。

{%}

按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。

{%}

你发现没有,a[0]~a[10]中的数值其实就是0分到10分每个分数出现的次数。接下来,我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次,具体如下。

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”没有出现过,不打印。

最终屏幕输出“2 3 5 5 8”,完整的代码如下。

#include <stdio.h>
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<=10;i++)改为for(i=10;i>=0;i--)就OK啦,快去试一试吧。

这种排序方法我们暂且叫它“桶排序”。因为其实真正的桶排序要比这个复杂一些,以后再详细讨论,目前此算法已经能够满足我们的需求了。

这个算法就好比有11个桶,编号从0~10。每出现一个数,就在对应编号的桶中放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。例如2号桶中有1个小旗子,表示2出现了一次;3号桶中有1个小旗子,表示3出现了一次;5号桶中有2个小旗子,表示5出现了两次;8号桶中有1个小旗子,表示8出现了一次。

现在你可以尝试一下输入n个0~1000之间的整数,将它们从大到小排序。提醒一下,如果需要对数据范围在0~1000的整数进行排序,我们需要1001个桶,来表示0~1000之间每一个数出现的次数,这一点一定要注意。另外,此处的每一个桶的作用其实就是“标记”每个数出现的次数,因此我喜欢将之前的数组a换个更贴切的名字book(book这个单词有记录、标记的意思),代码实现如下。

#include <stdio.h>

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)。还有一点,在表示时间复杂度的时候,nm通常用大写字母即O(M+N)

这是一个非常快的排序算法。桶排序从1956年就开始被使用,该算法的基本思想是由E.J. Issac和R.C. Singleton提出来的。之前我说过,其实这并不是真正的桶排序算法,真正的桶排序算法要比这个更加复杂。但是考虑到此处是算法讲解的第一篇,我想还是越简单易懂越好,真正的桶排序留在以后再聊吧。需要说明一点的是:我们目前学习的简化版桶排序算法,其本质上还不能算是一个真正意义上的排序算法。为什么呢?例如遇到下面这个例子就没辙了。

现在分别有5个人的名字和分数:huhu 5分、haha 3分、xixi 5分、hengheng 2分和gaoshou 8分。请按照分数从高到低,输出他们的名字。即应该输出gaoshou、huhu、xixi、haha、hengheng。发现问题了没有?如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输出的也仅仅是分数,但没有对人本身进行排序。也就是说,我们现在并不知道排序后的分数原本对应着哪一个人!这该怎么办呢?不要着急,请看下节——冒泡排序。

第 2 节 邻居好说话——冒泡排序

简化版的桶排序不仅仅有上一节所遗留的问题,更要命的是:它非常浪费空间!例如需要排序数的范围是0~2100000000,那你则需要申请2100000001个变量,也就是说要写成int a[2100000001]。因为我们需要用2100000001个“桶”来存储0~2100000000每一个数出现的次数。即便只给你5个数进行排序(例如这5个数是1、1912345678、2100000000、18000000和912345678),你也仍然需要2100000001个“桶”,这真是太浪费空间了!还有,如果现在需要排序的不再是整数而是一些小数,比如将5.56789、2.12、1.1、3.123、4.1234这五个数进行从小到大排序又该怎么办呢?现在我们来学习另一种新的排序算法:冒泡排序。它可以很好地解决这两个问题。

冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。

例如我们需要将12 35 99 18 76这5个数进行从大到小的排序。既然是从大到小排序,也就是说越小的越靠后,你是不是觉得我在说废话,但是这句话很关键(∩_∩)。

首先比较第1位和第2位的大小,现在第1位是12,第2位是35。发现12比35要小,因为我们希望越小越靠后嘛,因此需要交换这两个数的位置。交换之后这5个数的顺序是35 12 99 18 76。

按照刚才的方法,继续比较第2位和第3位的大小,第2位是12,第3位是99。12比99要小,因此需要交换这两个数的位置。交换之后这5个数的顺序是35 99 12 18 76。

根据刚才的规则,继续比较第3位和第4位的大小,如果第3位比第4位小,则交换位置。交换之后这5个数的顺序是35 99 18 12 76。

最后,比较第4位和第5位。4次比较之后5个数的顺序是35 99 18 76 12

经过4次比较后我们发现最小的一个数已经就位(已经在最后一位,请注意12这个数的移动过程),是不是很神奇。现在再来回忆一下刚才比较的过程。每次都是比较相邻的两个数,如果后面的数比前面的数大,则交换这两个数的位置。一直比较下去直到最后两个数比较完毕后,最小的数就在最后一个了。就如同是一个气泡,一步一步往后“翻滚”,直到最后一位。所以这个排序的方法有一个很好听的名字“冒泡排序”。

说到这里其实我们的排序只将5个数中最小的一个归位了。每将一个数归位我们将其称为“一趟”。下面我们将继续重复刚才的过程,将剩下的4个数一一归位。

好,现在开始“第二趟”,目标是将第2小的数归位。首先还是先比较第1位和第2位,如果第1位比第2位小,则交换位置。交换之后这5个数的顺序是99 35 18 76 12。接下来你应该都会了,依次比较第2位和第3位,第3位和第4位。注意此时已经不需要再比较第4位和第5位。因为在第一趟结束后已经可以确定第5位上放的是最小的了。第二趟结束之后这5个数的顺序是99 35 76 18 12。

“第三趟”也是一样的。第三趟之后这5个数的顺序是99 76 35 18 12。

现在到了最后一趟“第四趟”。有的同学又要问了,这不是已经排好了吗?还要继续?当然,这里纯属巧合,你若用别的数试一试可能就不是了。你能找出这样的数据样例来吗?请试一试。

“冒泡排序”的原理是:每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数(即第5位)归位,第二趟只能将倒数第2位上的数(即第4位)归位,第三趟只能将倒数第3位上的数(即第3位)归位,而现在前面还有两个位置上的数没有归位,因此我们仍然需要进行“第四趟”。

“第四趟”只需要比较第1位和第2位的大小。因为后面三个位置上的数归位了,现在第1位是99,第2位是76,无需交换。这5个数的顺序不变仍然是99 76 35 18 12。到此排序完美结束了,5个数已经有4个数归位,那最后一个数也只能放在第1位了。

最后我们总结一下:如果有n个数进行排序,只需将n-1个数归位,也就是说要进行n-1趟操作。而“每一趟”都需要从第1位开始进行相邻两个数的比较,将较小的一个数放在后面,比较完毕后向后挪一位继续比较下面两个相邻数的大小,重复此步骤,直到最后一个尚未归位的数,已经归位的数则无需再进行比较(已经归位的数你还比较个啥,浪费表情)。

这个算法是不是很强悍?记得我每次拍集体照的时候就总是被别人换来换去的,当时特别烦。不知道发明此算法的人当时的灵感是否来源于此。啰里吧嗦地说了这么多,下面是代码。建议先自己尝试去实现一下看看,再来看我是如何实现的。

#include <stdio.h>
int main()
{
    int a[100],i,j,t,n;
    scanf("%d",&n);  //输入一个数n,表示接下来有n个数
    for(i=1;i<=n;i++)  //循环读入n个数到数组a中
        scanf("%d",&a[i]);
    //冒泡排序的核心部分
    for(i=1;i<=n-1;i++) //n个数排序,只用进行n-1趟
    {
        for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数,想一想为什么到n-i就可以了。
        {
            if(a[j]<a[j+1]) //比较大小并交换
            {  t=a[j]; a[j]=a[j+1]; a[j+1]=t;  }
        }
    }
    for(i=1;i<=n;i++)  //输出结果
        printf("%d ",a[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

将上面代码稍加修改,就可以解决第1节遗留的问题,如下。

#include <stdio.h>
struct student
{
    char name[21];
    int score;
};//这里创建了一个结构体用来存储姓名和分数
int main()
{
    struct student a[100],t;
    int i,j,n;
    scanf("%d",&n); //输入一个数n
    for(i=1;i<=n;i++) //循环读入n个人名和分数
        scanf("%s %d",a[i].name,&a[i].score);
    //按分数从高到低进行排序
    for(i=1;i<=n-1;i++)
    {
        for(j=1;j<=n-i;j++)
        {
            if(a[j].score<a[j+1].score)//对分数进行比较
            {  t=a[j]; a[j]=a[j+1]; a[j+1]=t;  }
        }
    }
    for(i=1;i<=n;i++)//输出人名
        printf("%s\n",a[i].name);

    getchar();getchar();
    return 0;
}

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

5
huhu 5
haha 3
xixi 5
hengheng 2
gaoshou 8

运行结果是:

gaoshou
huhu
xixi
haha
hengheng

冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是O(N^2)。这是一个非常高的时间复杂度。冒泡排序早在1956年就有人开始研究,之后有很多人都尝试过对冒泡排序进行改进,但结果却令人失望。如Donald E. Knuth(中文名为高德纳,1974年图灵奖获得者)所说:“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外,似乎没有什么值得推荐的。”你可能要问:那还有没有更好的排序算法呢?不要走开,请看下节——快速排序。

第 3 节 最常用的排序——快速排序

上一节的冒泡排序可以说是我们学习的第一个真正的排序算法,并且解决了桶排序浪费空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了O(N^2)。假如我们的计算机每秒钟可以运行10亿次,那么对1亿个数进行排序,桶排序只需要0.1秒,而冒泡排序则需要1千万秒,达到115天之久,是不是很吓人?那有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢?

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,这就是一个用来参照的数,待会儿你就知道它用来做啥了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。

3  1  2  5  4  6  9  7  10  8

在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?

给你一个提示吧。请回忆一下冒泡排序是如何通过“交换”一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢?怎样交换才既方便又节省时间呢?先别急着往下看,拿出笔来,在纸上画画看。我高中时第一次学习冒泡排序算法的时候,就觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小地自恋一下(^o^)。

方法其实很简单:分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从找一个小于6的数,再从找一个大于6的数,然后交换它们。这里可以用两个变量ij,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j--),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。

6  1  2  5  9  3  4  7  10  8

到此,第一次交换结束。接下来哨兵j继续向左挪动(再次友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下。

6  1  2  5  4  3  9  7  10  8

第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。

3  1  2  5  4  6  9  7  10  8

到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到ij碰头为止。

OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列,因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列吧。

左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧。

不用找纸了,别以为我不知道你的小伎俩,你肯定又没有动手尝试!就准备继续往下看了吧。这里我留了一个空白区域,赶快自己动手模拟一下吧!

如果你模拟得没有错,调整完毕之后的序列的顺序应该是:

2  1  3  5  4

OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到的序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下。

1  2  3  4  5  6  9  7  10  8

对于序列“9 7 10 8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列:

1  2  3  4  5  6  7  8  9  10

到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

{%}

快速排序之所以比较快,是因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换,交换的距离就大得多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的,都是O(N^2),它的平均时间复杂度为O(N\log N)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想,到时候再聊。先上代码,如下。

#include <stdio.h>
int a[101],n;//定义全局变量,这两个变量需要在子函数中使用

void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
       return;

    temp=a[left]; //temp中存的就是基准数
    i=left;
    j=right;
    while(i!=j)
    {
        //顺序很重要,要先从右往左找
        while(a[j]>=temp && i<j)
            j--;
        //再从左往右找
        while(a[i]<=temp && i<j)
            i++;

        //交换两个数在数组中的位置
        if(i<j)//当哨兵i和哨兵j没有相遇时
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    //最终将基准数归位
    a[left]=a[i];
    a[i]=temp;

    quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程
    quicksort(i+1,right);//继续处理右边的,这里是一个递归的过程
}

int main()
{
    int i;
    //读入数据
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);

    quicksort(1,n); //快速排序调用

    //输出排序后的结果
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);

    getchar();getchar();
    return 0;
}

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

10
6  1  2  7  9  3  4  5  10  8

运行结果是:

1 2 3 4 5 6 7 8 9 10

下面是程序执行过程中数组a的变化过程,带下划线的数表示的是已归位的基准数。

6 1 2 7 9 3 4 5 10 8
3 1 2 5 4 6 9 7 10 8
2 1 3 5 4 6 9 7 10 8
1 2 3 5 4 6 9 7 10 8
1 2 3 5 4 6 9 7 10 8
1 2 3 4 5 6 9 7 10 8
1 2 3 4 5 6 9 7 10 8
1 2 3 4 5 6 8 7 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

快速排序由 C. A. R. Hoare(东尼·霍尔,Charles Antony Richard Hoare)在1960年提出,之后又有许多人做了进一步的优化。如果你对快速排序感兴趣,可以去看看东尼·霍尔1962年在Computer Journal发表的论文“Quicksort”以及《算法导论》的第七章。快速排序算法仅仅是东尼·霍尔在计算机领域才能的第一次显露,后来他受到了老板的赏识和重用,公司希望他为新机器设计一种新的高级语言。你要知道当时还没有PASCAL或者C语言这些高级的东东。后来东尼·霍尔参加了由Edsger Wybe Dijkstra(1972年图灵奖得主,这个大神我们后面还会遇到的,到时候再细聊)举办的ALGOL 60培训班,他觉得自己与其没有把握地去设计一种新的语言,还不如对现有的ALGOL 60进行改进,使之能在公司的新机器上使用。于是他便设计了ALGOL 60的一个子集版本。这个版本在执行效率和可靠性上都在当时ALGOL 60的各种版本中首屈一指,因此东尼·霍尔受到了国际学术界的重视。后来他在ALGOL X的设计中还发明了大家熟知的case语句,也被各种高级语言广泛采用,比如PASCAL、C、Java语言等等。当然,东尼·霍尔在计算机领域的贡献还有很多很多,他在1980年获得了图灵奖。

第 4 节 小哼买书

排序算法还有很多,例如我在《啊哈C!思考快你一步》一书中讲过的选择排序,另外还有计数排序、基数排序、插入排序、归并排序和堆排序等等。堆排序是基于二叉树的排序,我会在后面的章节讲到。现在来看一个具体的例子“小哼买书”(根据全国青少年信息学奥林匹克联赛NOIP2006普及组第一题改编),来实践一下本章所学的三种排序算法。

小哼的学校要建立一个图书角,老师派小哼去找一些同学做调查,看看同学们都喜欢读哪些书。小哼让每个同学写出一个自己最想读的书的ISBN号(你知道吗?每本书都有唯一的ISBN号,不信的话你去找本书翻到背面看看)。当然有一些好书会有很多同学都喜欢,这样就会收集到很多重复的ISBN号。小哼需要去掉其中重复的ISBN号,即每个ISBN号只保留一个,也就说同样的书只买一本(学校真是够抠门的)。然后再把这些ISBN号从小到大排序,小哼将按照排序好的ISBN号去书店买书。请你协助小哼完成“去重”与“排序”的工作。

输入有2行,第1行为一个正整数,表示有n个同学参与调查(n\leqslant100)。第2行有n个用空格隔开的正整数,为每本图书的ISBN号(假设图书的ISBN号在1~1000)。

输出也是2行,第1行为一个正整数k,表示需要买多少本书。第2行为k个用空格隔开的正整数,为从小到大已排好序的需要购买的图书的ISBN号。

例如输入:

10
20 40 32 67 40 20 89 300 400 15

则输出:

8
15 20 32 40 67 89 300 400

最后,程序运行的时间限制为1秒。

解决这个问题的方法大致有两种。第一种方法:先将这n个图书的ISBN号去重,再进行从小到大排序并输出;第二种方法:先从小到大排序,输出的时候再去重。这两种方法都可以。

先来看第一种方法。通过第一节的学习我们发现,桶排序稍加改动正好可以起到去重的效果,因此我们可以使用桶排序的方法来解决此问题。

#include <stdio.h>
int main()
{
    int a[1001],n,i,t;
    for(i=1;i<=1000;i++)
        a[i]=0; //初始化

    scanf("%d",&n); //读入n
    for(i=1;i<=n;i++) //循环读入n个图书的ISBN号
    {
        scanf("%d",&t); //把每一个ISBN号读到变量t中
        a[t]=1; //标记出现过的ISBN号
    }

    for(i=1;i<=1000;i++) //依次判断1~1000这个1000个桶
    {
        if(a[i]==1)//如果这个ISBN号出现过则打印出来
             printf("%d ",i);
    }

    getchar();getchar();
    return 0;
}

这种方法的时间复杂度就是桶排序的时间复杂度,为o(N+M)

第二种方法我们需要先排序再去重。排序我们可以用冒泡排序或者快速排序。

20 40 32 67 40 20 89 300 400 15

将这10个数从小到大排序之后为 15 20 20 32 40 40 67 89 300 400。

接下来,要在输出的时候去掉重复的。因为我们已经排好序,所以相同的数都会紧挨在一起。只要在输出的时候,预先判断一下当前这个数a[i]与前面一个数a[i-1]是否相同。如果相同则表示这个数之前已经输出过了,不用再次输出;不同则表示这个数是第一次出现,需要输出这个数。

#include <stdio.h>
int main()
{
    int a[101],n,i,j,t;

    scanf("%d",&n);   //读入n
    for(i=1;i<=n;i++) //循环读入n个图书ISBN号
    {
        scanf("%d",&a[i]);
    }

   //开始冒泡排序
    for(i=1;i<=n-1;i++)
    {
        for(j=1;j<=n-i;j++)
        {
            if(a[j]>a[j+1])
            {  t=a[j]; a[j]=a[j+1]; a[j+1]=t;  }
        }
    }
    printf("%d ",a[1]); //输出第1个数
    for(i=2;i<=n;i++) //从2循环到n
    {
        if( a[i] != a[i-1] ) //如果当前这个数是第一次出现则输出
             printf("%d ",a[i]);
    }

    getchar();getchar();
    return 0;
}

这种方法的时间复杂度由两部分组成,一部分是冒泡排序的时间复杂度,是O(N^2),另一部分是读入和输出,都是O(N),因此整个算法的时间复杂度是O(2^*N+N^2)。相对于N^2来说,2^*N可以忽略(我们通常忽略低阶),最终该方法的时间复杂度是O(N^2)

接下来还需要看下数据范围。每个图书ISBN号都是1~1000的整数,并且参加调查的同学人数不超过100,即n≤100。之前已经说过,在粗略计算时间复杂度的时候,我们通常认为计算机每秒钟大约运行10亿次(当然实际情况要更快),因此以上两种方法都可以在1秒钟内计算出解。如果题目中图书的ISBN号范围不是在1~1000,而是-2147483648~2147483647的话,那么第一种方法就不可行了,因为你无法申请出这么大的数组来标记每一个ISBN号是否出现过。另外如果n的范围不是小于等于100,而是小于等于10万,那么第二种方法的排序部分也不能使用冒泡排序。因为题目要求的时间限制是1秒,使用冒泡排序对10万个数进行排序,计算机要运行100亿次,需要10秒钟,因此要替换为快速排序,快速排序只需要100000×log2100000≈100000×17≈170万次,这还不到0.0017秒。是不是很神奇?同样的问题使用不同的算法竟然有如此之大的时间差距,这就是算法的魅力!

我们来回顾一下本章三种排序算法的时间复杂度。桶排序是最快的,它的时间复杂度是O(N+M);冒泡排序是O(N^2);快速排序是O(N\log N)

最后,你可以到“添柴-编程学习网”提交本题的代码,来验证一下你的解答是否完全正确。《小哼买书》题目的地址如下:

www.tianchai.org/problem-12001.html

接下来,本书中的所有算法都可以去“添柴-编程学习网”一一验证。如果你从来没有使用过类似“添柴-编程学习网”这样的在线自动评测系统(online judge),那么我推荐你可以先尝试提交下这道题:A+B=? 地址如下:

www.tianchai.org/problem-10000.html

目录