第6章 排序与选择1

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 排序与选择,排序定义,将一个数据元素（或记录）的任意序列，重新排列成一个按关键码有序的序列叫,排序基本操作,比较两个,关键字,大小,将,记录,从一个位置移动到另一个位置,基本概念,1,排序分类,按待排序记录所在位置,内部排序,：,在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；,外部排序：,在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。,2,稳定排序,和非稳定排序,稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，反之，就是非稳定的排序。,例如：,一组数排序前是,a1,a2,a3,a4,a5,，其中,a2=a4,，,经过某种排序后为,a1,a2,a4,a3,a5,则我们说这种排序是稳定的，因为,a2,排序前在,a4,的前面，排序后它还是在,a4,的前面。,假如变成,a1,a4,a2,a3,a5,就不是稳定的了。,3,插入排序,基本思想：,（1）初始状态：整个数组r被划分成两个部分：（）,初始时,有序区,仅含数组的第1个元素 r1（单独一个元素总是有序的），,无序区,为 r2 到 rn,-1,（假定数组共有n,-1,个元素）。排序完成后，我们称其为,终态,，此时有序区应为整个数组 r，无序区为空。,（2）基本操作：从无序区中取一元素（通常取第一个元素），按其大小插入到有序区适当位置，使有序区仍然保持有序性。示意如下：,插入前：（,1 2 8 9,）,3,7 6 5,插入后：（,1 2,3,8 9,）,7 6 5,（3）插入排序的整个过程从初始状态开始，不断重复第2步,骤的基本操作，直至到达终态。,有序区,无序区,4,直接插入排序,直接插入排序是最简单的排序方法之一，它的插入定位是通过将插入元素与有序区的各记录自右向左依次比较其,大小,来确定的。,例1 设待排序的元素共7个，分别为：8，3，2，5，9，,3,，6。直接插入排序过程如图6-1所示。,8,3,2,5,9,3,6,r,0,1,2,3,5,4,6,7,8,9,10,下标,数组名,5,初始元素序列：,（8）3 2 5 9,3,6,（3 8）2 5 9,3,6,（2 3 8）5 9,3,6,（2 3 5 8）9,3,6,（2 3 5 8 9）,3,6,（2 3,3,5,8 9）6,（2 3,3,5,6 8 9）,i=2:,（3）,i=3:,（2）,i=4:,（5）,i=5:,（9）,i=6:,（,3,）,i=7:,（,3,）,可见，直接插入排序是稳定的排序方法,6,在直接插入排序中将第i个元素 ri插出到有序区中可通过如下步骤实现：,（1）定位初始化：,r0=ri;j=i-1;,r0是监视哨，存放当前待插入元素，,j为待定的插入位置，初值为：i-1；,（2）定位,while(r0 rj),rj+1=rj;j-;,退出循环时，rj是第一个小于等于 r0的元素，j+1指出插入位置，且 rj+1位置元素已被移走。,（3）插入,rj+1=r0;,7,void,InsertSort,(,int,r,int n),int,i,j;,for(i=2;i=n;i+),r,0=,r,i;,j=i-1;,while(,r,018,满足要求不交换,（）7 53 36 48,36,60 18 41,第一次比较结果：,（）7 53 36 48,36,18 60 41,第二次比较结果：,（）7 53 36 48 18,36,60 41,第三次比较结果：,（）7 53 36 18 48,36,60 41,第四次比较结果：,（）7 53 18 36 48,36,60 41,第五次比较结果：,（）7 18 53 36 48,36,60 41,第六次比较结果：,一趟冒泡排序过程,12,例2 设初始元素序列为 53，36，48，36，60，7，18，41，用冒泡排序方法进行排序，写出每趟的结果。,（）53 36 48,36,60 7 18 41,（7 18 36,36,41 48 53）60,第七趟比较结果：,初始系列：,（7）53 36 48,36,60 18 41,第一趟比较结果：,（7 18）53 36 48,36,60 41,第二趟比较结果：,（7 18 36）53,36,48 41 60,第三趟比较结果：,（7 18 36,36,）53 41 48 60,第四趟比较结果：,（7 18 36,36,41）53 48 60,第五趟比较结果：,（7 18 36,36,41 48）53 60,第六趟比较结果：,（7 18 36,36,41 48 53 60）,13,从上图的冒泡全过程可知，第i趟冒泡，无序区共有n-i+1个元素，经过n-i次相邻两元素的比较及交换，无序区中最小元素就,“,飘浮,”,到有序区，每一趟冒泡后，无序区减少一个元素，有序区增加一个元素，所以最多只需进行n-1趟冒泡，排序就能完成。,依次对无序区相邻元素作比较和交换：,for(j=n;ji ;j-),if(rjrj-1),将rj和rj-1 交换,14,void,Bu,bb,leSort,(,int,r,int n,),int,i,j;,for(i=1;i,i;j,-,),if(,r,j,r,j,-,1),r,0=,r,j;,r,j=,r,j,-,1;,r,j,-,1=,r,0;,/*n,个元素比较,n-1,趟*,/,/*,第,i,趟比较需要比较,n-i,次*,/,/*,相邻两个数与要求的顺序相逆，则交换*,/,冒泡排序算法：,15,改进的冒泡排序算法,在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。,解决方案，可在程序中设置一个标志变量flag,用来标记每趟冒泡是否发生元素交换，若无交换则排序结束。,16,void,Bu,bb,leSort,(,int,r,int n,),int,i,j,flag,;,for(i=1;i,i;j,-,),if(,r,j,r,j,-,1,),r,0=,r,j;,r,j=,r,j,-,1;,r,j,-,1=,r,0;,flag=1;,if(!flag),break;,改进的冒泡排序算法：,17,算法评价,时间复杂度,最好情况（正序）,比较次数：,n-1,移动次数：0,最坏情况（逆序）,比较次数：,移动次数：,空间复杂度：,S(n)=O(1),T(n)=O(n),冒泡排序算法是稳定的,18,选择,排序,基本思想是：,（,1）初始状态：,整个数组 r 被划分成两个部分,即有序区和无序区。初始有序区为空。（）,（2）基本操作：,从无序区中选择最小元素，将其添加到有序区尾部。,（3）排序过程,：从初始（有序区为空）开始，不断重复步骤2操作，直至到达终态（无序区为空）。,常见的选择排序方法有两种：,直接选择排序,和,堆排序,。本节介绍直接选择排序，堆排序将在树的应用中介绍,19,直接选择排序,基本操作：,1、在无序区中，通过自左向右依次比较找出最小元素；。,2、将最小元素添加到有序区尾部（只要把最小元素与无序区的第一个元素交换即可）。,例3 设初始元素序列为 53，36，48，36，60，7，18，41，直接选择排序过程如下：,20,（）53 36 48,36,60 7 18 41,初始系列：,（7 18,36,36 41 48 53 60）,最后结果：,（7）36 48,36,60 53 18 41,第一次排序结果：,（7 18）48,36,60 53 36 41,第二次排序结果：,（7 18,36,）48 60 53 36 41,第三次排序结果：,（7 18,36,36）60 53 48 41,第四次排序结果：,（7 18,36,36 41）53 48 60,第五次排序结果：,（7 18,36,36 41 48）53 60,第六次排序结果：,（7 18,36,36 41 48 53）60,第七次排序结果：,21,找当前无序区中的最小元素并与无序区第一个元素交换，实现如下：,（1）初始化：min=i;,min中保存当前无序区查看过的最小元素下标。,（2）与无序区其他元素自左向右依次比较找最小元素,for(j=i+1;j=n;j+),if(rjrmin),min=j;,退出循环时，min中存放无序区中最小元素的下标。（3）最小元素与无序区的第一个元素交换：,if(min!=i),r0=rmin;rmin=ri;ri=r0;,22,void,SelectSort,(,int,r,int n,),int,i,j,min,;,for(i=1;i=n-1;i+),min=i;,for(j=i+1;j=n;j+),if(,r,j,r,min,),min,=j;,if(,min!=i,),r,0=,r,min,;,r,min,=,r,i;,r,i=,r,0;,直接选择排序算法：,/*,作,n-1,趟选取*,/,/*在i开始的,所有元素,中选最小元素*/,/*,min,中存放最小值元素的下标*/,/*,最小值元素与第,i,个元素交换*,/,23,算法评价,时间复杂度,记录移动次数,最好情况：,0,最坏情况：3(,n-1),比较次数,：,空间复杂度：,S(n)=O(1),T(n)=O(n),分析可得，直接选择排序方法为,不稳定,排序方法,24,