10.5归并排序归并排序的过程基于下列基本思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。
在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有序序列R
[l..n]有序子序列R[l..m]有序子序列R[m+1..n]这个操作对顺序表而言，是轻而易举的。voidMerg
e(RcdTypeSR[],RcdType&TR[],
inti,intm,intn){//将有序的记
录序列SR[i..m]和SR[m+1..n]//归并为有序
的记录序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;
++k){//将SR中记录由小到大地并入TRi
f(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j+
+];}……if(i<=m)TR[k..n]=SR[i..m
];//将剩余的SR[i..m]复制到TRif(j
<=n)TR[k..n]=SR[j..n];//将剩
余的SR[j..n]复制到TR归并排序的算法如果记录无序序列R[s..t]的两部分R[s.
.?(s+t)/2?]和R[?(s+t)/2?+1..t]分别按关键字有序，则利用上述归并算法很容易将它们归并成整
个记录序列是一个有序序列。由此，应该先分别对这两部分进行2-路归并排序。例如：52,23,80,
36,68,14(s=1,t=6)[52,23,80][36,68,14][5
2,23][80][52][23,52][23,52,80][36,68][14][36][6
8][36,68][14,36,68][14,23,36,52,68,80][23]
voidMsort(RcdTypeSR[],RcdType&TR1[],
ints,intt){//将SR[s..t]归并排
序为TR1[s..t]if(s==t)TR1[s]=SR[s];else{m=
(s+t)/2;Msort(SR,TR2,s,m);Msort(SR,
TR2,m+1,t);Merge(TR2,TR1,s,m,t);}}
//MsortvoidMergeSort(SqList&L){//
对顺序表L作2-路归并排序MSort(L.r,L.r,1,L.length);}//MergeSort
容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，
总共需进行?log2n?趟。习题：已知：一组无序记录，其关键字为：｛61，20，19，37，45，25，42｝用
归并排序方法对其升序排序，写出每一趟排序结果。10.7各种排序方法的综合比较一、时间性能1.平均的时间性能基数排序
时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：直接插入排序、起泡排序和简单选择排序
时间复杂度为O(n):2.当待排记录序列按关键字顺序有序时3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关
键字的分布而改变。直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O
(n2)。二、空间性能指的是排序过程中所需的辅助空间大小所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；2.快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间； |
|
