(3.8)--3.2 归并排序和快速排序.ppt
三、归并排序 前面讨论的几种简单排序方法，算法比较简单，时间复杂度都是 ，适用于问题规模不太大的情况。它们都是稳定的排序方法，即：可以保证，两个关键字相同的元素，原序列中排在前面元素，结果序列中也排在前面，保持相对次序不变。归并排序同样应用了分治法。当问题规模较小，待排序序列长度不超过1时，无需排序；当问题规模较大时，将较大规模待排序的序列一分为二，先后分别对前后两段问题规模减半子序列使用归并排序进行排序，并将排序完成后前后两段子序列归并成一段有序序列，归并后的有序序列存放在辅助数组中，最后，将辅助数组中有序序列拷贝至原数组空间。排序递归进行，最终划分后的子序列长度为1。1 2图 3.1 归并排序示意图/算法3.5 归并排序。对存放n个元素的数组按关键字递增排序 void MergeSort(ElemType A,int low,int high,ElemType Aux)if(low=high)return;/规模不超过1，无需排序 m=(low+high)div 2;/二分法划分 MergeSort(A,low,m，Aux);/前一半子序列排序 MergeSort(A,m+1,high，Aux);/后一半子序列排序 Merge(A,low,m,high,Aux);/归并两段有序子序列 for(i=low;i=high;+i)A i=Aux i;/移动回原数组 3 /归并排序中有序段合并子算法 void Merge(ElemType A,int low,int m,int high,ElemType Aux)i=low;/前段有序子序列起点 j=m+1;/后段有序子序列起点 k=i;/归并结果起始下标 while(i=m&j=high)/较小元素先转移至结果缓冲区 if(A i.key=A j.key)Aux k+=Ai+;else Aux k+=Aj+;4 while(i=m)/前段剩余元素转移至结果缓冲区 Aux k+=Ai+;while(j=high)/后段剩余元素转移至结果缓冲区 Aux k+=Aj+;5归并排序的主要操作是元素比较和元素移动，元素移动包括归并时移动到辅助数组和辅助数组移动回原数组，元素移动次数多于元素比较次数，所以，我们下面考虑算法时间复杂度时只需考虑元素移动次数。假设T(n)是n个元素归并排序的时间复杂度，N是大于等于n且符合N=2k的最小正整数，k为正整数，k=log2N，N=high)return;/规模不超过1的子序列无需排序 pivot=QuickPass(A,low,high);/快速划分，返回划分后枢轴元素所在位置 QuickSort(A,low,pivot-1);/对前一段子序列快速排序 QuickSort(A,pivot+1,high);/对后一段子序列快速排序 9 10图 3.2b 快速排序中快速划分示意图/算法3.6b 快速排序划分部分。int QuickPass(ElemType A,int low,int high)ElemType x=A low;/枢轴元素 while(low high)while(low high&x.key=Ahigh.key)-high;/从右往左扫描，保留右边大于等于枢轴元素的所有元素位置不变 if(low=high)break;Alow+=Ahigh;/较小元素从右边移至左边空余位置 11 while(low=Alow.key)+low;/从左往右扫描，保留左边小于等于枢轴元素的所有元素位置不变 if(low=high)break;Ahigh-=Alow;/较大元素从左边移至右边空余位置 A low=x;/枢轴元素放回空余位置 return low;/返回枢轴元素所在位置 12快速排序的时间复杂度。快速排序的主要操作为元素比较和元素移动，元素移动次数不多于元素比较次数，下面考虑算法时间复杂度时只考虑元素比较次数。假设T(n)为n个元素快速排序时平均时间复杂度，T(0)=0，T(1)=0，N1时，Pi为划分时有i个元素位于枢轴元素左边段的概率，n个元素划分一次的比较次数为n-1，得到：不失一般性，假设所有Pi相等，Pi=1/n，即：展开，得到：13 14消除分母后两边相减，得到：nT(n)-(n-1)T(n-1)=2(n-1)+2T(n-1)化简后，等价于：nT(n)-(n+1)T(n-1)=2(n-1)等价于：继续展开后累加求和，得到：从右侧图示中柱形面积小于等于对应积分，可以看到下述公式：展开后化简得到：因此：平均情况下，快速排序平均时间复杂度是O(nlog2n)。当原始序列几乎有序时，快速划分结果段长度不太均衡，退化为冒泡排序效率，因此，最坏情况下，快速排序时间复杂度退化为 。另外，快速排序递归所需工作栈辅助空间，平均情况下为O(log2n)，最坏情况下为 O(n)。借助于栈，快速排序算法可改写为非递归算法。15
