《《排序算法设计》教学课件》由会员分享，可在线阅读，更多相关《《排序算法设计》教学课件（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; ,
