八大排序算法-归并排序

基本思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并示例：

合并方法

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为m、n-m。

1. j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
2. 若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束

3. //选取r[i]和r[j]较小的存入辅助数组rf

   如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵
   否则，rf[k]=r[j]； j++； k++； 转⑵

4. //将尚未处理完的子表中元素存入rf

   如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空
   如果j<=n , 将r[j…n] 存入rf[k…n]//后一子表非空

5. 合并结束。

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] 
void Merge(ElemType r,ElemType rf,int i,int m, int n){
    int j,k;
    for(j=m+1,k=i;i<=m && j<=n;k++){
        if(r[i]<r[j]){//将比较小的元素插入到rf中元素k和i(或者j)的位置后移 
            rf[k] = r[i++];
        }else{
            rf[k] = r[j++];
        }
    }
    while(i<=m){
        rf[k++] = r[i++]; //如果前半部分有剩余则补到rf后边 
    }
    while(j<=n){
        rf[k++] = r[j++];//如果后半部分有剩余则补到rf后边 
    }
} 

两路归并的递归方法

//两路归并的递归算法
void MSort(ElemType r,ElemType rf,int s,int t){
    ElemType rf2;
    if(s == t){
        rf[s] = r[s];   //当时单个元素的时候结束递归，开始归并 
    }else{
        int m = (s+t)/2;//将r[s...t]平分成两部分r[s...m]和r[m+1...t]
        MSort(r,rf2,s,m);//递归将r[s...m]归并到rf2[s...m] 
        MSort(r,rf2,m+1,t);//递归将r[m+1...t]归并到rf2[m+1...t] 
        Merge(rf2,rf,s,m,t);//将rf[s...m]和rf[m+1...t] 归并到rf[s...t] 
    }
} 

完整代码

#include<stdio.h>

//定义长度为10的整型数组类型 
typedef int ElemType[10];

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n] 
void Merge(ElemType r,ElemType rf,int i,int m, int n){
    int j,k;
    for(j=m+1,k=i;i<=m && j<=n;k++){
        if(r[i]<r[j]){//将比较小的元素插入到rf中元素k和i(或者j)的位置后移 
            rf[k] = r[i++];
        }else{
            rf[k] = r[j++];
        }
    }
    while(i<=m){
        rf[k++] = r[i++]; //如果前半部分有剩余则补到rf后边 
    }
    while(j<=n){
        rf[k++] = r[j++];//如果后半部分有剩余则补到rf后边 
    }
} 
//两路归并的递归算法
void MSort(ElemType r,ElemType rf,int s,int t){
    ElemType rf2;
    if(s == t){
        rf[s] = r[s];   //当时单个元素的时候结束递归，开始归并 
    }else{
        int m = (s+t)/2;//将r[s...t]平分成两部分r[s...m]和r[m+1...t]
        MSort(r,rf2,s,m);//递归将r[s...m]归并到rf2[s...m] 
        MSort(r,rf2,m+1,t);//递归将r[m+1...t]归并到rf2[m+1...t] 
        Merge(rf2,rf,s,m,t);//将rf[s...m]和rf[m+1...t] 归并到rf[s...t] 
    }
} 
//打印 
void print(ElemType r,int n){
    int i;
    for(i=0;i<n;i++){
        printf("%3d",r[i]);
    }
    printf("\n");
}

int main(){
    ElemType r = {3,1,5,7,2,4,9,6,10,8}; 
    ElemType rf; 
    printf("排序前：\n");
    print(r,10); 
    printf("归并排序后：\n");
    MSort(r,rf,0,9);
    print(rf,10);

    return 0;
} 

执行结果