数据结构--第九章内部排序试卷.ppt

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) 2-路归并排序法的基本操作是将待排序列中相邻的两个有序子序列合并成一个有序序列。 合并算法描述如下： void Merge ( RecordType r1[], int low, int mid, int high, RecordType r[]) /*已知r1[low..mid]和r1[mid+1..high]分别按关键字有序排列，将它们合并成一个有序序列，存放在r[low..high] */ {i=low；j=mid+1； k=low； while ( (i=mid)(j=high) ) {if ( r1[i].key=r1[j].key ) {r[k]=r1[i] ； ++i；} else {r[k]=r1[j] ； ++j；} ++k ； } if ( i=mid ) r[k..high] =r1[i..mid]； if ( j=high ) r[k..high] =r1[j..high]； } /* Merge */ 2-路归并排序可以采用递归方法实现，具体描述如下： void MergeSort (RecordType r1[], int low, int high, RecordType r[]) /* r1[low..high]经过排序后放在r[low..high]中，r2[low..high]为辅助空间 */ { RecordType *r2； r2=(RecordType*)malloc(sizeof(RecordType)*(hight-low+1)); if ( low==high ) r[low]=r1[low]； else{ mid=(low+high)/2； MergeSort(r1，low， mid, r2)； MergeSort(r1，mid+1，high, r2)； Merge (r2，low，mid，high， r)； } free(r2); } /* MergeSort */ 归并排序的算法分析： 归并排序中一趟归并中要多次用到2-路归并算法，一趟归并排序的操作是调用 ?n/2h ?次算法merge 将r1[1…n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在r[1…n]中，其 时间复杂度为O(n)。整个归并排序需进行m（m=log2n）趟2-路归并，所以归并排序总的时间复杂度为O（nlog2n）。在实现归并排序时，需要和待排记录等数量的辅助空间，空间复杂度为O(n)。 归并排序的最大特点是，它是一种稳定的排序方法。 类似2-路归并排序，可设计多路归并排序法，归并的思想主要用于外部排序。 外部排序可分两步，①待排序记录分批读入内存，用某种方法在内存排序，组成有序的子文件，再按某种策略存入外存。②子文件多路归并，成为较长有序子文件，再记入外存，如此反复，直到整个待排序文件有序。 外部排序可使用外存、磁带、磁盘，最初形成有序子文件长取决于内存所能提供排序区大小和最初排序策略，归并路数取决于所能提供排序的外部设备数。 9.6 分配类排序 分配类排序则利用分配和收集两种基本操作，基数类排序就是典型的分配类排序。 9.6.1 多关键字排序 例如：我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题。若规定花色和面值的顺序如下： 花色：梅花 方块 红桃 黑桃 面值：A23…10JQK 并进一步规定花色的优先级高于面