程序设计综合实践-归并排序和快速排序

三、归并排序

前面讨论的几种简单排序方法，算法比较简单，时间复杂度都是，适用于问题规模不太大的情况。它们都是稳定的排序方法，即：可以保证，两个关键字相同的元素，原序列中排在前面元素，结果序列中也排在前面，保持相对次序不变。归并排序同样应用了分治法。当问题规模较小，待排序序列长度不超过1时，无需排序；当问题规模较大时，将较大规模待排序的序列一分为二，先后分别对前后两段问题规模减半子序列使用归并排序进行排序，并将排序完成后前后两段子序列归并成一段有序序列，归并后的有序序列存放在辅助数组中，最后，将辅助数组中有序序列拷贝至原数组空间。排序递归进行，最终划分后的子序列长度为1。1

2图3.1归并排序示意图//算法3.5归并排序。对存放n个元素的数组按关键字递增排序voidMergeSort(ElemTypeA[],intlow,inthigh,ElemTypeAux[]){if(low>=high)return;//规模不超过1，无需排序m=(low+high)div2;//二分法划分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

//归并排序中有序段合并子算法voidMerge(ElemTypeA[],intlow,intm,inthigh,ElemTypeAux[]){i=low;//前段有序子序列起点j=m+1;//后段有序子序列起点k=i;//归并结果起始下标while(i<=m&&j<=high){//较小元素先转移至结果缓冲区if(A[i].key<=A[j].key)Aux[k++]=A[i++];elseAux[k++]=A[j++];}

4while(i<=m)//前段剩余元素转移至结果缓冲区Aux[k++]=A[i++];while(j<=high)//后段剩余元素转移至结果缓冲区Aux[k++]=A[j++];}5归并排序的主要操作是元素比较和元素移动，元素移动包括归并时移动到辅助数组和辅助数组移动回原数组，元素移动次数多于元素比较次数，所以，我们下面考虑算法时间复杂度时只需考虑元素移动次数。假设T(n)是n个元素归并排序的时间复杂度，N是大于等于n且符合N=2k的最小正整数，k为正整数，k=log2N，N<2n。N个元素的归并排序包括2个N/2子序列的归并排序和2N次元素的移动：T(N)=2T(N/2)+2N继续展开，可得：显然，T(N)是nlog2n数量级的，T(n)也一样。任何情况下，归并排序的时间复杂度都是O(nlog2n)。另外，归并排序需要使用与原数组空间相同大小的辅助数组空间，空间复杂度是O(n)。6四、快速排序

快速排序同样使用了分治法。当问题规模较小，待排序序列长度不超过1时，无需排序；当问题规模较大时，快速排序先将较大规模待排序的序列划分为三个部分：中间部分只有一个元素，称为枢轴元素，前面部分所有元素小于等于枢轴元素，后面部分所有元素大于等于枢轴元素；这样，只要分别对前面部分元素子序列和后面部分元素子序列完成排序即可，前后两部分问题规模大幅减小后子序列的排序同样可以使用快速排序进行。7

8图3.2a快速排序示意图//算法3.6a快速排序递归部分。对存放n个元素的数组按关键字递增排序voidQuickSort(ElemTypeA[],intlow,inthigh){if(low>=high)return;//规模不超过1的子序列无需排序pivot=QuickPass(A,low,high);//快速划分，返回划分后枢轴元素所在位置QuickSort(A,low,pivot-1);//对前一段子序列快速排序QuickSort(A,pivot+1,high);//对后一段子序列快速排序}9

10图3.2b快速排序中快速划分示意图//算法3.6b快速排序划分部分。intQuickPass(ElemTypeA[],intlow,inthigh){ElemTypex=A[low];//枢轴元素while(low<high){while(low<high&&x.key<=A[high].key)--high;//从右往左扫描，保留右边大于等于枢轴元素的所有元素位置不变if(low==high)break;A[low++]=A[high];//较小元素从右边移至左边空余位置

11while(low<high&&x.key>=A[low].key)++low;//从左往右扫描，保留左边小于等于枢轴元素的所有元素位置不变if(low==high)break;A[high--]=A[low];//较大元素从左边移至右边空余位置}A[low]=x;//枢轴元素放回空余位置returnlow;//返回枢轴元素所在位置}

12快速排序的时间复杂度。快速排序的主要操作为元素比较和元素移动，元素移动次数不多于元素比较次数，下面考虑算法时间复杂度时只考虑元素比较次数。假设T(n)为n个元素快速排序时平均时间复杂度，T(0)=0，T(1)=0，N>1时，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)等价于：

继续展开后累加求和，得到：从右侧图示中柱形面积小于等于对应积分，可以看到下述公式：展开后化简得到：因此：