第9章-归并排序.ppt

稳定的排序算法 2-路归并排序可以采用递归方法实现： 首先将r1[]前半段的记录用归并法排序后放到r2[]的前半段； 将r1[]后半段的记录用归并法排序后放到r2[]的后半段； 将r2[]的前半段和后半段合并到r3[]中。 * * * * * 第9章 内部排序 9.1 排序的基本概念 9.2 插入类排序 9.3 交换类排序法 9.4 选择类排序法 9.5 归并排序 9.6 分配类排序 9.7 各种排序方法的综合比较 9.8 总结与提高 9.5 归并排序 基本思想：将两个或两个以上有序表合并成一个新的有序表。 假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1； 然后两两归并，得到?n/2?个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列； 在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。 归并排序的示例为： (19) (13) (05) (27) (01) (26) (31) (16) (13,19) (05,27) (01,26) (16,31) (05,13,19,27) (01,16,26,31) (01,05,13,16,19,26,27,31) 4 8 7 3 2 6 5 1 4 8 3 7 6 2 5 1 3 4 7 8 6 5 2 1 1 2 3 4 8 7 6 5 a: b: s=1 s=2 a: s=4 b: s=8 void Merge(RecordType r1[], int low, int mid, int high, RecordType r2[]) /* 已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r2[low..high] */ { i=low;　j=mid+1;　k=low; while ( (i=mid)(j=high) ) { if ( r1[i].key=r1[j].key ) { r2[k]=r1[i]; ++i; } else { r2[k]=r1[j]; ++j; } ++k; } 2路归并排序算法 …….. …….. while( i=mid ) { r2[k]=r1[i]; k++; i++; } while( j=high) { r2[k]=r1[j]; k++; j++; } } /* Merge */ 2路归并排序算法 void MergeSort ( RecordType r[], int n ) /* 对记录数组r[1..n]做归并排序 */ { MSort ( r, 1, n, r ); } 递归算法 *