归并排序

二路归并排序

//二路归并排序
//分治法
//自底向上的二路归并排序算法
#include<stdio.h>
#include<malloc.h>
void disp(int a[],int n){
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}
void Merge(int a[],int low,int mid,int high){
    //将a[low..mid]和a[mid+1..high]两个相邻的有序子序列归并为一个有序子序列a[low..high] 
    int *tmp;
    int i = low,j = mid+1,k = 0;
    tmp = (int *)malloc((high - low + 1)*sizeof(int));
    while(i < mid && j < high){
        if(a[i] <= a[j]){
            tmp[k] = a[i];
            i++;
            k++;
        }
        else{
            tmp[k] = a[j];
            j++;
            k++;
        }
    }    
    while(i <= mid){
        tmp[k] = a[i];
        i++;
        k++;
    }
    while(j <= high){
        tmp[k] = a[j];
        j++;
        k++;
    }
    for(k = 0,i = low;i<=high;k++,i++)
        a[i] = tmp[k];
    free(tmp);
}
void MergePass(int a[],int length,int n){    //进行一趟二路归并排序 
    int i;
    for(i=0;i+2*length-1 < n;i = i+2*length)
        Merge(a,i,i+length-1,i+2*length-1);
    if(i+length-1 < n)
        Merge(a,i,i+length-1,n-1); 
}
void MergeSort(int a[],int n){
    int i; 
    for(int i = 1;i<n;i = 2*i)
        MergePass(a,i,n);
}
int main(){
    int n = 10;
    int a[] = {2,5,1,7,10,6,9,4,3,8};
    printf("排序前:");
    disp(a,n);
    MergeSort(a,n);        //二路归并算法 
    printf("排序后:");
    disp(a,n);
    return 0; 
}