《排序算法设计》教学课件

《《排序算法设计》教学课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法设计（选择排序与插入排序）排序数据排序（sorting）是最重要的计算应用之一。例如查字典，字典中的词条是按序存放的，我们才能按字母顺序找到要查的字。又如图书馆的藏书也是按书的编号有序排列的。在计算机上数据库里的资料也是有序排列的。排序排序（sorting）是数据处理中经常使用的一种重要运算。其功能是将数据元素的无序序列调整为一个有序序列。数据元素中一般有多个数据项，排序可选择其中一个可排序的数据项（可进行比较运算）作为依据，称为排序关键字。常用的排序法比如我们对高考考生的统计表进行排序，可根据考生的准考证号，这样的关键字可以保证排序结果的唯一性，称主关键字。但为了便于录取，我们也可

2、以按高考总分排序，只可称关键字,这样同一分数的人很多，这些人的排名可再取一个次关键字如数学或语文分来排序，以减少重复排名的随意性。从小到大排序称升序，反之为降序。最常见的三类是选择排序、插入排序和交换排序。基本思想是：每一趟从待排序的记录中选出关键字最小的元素，顺序放在已排好序的子序列的后面，直到全部记录排序完成。直接选择排序（StraightSelectionSort）是最简单的。此方法的最大优点是易读。缺点是做过的工作和序列的部分有序性利用不上，效率低。选择排序中也有可能利用到以前的工作的方法，如堆排列（HeapSort）选择排序[4938659776132749’]13[3865977

3、6492749’]1327[659776493849’]132738[9776496549’]13273849[76976549’]1327384949’[976576]1327384949’65[9776]1327384949’657697图6.7直接选择排序的过程选择排序【例】直接选择排序voidSelectSort(intslist[],intlast){inti,j,k,temp;for(i=0;i

4、{temp=slist[i];slist[i]=slist[k];slist[k]=temp;}}}(1)直接插入排序的思想是:(以升序为例)当插入第i(i>=1)个元素sl[i]时,前面的元素sl[0],sl[1],…,sl[i-1]已经排好序,我们将sl[i]的关键字与sl[i-1],sl[i-2],…,的关键码顺序进行比较,找到第一个比它小的,则sl[i]插到该元素之后。插入排序i0123456temp初始序列[8]67945261[68]7945272[678]945293[6789]45244[46789]5255[456789]226[2456789]直接插入排序算法中用了一个临

5、时变量temp，要插入的元素放到temp中，这样插入前各元素后移时允许将该元素冲掉。插入排序【例】升序直接插入排序算法voidInsertSort(intslist[],intlast){inti,j,temp;for(i=1;i<=last;i++){temp=slist[i];j=i;while(j>0&&temp

6、序对半插入排序算法。当关键字相同时，插入排序原来在前的仍在前，称稳定排序。voidBinaryInsertSort(intslist[],intlast){intlow,high,mid,i,j,temp;for(i=1;i<=last;i++){temp=slist[i];low=0;high=i-1;while(low<=high){//请注意与对半查找的mid=(low+high)/2;//不同之处if(temp=low;j--)slist[j+1]=slist[j];sli

7、st[low]=temp;}}