软件_查找和排序_排序.ppt

1、第二节 排序,一、基本概念 二、选择排序 三、插入排序 四、交换排序 五、归并排序,一 排序基本概念,1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。 2、排序过程的组成步骤： 首先比较两个关键字的大小； 然后将记录从一个位置移动到另一个位置。,稳定的排序,当待排序记录的关键字均不相同时，则排序结果是唯一的，否则排序的结果不一定唯一。 如果在待排序文件中存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的，否则排序算法是不稳定的。,评价排序算法好坏的标准,执行时间 所需的辅助空间 算法的复杂程度,排序方

2、法,插入排序,选择排序,交换排序,归并排序,线性插入排序,对半插入排序,简单选择排序,堆排序,冒泡排序,快速排序,选择排序简单选择排序,每一趟从待排序的记录中选出关键字最小的记录，顺序存放已排好的子文件的最后(最前)，直到全部记录排序完毕。,简单选择排序的算法如下： void SelectSort( RedType L ,int n) int i,j,k,t; for (i=1,i=n;+i） /选择第i小的元素，并交换到位 j=i； for(k=i+1;k=n;+k) if ( Lk.keyLj.key) j=k; /Lj 中存放的是第i小的元素 if(j!=i) t=Li; /交换 Li=

3、Lj; Lj=t ； ,1 3 4 20 27 12 5,i,j指向最小,简单选择排序特点,容易理解 其时间复杂度为O(n2) 算法是不稳定的,选择排序堆排序,堆,堆就是一个关键字序列：并且这n个关键字的序列K1,K2.Kn要满足以下性质(堆性质)，就是: KiK2i且KiK2i+1 或者 KiK2i且KiK2i+1,1 2 3 4 5 6 7 8,堆,当把这个序列存入一个向量并把它看作是一棵完全二叉树的存储结构时，堆就是这样一棵二叉树：任一非叶结点的关键字均不小于(或不大于)其左右孩子结点的关键字。,1 2 3 4 5 6 7 8,最大值,(a):堆顶元素取最大值 大根堆,(b):堆顶元素取

4、最小值 小根堆,堆排序基本思想,因为堆顶是最大的数，所以当把一个关键字序列排成一个大根堆时，就很容易地找到最大的数，它就在序列的第一个位置上 然后把这个最大的数与最后一个记录交换，这时，最后一个记录就是关键字最大的记录了。 对于剩下的关键字序列，我们仍然把它排成一个大根堆，然后再把第一个记录(当前堆中的堆顶)与当前堆的最后一个记录交换。这时，在整个序列后面就有了两个有序的关键字(从小到大)。 重复这样的过程，就可以把有序区不断扩大直到全部关键字都进入有序区。直到排序完成。,堆的构造,无序序列r1：n构成的完全二叉树， 从它最后一个非叶子结点（第n/2个元素）开始直到根结点为止，逐步进行调整即可

5、将此完全二叉树构成堆。 调整：与其左右子树根结点值比较，取其中大的进行交换。,堆的构造例,46 55 13 42 94 05 17 70,1 2 3 4 5 6 7 8,堆的构造例,46 55 13 42 94 05 17 70,1 2 3 4 5 6 7 8,对调,对调,1 2 3 4 5 6 7 8,对调,对调,13,13,堆的构造例,46 55 13 42 94 05 17 70,1 2 3 4 5 6 7 8,对调,55,55,对调,1 2 3 4 5 6 7 8,对调,46,46,对调,堆的构造例,46 55 13 42 94 05 17 70,1 2 3 4 5 6 7 8,对调,

6、46,46,对调,1 2 3 4 5 6 7 8,成堆!,堆的构造例,46,55,13,42,70,94,05,17,初始无序结点,从42开始调整,46,55,13,70,42,94,05,17,将以13为根的子树调整成堆,46,55,17,70,42,94,05,13,将以55为根的子树调整成堆,46,94,17,70,42,55,05,13,将以46为根的子树调整成堆,94,70,17,46,42,55,05,13,成堆,46 55 13 42 94 05 17 70,调整成堆算法,void SIFT(int r,int i,int n) /调整r1:n中结点ri,使成为一个堆 int j

7、; int T; T=ri; j=2*i; /j为i结点的左孩子序号 while(jn) if(jn) /退出while ,i,j,T,堆排序,由给定的无序序列构造堆 将堆顶元素与堆中最后一个元素交换 将最后一个元素从堆中“删除” 将余下的元素构成完全二叉树重新调整成堆 反复进行，直到堆空,堆排序过程示例,第一趟排序结果,第二趟排序结果,第三趟排序结果,堆排序过程示例(续1),第四趟排序结果,第五趟排序结果,第六趟排序结果,堆排序过程示例(续2),堆排序结果,第七趟排序结果,堆排序过程,第一趟结果:,第二趟结果:,第三趟结果:,第四趟结果:,第五趟结果:,第六趟结果:,第七趟结果:,堆排序算法

8、,void heapsort(int r,int n) /堆排序 int t; for(int i=n/2-1;i=0;i-) /将r调整成堆 SIFT(r,i,n); for(i=n-1;i=0;i-) t=r0; r0=ri; ri=t; SIFT(r,0,i-1); ,i,0,n-1,堆排序算法,void heapsort(int r,int n) /堆排序 int t; for(int i=n/2-1;i=0;i-) /将r调整成堆 SIFT(r,i,n); for(i=n-1;i0;i-) t=r0; r0=ri; ri=t; SIFT(r,0,i-1); ,i,0,n-1,课堂练习

9、（填空题）,假定有关键字序列： 49 38 65 97 76 13 27 ,对其进行堆排序的第一趟结果为,27 76 65 38 49 13 97,算法分析,这个算法主要是建立初始堆和重建堆的过程。它的时间复杂度最坏情况下为O(nlgn),而平均性能接近于最坏性能。 堆排序不适宜于记录数较少的文件。堆排序是不稳定的。,三、插入排序,每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 线性插入排序 对半插入排序,插入排序 线性插入、对半插入,1、线性插入排序: 基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已

10、排好序的数组的适当位置上。,该算法适合于n 较小的情况，,1、线性插入排序: 基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上,待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 线性插入排序示例,对于有n个数据元素的待排序列，插入操作要进行n-1次,哨兵(监视哨),哨兵(监视哨)有两个作用：

11、作为临时变量存放Ri(当前要进行比较的关键字)的副本， 在查找循环中用来监视下标变量j是否越界。,R0 R1 R2 R3 R4 R5 6 2061573 15 6201573 7 6152073 36715203 3671520,void insertsort(elemtype r,int n) int i,j; for(i=1;in-1;i+) r0=ri+1; / r0: 监视哨 j=i; while(r0 .key rj .key) rj+1=rj;/记录后移 j-; rj+1= r0; / 插入 ,插入算法如下： 方法:Ki与Ki-1,K i-2,K1依次比较,直到找到应插入的位置。,

12、P105 例,线性插入排序算法分析,时间复杂度在不同输入实例时是不同的， 最好情况是文件初态为正序，此时算法的时间复杂度为O(n), 最坏情况是文件为反序，时间复杂度为O(n2), 算法的平均时间复杂度也是O(n2). 该算法的空间复杂度为O(1) 。 线性插入排序是稳定的。也就是相同关键字的记录的相对位置在排序后不发生改变。,插入排序对半插入排序,在有序区中进行对分查找，以确定插入的位置， 移动记录腾出空间，将相应关键字的记录插入,(highlow ，查找结束，插入位置为low 或high+1 ),( 4236 ),( 4253 ),void BinsertSort(RedType L ,i

13、nt n) int i,low,high,mid; for(i=2; i=high+1; j ) Lj+1=Lj; / 记录后移 Lhigh+1=L0; /插入 /* for*/ ,对半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与线性插入排序相同。,/折半后的位置,对半插入排序算法分析,平均时间复杂度也是O(n2). 空间复杂度为O(1),四、交换排序,两两比较待排序记录的关键字，发现两个记录次序相反时即进行交换，直到没有反序的记录为止。 冒泡排序 快速排序,思想：小的浮起，大的沉底。从左端开始比较。 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换

14、，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上； 依次类推，则完成排序。,交换排序冒泡排序,冒泡排序示例,初始值 46 55 13 42 94 5 17 70,第一趟 46 13 42 55 5 17 70 94,46 13 55 42 94 5 17 70,46 13 42 55 94 5 17 70,46 13 42 55 5 94 17 70,46 13 42 55 5 17 94 70,冒泡排序算法,void Bubblesort(int r ,int n) int flag=1; /当flag为0,则停止排序

15、 for (int i=n;i=2;i-) /i表示趟数,最多n-1趟 flag=0; /开始时元素未交换 for(int j=1;jrj+1) int t=rj; rj=rj+1; rj+1=t; flag=1; / 交换 if(flag=0) return; ,冒泡排序算法分析,正序：时间复杂度为O(n) 逆序：时间复杂度为O(n2) 平均时间复杂度也是O(n2) 空间复杂度为O(1) 冒泡排序算法是稳定的 。 适合于数据较少的情况。 排序n个记录的文件最多需要n-1趟冒泡排序。,通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列

16、有序。,快速排序（算法思想）,(对冒泡排序的改进）,快速排序（算法描述）,基准值通常取第一个记录的值。,(1)附设两个指针i和j ，初值分别指向第一个记录和最后一个记录，设基准值为 key; (2)从 j所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换; (3)从i 所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换 (4)重复(2)、(3)两步直至i = j为止。,快速排序一趟算法,初始值 46 55 13 42 94 5 17 70,17 55 13 42 94 5 17 70,17 55 13 42 94 5 55 70,基准X=46,17 5 13 42 94 5

17、 55 70,17 5 13 42 94 94 55 70,17 5 13 42 94 94 55 70,46,快速排序一趟算法,初始值 46 55 13 42 94 5 17 70,基准X=46,17,55,5,94,46,17 5 13 42 46 94 55 70,快速排序例,初始值 46 55 13 42 94 5 17 70,第一趟 13 5 17 42 46 94 55 70,第二层 5 13 17 42 46 70 55 94,第三层 5 13 17 42 46 55 70 94,第四层 5 13 17 42 46 55 70 94,快速排序算法,void quicksort(i

18、nt r ,int left,int right) int i=left,j=right; int x=ri; while (ix) /递归调用右子区间 ,例,快速排序算法分析,对于快速排序，其时间主要耗费在划分操作上，最坏的情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录。这时快速排序必须作n-1次划分，时间复杂度为O(n2).这种情况就是文件已按递增序或递减序排列。在最好的情况下，每次划分所选的基准都是当前无序区的中值记录，此时的时间复杂度为O(nlog2n) 。由于出现最坏情况的输入实例概率极小，因此它的平均性能接近于它的最好时间复杂度，也是O(nlog2n). 快速排

19、序算法是非稳定的。,课堂练习,假定有关键字序列： 52, 49, 80, 36, 14, 58, 61, 97, 23 ,75 ， 对其进行快速排序的第一趟结果为:,23, 49, 14, 36, (52) 58, 61, 97, 80, 75,52, 49, 80, 36, 14, 58, 61, 97, 23, 75,(52),23, 49, 14, 36,58, 61, 97, 80, 75,14, (23), 49, 36,(58), 61, 97, 80, 75,36, ( 49),(61), 97, 80, 75,(36),75, 80, (97),(75), 80,(80),14

20、, 23, 36, 49, 52, 58, 61, 75, 80, 97,(14),课堂练习(续）,归并排序又称为表排序，其含义是将两个有序序列合并成为一个有序序列。1、基本思想 设待排序序列有n个记录，开始将其看作是n个长度为1 的有序子文件，然后进行归并，将相邻的有序子文件两两合并，得到n/2个长度为2或1的有序子文件(如果n为奇数，则最后一个有序子文件的长度为1)，再两两归并得到n/4个有序子文件，以此类推，直至得到长为n的有序文件。该有序序列就是原始序列经归并排序后的有序序列。在排序过程中，子序列总是两两归并，所以归并排序又被称为二路归并排序。,五、归并排序,例如对序列16，31，9，

21、15，87，76，13，24，43进行二路归并排序过程为：,2、二路归并的算法 在编写程序实现时，实际上是把两个长度为k的有序序列连接合并成一个长度为2k的有序序列。可利用三个指针分别指向三个序列的第一个元素，将两个序列的第一个元素进行比较，取出关键字较小者作为结果序列的第一个元素，将较小者所在序列及结果序列的指针后移，继续比较和加入。最后当两个序列之一的所有元素都取完时，再将另一序列的剩余元素顺序复制到结果序列中，完成归并。,i,j,k,void merge(int r,int r1,int low,int mid,int high) /rlow到rmid与rmid+1到rhigh是两个有序

22、子文件 /本算法将其归并成一个有序子文件从r1low到r1high int i=low; int j=mid+1; int k=low; while (i=mid) /复制第二个文件剩余记录 ,一次归并,i,j,k,一趟归并过程中的三种情况,n,1,length,i,i,i+2*length=n,n,1,length,i,i,i+lengthn,剩下两个子文件，其中一个长度小于length,归并后退出,n,1,length,i,i,只剩下一个子文件，将最后一个子文件复制到r1中，完成后退出,待归并记录至少有两个长度为length的子文件，归并完成后 i+2*length,/对r进行一趟归并，结

23、果放在r1中 void mergepass(int r,int r1,int n,int length) / length是本趟归并的有序子文件的长度 int i=1,j; /指向第一对子文件起始点 while (i+2*length=n)/待归并记录至少有两个长度为length的子文件 merge(r,r1,i,i+length-1,i+2*length-1); i=i+2*length; /指向下一对子文件起始点 if (i+lengthn)/剩下两个子文件，其中一个长度小于length merge(r,r1,i,i+length-1,n-1); else /子文件个数为奇数，将最后一个子

24、文件复制到r1中 for (j=i;jn;j+) r1j=rj; ,merge,void mergesort( int r,int r1,int n ) /归并排序 int length=1; while (lengthn) mergepass(r,r1,n,length) ; / 一趟归并，结果在r1中 length=2*length; /区间扩大一倍 mergepass(r1,r,n,length) ; / 再次归并，结果在r中 length=2*length; ,3、二路归并的算法分析 第i趟排序后，有序子文件长度为2i，具有那个记录的文件排序，必须做log2n趟归并，每趟所花时间为O(

25、n)，所以二路归并排序的时间复杂度为O(nlog2n) 所需的空间为O(n)。,回想一下,1.选择排序 基本思想：每趟选一排在（前）后。 简单选择排序： 每一趟从待排序的记录中选出关键字最小的记录，顺序存放已排好的子文件的最后(最前)，直到全部记录排序完毕。 堆排序：堆的定义、堆的构造、堆排序基本思想 由给定的无序序列构造堆 将堆顶元素与堆中最后一个元素交换， 将最后一个元素从堆中删除 将余下的元素构成完全二叉树重新调整成堆 反复进行，直到堆空。,回想一下,2.插入排序： 基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。 线性

26、插入排序 从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上 对半插入排序 在有序区中进行对分查找，以确定插入的位置,回想一下,3.交换排序 基本思想：两两比较反即换。 冒泡排序 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上； 依次类推，则完成排序。 快速排序 通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。,回想一下,4.归并排序 基本思想：将相邻的有序子文件两两合并，得到n/2个长度为2或1的有序子文件，再两两归并得到n/4个有序子文件，以此类推，直至得到长为n的有序文件。,几种排序方法比较,各种排序方法的比较和选择,1.待排序的记录数目n； n较小的可用插入排序或简单选择排序, 若记录本身较大,宜采用选择排序,因插入法的移动次数较多 n较大的就要用时间复杂度为O(nlgn)的排序方法,如快速排序、归并排序或堆排序。 2.记录的大小(规模)；(记录很大的话要用大量时间和空间来移动它们，因此最好用链表作为存储结构，