啊哈算法.pdf
- 文档编号:3437686
- 上传时间:2023-05-05
- 格式:PDF
- 页数:24
- 大小:2.29MB
啊哈算法.pdf
《啊哈算法.pdf》由会员分享,可在线阅读,更多相关《啊哈算法.pdf(24页珍藏版)》请在冰点文库上搜索。
第1章一大波数正在靠近排序1一大波数正在靠近排序第1章啊哈!
算法2第1节最快最简单的排序桶排序在我们生活的这个世界中到处都是被排序过的东东。
站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序总之很多东东都需要排序,可以说排序是无处不在。
现在我们举个具体的例子来介绍一下排序算法。
首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。
期末考试完了老师要将同学们的分数按照从高到低排序。
小哼的班上只有5个同学,这5个同学分别考了5分、3分、5分、2分和8分,哎,考得真是惨不忍睹(满分是10分)。
接下来将分数进行从大到小排序,排序后是85532。
你有没有什么好方法编写一段程序,让计算机随机读入5个数然后将这5个数从大到小输出?
请先想一想,至少想15分钟再往下看吧(*_*)。
第1章一大波数正在靠近排序3我们这里只需借助一个一维数组就可以解决这个问题。
请确定你真的仔细想过再往下看哦。
首先我们需要申请一个大小为11的数组inta11。
OK,现在你已经有了11个变量,编号从a0a10。
刚开始的时候,我们将a0a10都初始化为0,表示这些分数还都没有人得过。
例如a0等于0就表示目前还没有人得过0分,同理a1等于0就表示目前还没有人得过1分a10等于0就表示目前还没有人得过10分。
下面开始处理每一个人的分数,第一个人的分数是5分,我们就将相对应的a5的值在原来的基础增加1,即将a5的值从0改为1,表示5分出现过了一次。
第二个人的分数是3分,我们就把相对应的a3的值在原来的基础上增加1,即将a3的值从0改为1,表示3分出现过了一次。
啊哈!
算法4注意啦!
第三个人的分数也是5分,所以a5的值需要在此基础上再增加1,即将a5的值从1改为2,表示5分出现过了两次。
按照刚才的方法处理第四个和第五个人的分数。
最终结果就是下面这个图啦。
你发现没有,a0a10中的数值其实就是0分到10分每个分数出现的次数。
接下来,我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次,具体如下。
a0为0,表示“0”没有出现过,不打印。
a1为0,表示“1”没有出现过,不打印。
a2为1,表示“2”出现过1次,打印2。
a3为1,表示“3”出现过1次,打印3。
a4为0,表示“4”没有出现过,不打印。
a5为2,表示“5”出现过2次,打印55。
a6为0,表示“6”没有出现过,不打印。
a7为0,表示“7”没有出现过,不打印。
a8为1,表示“8”出现过1次,打印8。
a9为0,表示“9”没有出现过,不打印。
a10为0,表示“10”没有出现过,不打印。
最终屏幕输出“23558”,完整的代码如下。
#includeintmain()inta11,i,j,t;for(i=0;i=10;i+)ai=0;/初始化为0for(i=1;i=5;i+)/循环读入5个数第1章一大波数正在靠近排序5scanf(%d,&t);/把每一个数读到变量t中at+;/进行计数for(i=0;i=10;i+)/依次判断a0a10for(j=1;j=ai;j+)/出现了几次就打印几次printf(%d,i);getchar();getchar();/这里的getchar();用来暂停程序,以便查看程序输出的内容/也可以用system(pause);等来代替return0;输入数据为:
53528仔细观察的同学会发现,刚才实现的是从小到大排序。
但是我们要求是从大到小排序,这该怎么办呢?
还是先自己想一想再往下看哦。
其实很简单。
只需要将for(i=0;i=0;i-)就OK啦,快去试一试吧。
这种排序方法我们暂且叫它“桶排序”。
因为其实真正的桶排序要比这个复杂一些,以后再详细讨论,目前此算法已经能够满足我们的需求了。
这个算法就好比有11个桶,编号从010。
每出现一个数,就在对应编号的桶中放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。
例如2号桶中有1个小旗子,表示2出现了一次;3号桶中有1个小旗子,表示3出现了一次;5号桶中有2个小旗子,表示5出现了两次;8号桶中有1个小旗子,表示8出现了一次。
现在你可以尝试一下输入n个01000之间的整数,将它们从大到小排序。
提醒一下,啊哈!
算法6如果需要对数据范围在01000的整数进行排序,我们需要1001个桶,来表示01000之间每一个数出现的次数,这一点一定要注意。
另外,此处的每一个桶的作用其实就是“标记”每个数出现的次数,因此我喜欢将之前的数组a换个更贴切的名字book(book这个单词有记录、标记的意思),代码实现如下。
#includeintmain()intbook1001,i,j,t,n;for(i=0;i=1000;i+)booki=0;scanf(%d,&n);/输入一个数n,表示接下来有n个数for(i=1;i=0;i-)/依次判断编号10000的桶for(j=1;j=booki;j+)/出现了几次就将桶的编号打印几次printf(%d,i);getchar();getchar();return0;可以输入以下数据进行验证。
1081005022156110009990运行结果是:
10009991005022158610最后来说下时间复杂度的问题。
代码中第6行的循环一共循环了m次(m为桶的个数),第9行的代码循环了n次(n为待排序数的个数),第14行和第15行一共循环了m+n次。
所以整个排序算法一共执行了m+n+m+n次。
我们用大写字母O来表示时间复杂度,因此该第1章一大波数正在靠近排序7算法的时间复杂度是O(m+n+m+n)即O(2*(m+n)。
我们在说时间复杂度的时候可以忽略较小的常数,最终桶排序的时间复杂度为O(m+n)。
还有一点,在表示时间复杂度的时候,n和m通常用大写字母即O(M+N)。
这是一个非常快的排序算法。
桶排序从1956年就开始被使用,该算法的基本思想是由E.J.Issac和R.C.Singleton提出来的。
之前我说过,其实这并不是真正的桶排序算法,真正的桶排序算法要比这个更加复杂。
但是考虑到此处是算法讲解的第一篇,我想还是越简单易懂越好,真正的桶排序留在以后再聊吧。
需要说明一点的是:
我们目前学习的简化版桶排序算法,其本质上还不能算是一个真正意义上的排序算法。
为什么呢?
例如遇到下面这个例子就没辙了。
现在分别有5个人的名字和分数:
huhu5分、haha3分、xixi5分、hengheng2分和gaoshou8分。
请按照分数从高到低,输出他们的名字。
即应该输出gaoshou、huhu、xixi、haha、hengheng。
发现问题了没有?
如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。
最终输出的也仅仅是分数,但没有对人本身进行排序。
也就是说,我们现在并不知道排序后的分数原本对应着哪一个人!
这该怎么办呢?
不要着急,请看下节冒泡排序。
第2节邻居好说话冒泡排序简化版的桶排序不仅仅有上一节所遗留的问题,更要命的是:
它非常浪费空间!
例如需要排序数的范围是02100000000,那你则需要申请2100000001个变量,也就是说要写成inta2100000001。
因为我们需要用2100000001个“桶”来存储02100000000每一个数出现的次数。
即便只给你5个数进行排序(例如这5个数是1、1912345678、2100000000、18000000和912345678),你也仍然需要2100000001个“桶”,这真是太浪费空间了!
还有,如果现在需要排序的不再是整数而是一些小数,比如将5.56789、2.12、1.1、3.123、4.1234这五个数进行从小到大排序又该怎么办呢?
现在我们来学习另一种新的排序算法:
冒泡排序。
它可以很好地解决这两个问题。
冒泡排序的基本思想是:
每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。
例如我们需要将1235991876这5个数进行从大到小的排序。
既然是从大到小排序,也就是说越小的越靠后,你是不是觉得我在说废话,但是这句话很关键(_)。
首先比较第1位和第2位的大小,现在第1位是12,第2位是35。
发现12比35要小,啊哈!
算法8因为我们希望越小越靠后嘛,因此需要交换这两个数的位置。
交换之后这5个数的顺序是3512991876。
按照刚才的方法,继续比较第2位和第3位的大小,第2位是12,第3位是99。
12比99要小,因此需要交换这两个数的位置。
交换之后这5个数的顺序是3599121876。
根据刚才的规则,继续比较第3位和第4位的大小,如果第3位比第4位小,则交换位置。
交换之后这5个数的顺序是3599181276。
最后,比较第4位和第5位。
4次比较之后5个数的顺序是3599187612。
经过4次比较后我们发现最小的一个数已经就位(已经在最后一位,请注意12这个数的移动过程),是不是很神奇。
现在再来回忆一下刚才比较的过程。
每次都是比较相邻的两个数,如果后面的数比前面的数大,则交换这两个数的位置。
一直比较下去直到最后两个数比较完毕后,最小的数就在最后一个了。
就如同是一个气泡,一步一步往后“翻滚”,直到最后一位。
所以这个排序的方法有一个很好听的名字“冒泡排序”。
说到这里其实我们的排序只将5个数中最小的一个归位了。
每将一个数归位我们将其称第1章一大波数正在靠近排序9为“一趟”。
下面我们将继续重复刚才的过程,将剩下的4个数一一归位。
好,现在开始“第二趟”,目标是将第2小的数归位。
首先还是先比较第1位和第2位,如果第1位比第2位小,则交换位置。
交换之后这5个数的顺序是9935187612。
接下来你应该都会了,依次比较第2位和第3位,第3位和第4位。
注意此时已经不需要再比较第4位和第5位。
因为在第一趟结束后已经可以确定第5位上放的是最小的了。
第二趟结束之后这5个数的顺序是9935761812。
“第三趟”也是一样的。
第三趟之后这5个数的顺序是9976351812。
现在到了最后一趟“第四趟”。
有的同学又要问了,这不是已经排好了吗?
还要继续?
当然,这里纯属巧合,你若用别的数试一试可能就不是了。
你能找出这样的数据样例来吗?
请试一试。
“冒泡排序”的原理是:
每一趟只能确定将一个数归位。
即第一趟只能确定将末位上的数(即第5位)归位,第二趟只能将倒数第2位上的数(即第4位)归位,第三趟只能将倒数第3位上的数(即第3位)归位,而现在前面还有两个位置上的数没有归位,因此我们仍然需要进行“第四趟”。
“第四趟”只需要比较第1位和第2位的大小。
因为后面三个位置上的数归位了,现在第1位是99,第2位是76,无需交换。
这5个数的顺序不变仍然是9976351812。
到此排序完美结束了,5个数已经有4个数归位,那最后一个数也只能放在第1位了。
最后我们总结一下:
如果有n个数进行排序,只需将n1个数归位,也就是说要进行n-1趟操作。
而“每一趟”都需要从第1位开始进行相邻两个数的比较,将较小的一个数放在后面,比较完毕后向后挪一位继续比较下面两个相邻数的大小,重复此步骤,直到最后一个尚未归位的数,已经归位的数则无需再进行比较(已经归位的数你还比较个啥,浪费表情)。
这个算法是不是很强悍?
记得我每次拍集体照的时候就总是被别人换来换去的,当时特别烦。
不知道发明此算法的人当时的灵感是否来源于此。
啰里吧嗦地说了这么多,下面是代码。
建议先自己尝试去实现一下看看,再来看我是如何实现的。
#includeintmain()inta100,i,j,t,n;scanf(%d,&n);/输入一个数n,表示接下来有n个数for(i=1;i=n;i+)/循环读入n个数到数组a中scanf(%d,&ai);啊哈!
算法10/冒泡排序的核心部分for(i=1;i=n-1;i+)/n个数排序,只用进行n-1趟for(j=1;j=n-i;j+)/从第1位开始比较直到最后一个尚未归位的数,想一想为什么到n-i就可以了。
if(ajaj+1)/比较大小并交换t=aj;aj=aj+1;aj+1=t;for(i=1;i=n;i+)/输出结果printf(%d,ai);getchar();getchar();return0;可以输入以下数据进行验证。
1081005022156110009990运行结果是:
01681522501009991000将上面代码稍加修改,就可以解决第1节遗留的问题,如下。
#includestructstudentcharname21;charscore;/这里创建了一个结构体用来存储姓名和分数intmain()structstudenta100,t;inti,j,n;scanf(%d,&n);/输入一个数nfor(i=1;i=n;i+)/循环读入n个人名和分数scanf(%s%d,ai.name,&ai.score);第1章一大波数正在靠近排序11/按分数从高到低进行排序for(i=1;i=n-1;i+)for(j=1;j=n-i;j+)if(aj.scoreaj+1.score)/对分数进行比较t=aj;aj=aj+1;aj+1=t;for(i=1;i=n;i+)/输出人名printf(%sn,ai.name);getchar();getchar();return0;可以输入以下数据进行验证。
5huhu5haha3xixi5hengheng2gaoshou8运行结果是:
gaoshouhuhuxixihahahengheng冒泡排序的核心部分是双重嵌套循环。
不难看出冒泡排序的时间复杂度是O(N2)。
这是一个非常高的时间复杂度。
冒泡排序早在1956年就有人开始研究,之后有很多人都尝试过对冒泡排序进行改进,但结果却令人失望。
如DonaldE.Knuth(中文名为高德纳,1974年图灵奖获得者)所说:
“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外,似乎没有什么值得推荐的。
”你可能要问:
那还有没有更好的排序算法呢?
不要走开,请看下节快速排序。
啊哈!
算法12第3节最常用的排序快速排序上一节的冒泡排序可以说是我们学习的第一个真正的排序算法,并且解决了桶排序浪费空间的问题,但在算法的执行效率上却牺牲了很多,它的时间复杂度达到了O(N2)。
假如我们的计算机每秒钟可以运行10亿次,那么对1亿个数进行排序,桶排序只需要0.1秒,而冒泡排序则需要1千万秒,达到115天之久,是不是很吓人?
那有没有既不浪费空间又可以快一点的排序算法呢?
那就是“快速排序”啦!
光听这个名字是不是就觉得很高端呢?
假设我们现在对“61279345108”这10个数进行排序。
首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,这就是一个用来参照的数,待会儿你就知道它用来做啥了)。
为了方便,就让第一个数6作为基准数吧。
接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。
31254697108在初始状态下,数字6在序列的第1位。
我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。
现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。
想一想,你有办法可以做到这点吗?
给你一个提示吧。
请回忆一下冒泡排序是如何通过“交换”一步步让每个数归位的。
此时你也可以通过“交换”的方法来达到目的。
具体是如何一步步交换呢?
怎样交换才既方便又节省时间呢?
先别急着往下看,拿出笔来,在纸上画画看。
我高中时第一次学习冒泡排序算法的时候,就觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。
于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小地自恋一下(o)。
方法其实很简单:
分别从初始序列“61279345108”两端开始“探测”。
先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换它们。
这里可以用两个变量i和j,分别指向序列最左边和最右边。
我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。
刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。
让哨兵j指向序列的最右边(即j=10),指向数字8。
第1章一大波数正在靠近排序13首先哨兵j开始出动。
因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。
哨兵j一步一步地向左挪动(即j),直到找到一个小于6的数停下来。
接下来哨兵i再一步一步向右挪动(即i+),直到找到一个大于6的数停下来。
最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。
现在交换哨兵i和哨兵j所指向的元素的值。
交换之后的序列如下。
61259347108啊哈!
算法14到此,第一次交换结束。
接下来哨兵j继续向左挪动(再次友情提醒,每次必须是哨兵j先出发)。
他发现了4(比基准数6要小,满足要求)之后停了下来。
哨兵i也继续向右挪动,他发现了9(比基准数6要大,满足要求)之后停了下来。
此时再次进行交换,交换之后的序列如下。
61254397108第二次交换结束,“探测”继续。
哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。
哨兵i继续向右移动,糟啦!
此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。
说明此时“探测”结束。
我们将基准数6和3进行交换。
交换之后的序列如下。
31254697108第1章一大波数正在靠近排序15到此第一轮“探测”真正结束。
此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。
回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。
OK,解释完毕。
现在基准数6已经归位,它正好处在序列的第6位。
此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“31254”,右边的序列是啊哈!
算法16“97108”。
接下来还需要分别处理这两个序列,因为6左边和右边的序列目前都还是很混乱的。
不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。
现在先来处理6左边的序列吧。
左边的序列是“31254”。
请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。
好了开始动笔吧。
不用找纸了,别以为我不知道你的小伎俩,你肯定又没有动手尝试!
就准备继续往下看了吧。
这里我留了一个空白区域,赶快自己动手模拟一下吧!
如果你模拟得没有错,调整完毕之后的序列的顺序应该是:
21354OK,现在3已经归位。
接下来需要处理3左边的序列“21”和右边的序列“54”。
对序列“21”以2为基准数进行调整,处理完毕之后的序列为“12”,到此2已经归位。
序列“1”只有一个数,也不需要进行任何处理。
至此我们对序列“21”已全部处理完毕,得到的序列是“12”。
序列“54”的处理也仿照此方法,最后得到的序列如下。
12345697108对于序列“97108”也模拟刚才的过程,直到不可拆分出新的子序列为止。
最终将会得到这样的序列:
第1章一大波数正在靠近排序1712345678910到此,排序完全结束。
细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。
下面上个霸气的图来描述下整个算法的处理过程。
啊哈!
算法18快速排序之所以比较快,是因为相比冒泡排序,每次交换是跳跃式的。
每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。
这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换,交换的距离就大得多了。
因此总的比较和交换次数就少了,速度自然就提高了。
当然在最坏的情况下,仍可能是相邻的两个数进行了交换。
因此快速排序的最差时间复杂度和冒泡排序是一样的,都是O(N2),它的平均时间复杂度为O(NlogN)。
其实快速排序是基于一种叫做“二分”的思想。
我们后面还会遇到“二分”思想,到时候再聊。
先上代码,如下。
#includeinta101,n;/定义全局变量,这两个变量需要在子函数中使用voidquicksort(intleft,intright)inti,j,t,temp;if(leftright)return;temp=aleft;/temp中存的就是基准数i=left;j=right;while(i!
=j)/顺序很重要,要先从右往左找while(aj=temp&ij)j-;/再从左往右找while(ai=temp&ij)i+;/交换两个数在数组中的位置if(ij)/当哨兵i和哨兵j没有相遇时t=ai;ai=aj;aj=t;/最终将基准数归位第1章一大波数正在靠近排序19aleft=ai;ai=temp;quicksort(left,i-1);/继续处理左边的,这里是一个递归的过程quicksort(i+1,right);/继续处理右边的,这里是一个递归的过程intmain()inti,j,t;/读入数据scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);quicksort(1,n);/快速排序调用/输出排序后的结果for(i=1;i=n;i+)printf(%d,ai);getchar();getchar();return0;可以输入以下数据进行验证。
1061279345108运行结果是:
12345678910下面是程序执行过程中数组a的变化过程,带下划线的数表示的是已归位的基准数。
6127934510831254697108213546971081235469710812354697108啊哈!
算法20123456971081234569710812345687910123456789101234567891012345678910快速排序由C.A.R.Hoare(东尼霍尔,CharlesAntonyRichardHoare)在1960年提出,之后又有许多人做了进一步的优化。
如果你对快速排序感兴趣,可以去看看东尼霍尔1962年在C
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 啊哈 算法