《《排序算法设计》教学课件》由会员分享,可在线阅读,更多相关《《排序算法设计》教学课件(12页珍藏版)》请在金锄头文库上搜索。
1、排序算法设计,(选择排序与插入排序),排序,数据排序(sorting) 是最重要的计算应用之一。例如查字典,字典中的词条是按序存放的,我们才能按字母顺序找到要查的字。又如图书馆的藏书也是按书的编号有序排列的。在计算机上数据库里的资料也是有序排列的。,排序,排序(sorting)是数据处理中经常使用的一种重要运算。其功能是将数据元素的无序序列调整为一个有序序列。数据元素中一般有多个数据项,排序可选择其中一个可排序的数据项(可进行比较运算)作为依据,称为排序关键字。,常用的排序法,比如我们对高考考生的统计表进行排序,可根据考生的准考证号,这样的关键字可以保证排序结果的唯一性,称主关键字。但为了便于
2、录取,我们也可以按高考总分排序,只可称关键字,这样同一分数的人很多,这些人的排名可再取一个次关键字如数学或语文分来排序,以减少重复排名的随意性。从小到大排序称升序,反之为降序。 最常见的三类是选择排序、插入排序和交换排序。,基本思想是: 每一趟从待排序的记录中选出关键字最小的元素,顺序放在已排好序的子序列的后面,直到全部记录排序完成。直接选择排序(Straight Selection Sort)是最简单的。此方法的最大优点是易读。缺点是做过的工作和序列的部分有序性利用不上,效率低。选择排序中也有可能利用到以前的工作的方法,如堆排列(Heap Sort),选择排序,493865977613274
3、9 1338659776492749 1327659776493849 1327389776496549 1327384976976549 1327384949976576 1327384949659776 1327384949657697 图6.7直接选择排序的过程,选择排序,【例】直接选择排序,void SelectSort(int slist,int last) int i,j,k,temp; for(i=0;ilast;i+) k=i; temp=slisti; for(j=i;j=last;j+) if(slistjtemp) k=j; temp=slistj; if(k!=i) t
4、emp=slisti; slisti=slistk; slistk=temp; ,(1)直接插入排序的思想是:(以升序为例)当插入第i(i=1)个元素sli时,前面的元素sl0,sl1,sli-1已经排好序,我们将sli的关键字与sli-1, sli-2,的关键码顺序进行比较,找到第一个比它小的,则sli插到该元素之后。,插入排序,直接插入排序算法中用了一个临时变量temp,要插入的元素放到temp中,这样插入前各元素后移时允许将该元素冲掉。,插入排序,【例】升序直接插入排序算法,void InsertSort(int slist,int last ) int i,j,temp; for (i=1;i0 ,(2)对半插入排序(Binary Insert Sort)是用对半查找的思想取代顺序查找。对半插入排序要快于插入排序。,插入排序,【例】升序对半插入排序算法,升序对半插入排序算法。当关键字相同时,插入排序原来在前的仍在前,称稳定排序。 void BinaryInsertSort(int slist,int last) int low,high,mid,i,j, temp; for (i=1;i=low;j-) slistj+1=slistj; slistlow=temp; ,