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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,排序算法设计,（选择排序与插入排序）,排序,数据排序（,sorting,）,是最重要的计算应用之一。例如查字典，字典中的词条是按序存放的，我们才能按字母顺序找到要查的字。又如图书馆的藏书也是按书的编号有序排列的。在计算机上数据库里的资料也是有序排列的。,排序,排序（,sorting,）,是数据处理中经常使用的一种重要运算。其功能是将数据元素的无序序列调整为一个有序序列。数据元素中一般有多个数据项，排序可选择其中一个可排序的数据项（可进行比较运算）作为依据，称为,排序关键字,。,常用的排序法,比如我们对高考考生的统计表进行排序，可根据考生的准考证号，这样的关键字可以,保证排序结果的唯一性，称主关键字,。但为了便于录取，我们也可以按高考总分排序，只可称,关键字,这样同一分数的人很多，这些人的排名可再取一个,次,关键字,如数学或语文分来排序，以减少重复排名的随意性。从小到大排序称,升序,，反之为,降序,。,最常见的三类是,选择排序、插入排序,和,交换排序,。,基本思想是：,每一趟从待排序的记录中选出关键字最小的元素，顺序放在已排好序的子序列的后面，直到全部记录排序完成。,直接选择排序,（,Straight Selection Sort,）是最简单的。此方法的最大优点是,易读,。缺点是做过的工作和序列的部分有序性利用不上，,效率低,。选择排序中也有可能利用到以前的工作的方法，如,堆排列（,Heap Sort,）,选择排序,49,38659776,13,2749,13,38,65977649,27,49,1327,65,977649,38,49,132738,97,76,49,6549,13273849,76,9765,49,1327384949,97,65,76,132738494965,97,76,1327384949657697,图,6.7,直接选择排序的过程,选择排序,【,例,】,直接选择排序,void SelectSort(int slist,int last),int i,j,ktemp;,for(i=0;ilast;i+),k=i;,temp=slisti;,for(j=i;j=last;j+)if(slistj=1),个元素,sli,时,前面的元素,sl0,sl1,sli-1,已经排好序,我们将,sli,的关键字与,sli-1,sli-2,的关键码顺序进行比较,找到第一个比它小的,则,sli,插到该元素之后。,插入排序,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,78,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;i0&tempslistj-1),slistj=slistj-1;,j-;/,查找与移动同时做,slistj=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=slisti;,low=0;,high=i-1;,while(low=high)/,请注意与对半查找的,mid=(low+high)/2;/,不同之处,if(temp=low;j-)slistj+1=slistj;,slistlow=temp;,