第章 分治策略合并排序.pptVIP

Software College, Northeast University neuzl@163.com 2.4 合并排序 MergeSort 插入法InsertionSort template class Type INSERTIONSORT( Type A[ ], int n) { Type item; int i; for( int j=1; j n ; j++) { item=A[ j ]; i= j -1; while( itemA[ i ] i-1) do { A[i+1]=A[i]; i=i-1; } A[i+1]=item; } } 插入法计算时间 插入算法的while循环中的语句可能执行0~j次(j=1,2…n-1)。所以，最坏情况的计算时间为：2+…+n=(n(n+1)/2)-1= Θ(n2)。 如果输入数据本来就是按非降次序排列的，则根本不会进入while循环，这就是最好情况，计算时间是?(n)。 MergeSort Algorithm: Split array A[1..n] in two and make copies of each half in arrays B[1.. n/2 ] and C[1.. n/2 ] Sort arrays B and C Merge sorted arrays B and C into array A as follows: Repeat the following until no elements remain in one of the arrays: compare the first elements in the remaining unprocessed portions of the arrays copy the smaller of the two into A, while incrementing the index indicating the unprocessed portion of that array Once all elements in one of the arrays are processed, copy the remaining unprocessed elements from the other array into A. 分治策略求解 若n为1，算法终止； 否则，将这一元素集合分割成两个或更多个子集合，对每一个子集合分别排序。 然后将排好序的子集合归并为一个集合。 归并排序过程 void MergeSort(type a[ ], int left, int right) { if (leftright) //至少有两个元素 { 找到数组的中间元素下标mid 递归调用算法本身对从left到mid的数组元素排序 递归调用算法本身对从mid到right的数组元素排序 合并两段排好序的数组 } } 归并排序主程序伪代码 templateclass Type void MergeSort(Type a[ ], int left, int right) {// A[left:right]是一个全程数组， //含有 right-left+1个待排序的元素。 if ( ) { //至少有2个元素 int mid = (left+right)/2; //求当前数组的分割点 MergeSort(a, left,mid); MergeSort(a, mid+1, right); Merge(a, b, left, mid , right); copy(a, b, left, right); } } 合并过程Merge(a,b,left,mid,right) 前提是待合并的两段数据已经排好序 考虑数组a的两段为[1, 7, 8, 9]和[2, 3, 4, 5] 合并函数MERGE的实现 合并函数 template class Type void Merge( Type a[ ], Type b[ ], int l, int m, int r) {//合并a[l:m]和a[m+1:r]到b[l:r] int i=l; j=m+1,