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

排序算法设计 （选择排序与插入排序） 排序 数据排序（sorting） 是最重要的计算应用之一。例如查字典，字典中的词条是按序存放的，我们才能按字母顺序找到要查的字。又如图书馆的藏书也是按书的编号有序排列的。在计算机上数据库里的资料也是有序排列的。 排序 排序（sorting）是数据处理中经常使用的一种重要运算。其功能是将数据元素的无序序列调整为一个有序序列。数据元素中一般有多个数据项，排序可选择其中一个可排序的数据项（可进行比较运算）作为依据，称为排序关键字。 常用的排序法 比如我们对高考考生的统计表进行排序，可根据考生的准考证号，这样的关键字可以保证排序结果的唯一性，称主关键字。但为了便于录取，我们也可以按高考总分排序，只可称关键字,这样同一分数的人很多，这些人的排名可再取一个次关键字如数学或语文分来排序，以减少重复排名的随意性。从小到大排序称升序，反之为降序。 最常见的三类是选择排序、插入排序和交换排序。 基本思想是： 每一趟从待排序的记录中选出关键字最小的元素，顺序放在已排好序的子序列的后面，直到全部记录排序完成。直接选择排序（Straight Selection Sort）是最简单的。此方法的最大优点是易读。缺点是做过的工作和序列的部分有序性利用不上，效率低。选择排序中也有可能利用到以前的工作的方法，如堆排列（Heap Sort） 选择排序 [49 38 65 97 76 13 27 49’] ?13 [38 65 97 76 49 27 49’] ?13 27 [65 97 76 49 38 49’] ?13 27 38 [97 76 49 65 49’] ?13 27 38 49 [76 97 65 49’] ?13 27 38 49 49’ [97 65 76] ?13 27 38 49 49’ 65 [97 76] ?13 27 38 49 49’ 65 76 97 图6.7直接选择排序的过程 选择排序 【例】直接选择排序 void SelectSort(int slist[],int last){ int i,j,k,temp; for(i=0;ilast;i++){ k=i; temp=slist[i]; for(j=i;j=last;j++) if(slist[j]temp){ k=j; temp=slist[j]; } if(k!=i){ 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]插到该元素之后。 插入排序 i 0 1 2 3 4 5 6 temp 初始序列 [8] 6 7 9 4 5 2 6 1 [6 8] 7 9 4 5 2 7 2 [6 7 8] 9 4 5 2 9 3 [6 7 8 9] 4 5 2 4 4 [4 6 7 8 9] 5 2 5 5 [4 5 6 7 8 9] 2 2 6 [2 4 5 6 7 8 9] 直接插入排序算法中用了一个临时变量temp，要插入的元素放到temp中，这样插入前各元素后移时允许将该元素冲掉。 插入排序 【例】升序直接插入排序算法 void InsertSort(int slist[],int last ){ int i,j,temp; for (i=1;i=last;i++){ temp=slist[i]; j=i; while (j0tempslist[j-1]){ slist[j]=slist[j-1]; j--; //查找与移动同时做 } slist[j]=temp; } } (2)对半插入排序（Binary Insert Sort）是用对半查找的思想取代顺序查找。对半插入排序要快于插入排序。 插入排序 【例】升序对半插入排序算法 升序对半插入排序算法。当关键字相同时，插入排序原来在前的仍在前，称稳定排序。 void BinaryInsertSort(int slist[],int last){ int low,high,mid,i,j, temp; for (i=1;i=last;i++){ temp=slist[i]; low=0; high=i-1; while (low=high){ //请