【考研计算机专业课】武汉大学数据结构PPT课件 第10章 内排序.ppt

while (i=mid) //将第1段余下部分复制到R1 { R1[k]=R[i]; i++;k++; } while (j=high) //将第2段余下部分复制到R1 { R1[k]=R[j]; j++;k++; } for (k=0,i=low;i=high;k++,i++) //将R1复制回R中 R[i]=R1[k]; free(R1); } void MergePass(RecType R[],int length,int n) { int i; for (i=0;i+2*length-1n;i=i+2*length) //归并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()实现了一趟归并 二路归并排序算法如下： void MergeSort(RecType R[],int n) { int length; for (length=1;lengthn;length=2*length) MergePass(R,length,n); } 例 设待排序的表有8个记录,其关键字分别为{18,2,20,34,12,32,6,16,1,5}。说明采用归并排序方法进行排序的过程。 18 2 20 34 12 32 6 16 1 5 初始： 2 18 20 34 12 32 6 16 1 5 2 18 20 34 6 12 16 32 1 5 2 6 12 16 18 20 32 34 1 5 1 2 5 6 12 16 18 20 32 34 log210取上界为4 第1趟 第2趟 第3趟 第4趟 　 容易看出，对 n 个记录进行归并排序的时间复杂度为Ο(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 ?log2n? 趟。 例 对任意的7个关键字进行排序，至少要进行 次关键字之间的两两比较。 A.13 B.14 C.15 D.16 解：基于“比较”进行排序的算法在最坏情况下所需进行的比较次数至少为?log2(n!)?。?log2(7!)?=13。本题答案为A。 例 若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 。 A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序 本题为2009年全国考研题 void BubbleSort(RecType R[],int n) { int i,j,exchange;RecType temp; for (i=0;in-1;i++) { exchange=0; for (j=n-1;ji;j--) //比较,找出最小关键字的记录 if (R[j].keyR[j-1].key) { temp=R[j]; R[j]=R[j-1];R[j-1]=temp; exchange=1; } if (exchange==0) return; //中途结束算法 } } 最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟冒泡 “比较”的次数： 最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟冒泡 “比较”的次数： 0 “移动”的次数： “移动”的次数： n-1 10.3.2 快速排序 快速排序是由冒泡排序改进而得的。 基本思想：在待排序的n个记录中任取一个记录(通常取第一个记录)，把该记