数据结构（排序三）

归并排序

利用归并的思想实现的排序方法

二路归并排序原理

• 假设初始序列有n个记录，则可以看成n个有序的子序列，每个子序列的长度为1
• 然后两两归并，得到┌n/2┐个长度为2或1的有序子序列；再次两两归并，...
• 如此重复，直到得到一个长度为n的有序序列为止

#include <stdio.h>
#define MAXSIZE 15

void sort(int *s1,int n,int *s2,int m){
    int i,j,k=0;
    int temp[MAXSIZE];
    for(i=0,j=0;i<n && j<m;){
        if(s1[i]<s2[j])
            temp[k++]=s1[i++];
        else
            temp[k++]=s2[j++];
    }
    while(i<n)
        temp[k++]=s1[i++];
    while(j<m)
        temp[k++]=s2[j++];
    for(i=0;i<k;i++){
        s1[i]=temp[i];
    }
}

void MergeSort(int a[],int n){
    int *s1,*s2,m;
    if(n>1){
        s1=a;
        m=n/2;
        s2=s1+m;
        MergeSort(s1,m);
        MergeSort(s2,n-m);
        sort(s1,m,s2,n-m);
    }
}

void main(){
    int a[]={9,8,7,6,5,4,3,2,1,0},i;
    MergeSort(a,10);
    for(i=0;i<10;i++){
        printf("%d  ",a[i]);
    }
}