第八章 排序 归并排序

归并排序

1 . 基本思想 : 将两个或两个以上的有序子序列 “归并” 成一个有序序列

2 . 在内部排序中, 通常采用的是 2-路归并排序， 即将两个位置相邻的有序子序列 R[1,m] 和 ????R[m+1, n] 归并成一个有序序列 R[1,n]

3 . 合并两个相邻的有序子序列 : r[s, m] 与 r[m+1, t], 合并成 r1[s, t]

void Merge(int r[], int s, int m, int t){
    int r1[n]; // 数组 r1 作为合并的辅助空间
    int i=s, j=m+1, k=s;
    while(i<=m && j<=t){
        if(r[i]<=r[j]) r1[k++]=r[i++];
        else r1[k++]=r[j++];
    }
    while(i<=m) r1[k++]=r[i++];
    while(j<=t) r1[k++]=r[j++];
    for(int i=s; i<=t; i++) r[i]=r1[i];
} 

4 . 归并排序 r[s] ~ r[t]

void MergeSort(int r[], int s, int t){
    if(s==t) return ; // 待排区间长度为 1 , 递归结束 
    int m=(s+t)/2;
    MergeSort(r, s, m); // 归并排序前半个子序列 
    MergeSort(r, m+1, t); // 归并排序后半个子序列 
    Merge(r, s, m, t); // 将两个已排序的子序列合并 
} 

5 . 算法分析

• 时间复杂度 : 最好最好与平均全部是 $O(nlo{g}_{2}n)$

• 空间复杂度 : $O(n)$

• 归并排序是一种稳定的排序算法