《第13周内排序第5讲-归并排序.pdf》由会员分享，可在线阅读，更多相关《第13周内排序第5讲-归并排序.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、归并排序是归并排序是多次多次将相邻将相邻两两个或两个以上个或两个以上的有序表合并成一个的有序表合并成一个 新的有序表。新的有序表。 最简单的最简单的归并归并是将相邻是将相邻两两个有序的子表个有序的子表合并成一个有序的表，合并成一个有序的表， 即即二路归并排序二路归并排序。 1、归并、归并的思路的思路 一次二路一次二路归并：将归并：将两个位置相邻的记录有序子两个位置相邻的记录有序子序列归并为序列归并为 一个记录的有序序列。一个记录的有序序列。 有有 序序 序序 列列 Rlow.high 有序子有序子序列序列 Rlow.mid有序子有序子序列序列 Rmid+1.high Rlow.high voi
2、d Merge(RecType R,int low,int mid,int high) RecType *R1; int i=low, j=mid+1, k=0; /k是是R1的下标的下标,i、j分别为第分别为第1、2段的下标段的下标 R1=(RecType *)malloc(high-low+1)*sizeof(RecType); while (i=mid i+;k+; else/将第将第2段中的记录放入段中的记录放入R1中中 R1k=Rj; j+;k+; Merge()：一次：一次二路归并，将二路归并，将两两个相邻的有序子序列归并为一个个相邻的有序子序列归并为一个有有 序序列。序序列。 空
3、间复杂度为空间复杂度为 O(high-low+1) 2、二、二路归并算法路归并算法 while (i=mid)/将第将第1段余下部分复制到段余下部分复制到R1 R1k=Ri; i+;k+; while (j=high)/将第将第2段余下部分复制到段余下部分复制到R1 R1k=Rj; j+;k+; for (k=0,i=low;i=high;k+,i+)/将将R1复制回复制回R中中 Ri=R1k; free(R1); void MergePass(RecType R,int length,int n) int i; for (i=0;i+2*length-1n;i=i+2*length) /归并
4、归并length长的两相邻子表长的两相邻子表 Merge(R,i,i+length-1,i+2*length-1); if (i+length-1n)/余下两个子表余下两个子表,后者长度小于后者长度小于length Merge(R,i,i+length-1,n-1);/归并这两个子表归并这两个子表 MergePass()：一趟二路归并（一趟二路归并（段长度为段长度为length ）。）。 length=2 两个段长度均为两个段长度均为 length 第第2个个段段长度小于长度小于 length MergeSort()：二二路归并排序路归并排序算法：算法： void MergeSort(RecT
5、ype R,int n) int length; for (length=1;lengthn;length=2*length) MergePass(R,length,n); log2n 趟 【例例10- -7】 设待排序表有设待排序表有10个记录个记录,其关键字分别为其关键字分别为18，2，20， 34，12，32，6，16，1，5。说明采用归并排序方法进行排序的过。说明采用归并排序方法进行排序的过 程。程。 1822034123261615 初始：初始： 需要需要log210取取上界即上界即4趟趟 2 1820 3412 326 161 5 第第1趟趟 2 18 20 346 12 16 3
6、21 5第第2趟趟 2 6 12 16 18 20 32 341 5第第3趟趟 1 2 5 6 12 16 18 20 32 34第第4趟趟 2 1820 3412 326 161 5 2 18 20 3412 18 20 34 1822034123261615 2 6 12 16 18 20 32 34 1 2 5 6 12 16 18 20 32 34 更清楚的表示更清楚的表示 一颗归并树一颗归并树 3、归并、归并算法分析算法分析 所以空间复杂所以空间复杂度为度为(n)。 1 52 6 12 16 18 20 32 34 1 2 5 6 12 16 18 20 32 34 每一次每一次二路
7、归并后二路归并后临时空间都会释放。而最后的一次临时空间都会释放。而最后的一次二路归二路归 需要需要全部记录参加归并：全部记录参加归并： 占用临时空间为全部记录个数占用临时空间为全部记录个数n 【例例10- -8】数据序列数据序列5,4,15,10,3,2,9,6,8是某排序方法第一趟是某排序方法第一趟 后的结果，该排序算法可能是后的结果，该排序算法可能是。 A.冒泡排序冒泡排序B.二路归并排序二路归并排序 C. 堆排序堆排序D.简单选择排序简单选择排序 第一趟：第一趟： 5,4, 15,10, 3,2, 9,6, 8 相邻的两个元素都是递减的相邻的两个元素都是递减的 【例例10- -9】就排序
8、算法所用的辅助空间而言，堆排序、快速排就排序算法所用的辅助空间而言，堆排序、快速排 序和归并排序的关系是序和归并排序的关系是。 A.堆排序堆排序 快速排序快速排序 归并排序归并排序 B.堆排序堆排序 归并排序归并排序 归并排序归并排序 快速排序快速排序 D.堆排序堆排序 快速排序快速排序 归并排序归并排序 堆排序、快速排序、归并排序堆排序、快速排序、归并排序 O(1) O(log2n) O(n) 二路归并二路归并 多路归并多路归并 推广推广 三三路路归并和二路归并的时间比较归并和二路归并的时间比较 三三路路归并的时间复杂度为归并的时间复杂度为O(nlog3n) nlog3n=nlog2n/log23=O(nlog2n) 同一个级别！同一个级别！ 本讲完本讲完