http://acm.pku.edu.cn/judgeonline/probleM?id=1649 设计与学科前沿研究相结合的综合实习大项目进行设计型和综合型实践训练,例如让学 生在开源的 Lucene等文本索引包基础上,添加自己的网页排序算法。 7.教学案例 归并排序 Sedgwick逆转第2个子序列的优化策略 算法思想如下:在把数组暂时复制到临时数组时,将第二个子数组中元素的顺序颠倒了 一下。这样,两个子数组从两端开始处理,向中间推进,使得这两个子数组的两端互相成为 另一个数组的“监视哨”,从而不需要检査子序列结束的情况。另外,当子数组小于某个长度 (例如28)时,也不继续递归,而是在最后对整个序列使用插入排序。 算法代码如下: #define THRESHOLd 28 emplate <class record> void ModMerge Sort( Record array, Record Temp array, int left, int right){∥Aray为待排序数组,left, right 两端 int middle. if (right-left+1>THRESHOLD) ∥如果序列长度大于阙值(28最佳),递归归并 middle=(left+ right)/2 ∥从中间划分为两个子序列 ModMergesorti(Aray, Temp Array, left, middle),∥对左边一半进行递归 ModMerge Sort(Aray, Temp array, middle+l, right),∥对右边一半进行递归 ModMerge( Array, Temp Array, left, right, middle); 亍归并 else InsertSort(& Array[left], right-lefi+1);,∥小长度子序列进行插入排序,“&”传Amay[e的地址 ∥优化的 Sedgwick两个有序子序列归并,右子序列逆置了,都从两端向中间扫描,归并到新数组 void ModMerge( Record Array[, Record TempArrayll, int left, int right,int middle) H fiE ∥两个子序列的起始位置 int ij, k for(i=left; i<= middle; i++ 制左边的子序列 Temp Array[]= Array[]; forg=1; j<=right-middle, j++) ∥复制右边的子序列,但顺序颠倒过来 Temp Array[right-j+1]= Array[j+middle] ∥开始归并,取较小者插入合并数组中 for(indexI left, index2=right, k= left; k<=right; k++) if( Temp array[ indexI]< TempArray[index2])∥为保证稳定性,相等时左边优先 Array[k]= Temp[index++ else Array[k]=TempArray index2-] 讲解算法时,注意介绍前面的图示。强调复制右边的子序列时,顺序颠倒过来http://acm.pku.edu.cn/JudgeOnline/problem?id=1649 设计与学科前沿研究相结合的综合实习大项目进行设计型和综合型实践训练，例如让学 生在开源的 Lucene 等文本索引包基础上，添加自己的网页排序算法。 7．教学案例 归并排序 Sedgwick 逆转第 2 个子序列的优化策略。 算法思想如下：在把数组暂时复制到临时数组时，将第二个子数组中元素的顺序颠倒了 一下。这样，两个子数组从两端开始处理，向中间推进，使得这两个子数组的两端互相成为 另一个数组的“监视哨”，从而不需要检查子序列结束的情况。另外，当子数组小于某个长度 （例如 28）时，也不继续递归，而是在最后对整个序列使用插入排序。 算法代码如下： #define THRESHOLD 28 template <class Record> void ModMergeSort(Record Array[], Record TempArray[], int left, int right) { // Array 为待排序数组，left，right 两端 int middle; if (right-left+1 > THRESHOLD) { // 如果序列长度大于阈值(28 最佳)，递归归并 middle = (left + right) / 2; // 从中间划分为两个子序列 ModMergeSort(Array, TempArray ,left,middle); // 对左边一半进行递归 ModMergeSort(Array, TempArray ,middle+1,right);// 对右边一半进行递归 ModMerge(Array, TempArray ,left,right,middle); // 进行归并 } else InsertSort(&Array[left],right-left+1); // 小长度子序列进行插入排序，“&”传 Array[left]的地址 } // 优化的 Sedgwick 两个有序子序列归并，右子序列逆置了，都从两端向中间扫描，归并到新数组 template <class Record> void ModMerge(Record Array[],Record TempArray[],int left,int right,int middle) { //归并过程 int index1,index2; // 两个子序列的起始位置 int i,j,k ; for (i = left; i <= middle; i++) // 复制左边的子序列 TempArray[i] = Array[i]; for (j = 1; j <= right-middle; j++) // 复制右边的子序列，但顺序颠倒过来 TempArray[right-j+1] = Array[j+middle]; // 开始归并，取较小者插入合并数组中 for (index1 = left, index2 = right, k = left; k <= right; k++) if (TempArray[index1] <= TempArray[index2]) // 为保证稳定性，相等时左边优先 Array[k] = TempArray[index1++]; else Array[k] = TempArray[index2--]; } 讲解算法时，注意介绍前面的图示。强调复制右边的子序列时，顺序颠倒过来