内部排序——归并排序

大家好，想要了解更多关于内部排序，可以看看前面的文章噢！

4.归并排序

归并排序是把两个或两个以上的有序表合并成一个新的有序表。把含有 N 个记录的无序表当成 N 个有序的子表，每个子表的的长度为 1，然后，利用两两归并，得到 n/2 个长度为 2 或 1 的有序子表。再两两归并直到得到长度为 N 的一个有序表。

例如: 对 49 38 65 97 76 13 27 进行归并排序。

算法：

void Merge(RcdType SR,RcdType &TR, inti, int m, int n){(J 为第二个表的下限初值)

for(j=m+1，k=i; i<= m && j<= n; ++ k){

if LQ(SR[i].key,SR[i].key)

TR[K] = SR[i++];

else TR[k]=SR[j++] } (把第 J 个值送后再加 1)

if (i<=m)TR[k...n]=SR [i...m];(第二个表空)

if(j<=n)TR[k...n]=SR[j..n]; (第一个表空)

}// Merge

void Msort(RcdType SR[], RcdType&TR1[],int s, int t) /*int s 为排序表的下限, int t 为排序表的上限*/

{

if(s==t) TR1[s]=SR[s];

else {

m=(s+t)/2; (将 SR[s...t]平分为 SR[s.….m]和 SR[m+1...t])

Msort(SR,TR1,s,m); (递归地将 SR[s…m]归并为有序的 TR1[s...m])

Msort(SR,TR2, m+1,t); (递归地将 SR[m+1...t]归并为有序的 TR2[m+1..t])

Merge(TR2,TR1,s,m,t); (将 TR2[m+1..t]]归并为 TR1[s..t])

}// Msort

void MergeSort( SQList & L){

Msort (L.r, L.r1, 1,L.length);

}// MergeSort

总结

归并排序时间复杂度为 O（nlog2n）,理解起来也比较容易。