归并排序

归并排序

时间复杂度是 O(nlogn)，空间复杂度是O(n)

#include <stdio.h>
#include <stdlib.h>

void printArray(int a[], int len)
{
    for(int i=0; i<len; ++i)
    {
        if(0==i)
            printf("[%d,",a[i]);
        else if(i < len-1)
            printf("%d,",a[i]);
        else
            printf("%d]\n",a[i]);
    }
}

//将 有序的数组 a、b 合并为一个有序的数组c。数组c要预先分配好内存。
void Merge2(int a[], int left1, int right1, int b[], int left2, int right2, int c[])
{
    int i = left1, j = left2, k = 0;
    for(k = 0; i <= right1 && j <= right2; ++k){
        if(a[i] <= b[j])
            c[k] = a[i++];
        else
            c[k] = b[j++];
    }
    while(i <= right1)
        c[k++] = a[i++];
    while(j <= right2)
        c[k++] = b[j++];
}

//将分别有序的data[s..m] 和 data[m+1 .. n] 归并为有序的 data[s..n]
void Merge(int data[], int s, int m, int n){
    int i, start = s, k=0;
    int *temp = (int*) malloc((n-s+1)*sizeof(int));
    for(i=m+1; s<=m && i<=n; ++k){
        if( data[s] <= data[i] ) 
            temp[k]=data[s++];
        else
            temp[k] = data[i++];
    }
    for(; s<=m; ++k)
        temp[k] = data[s++];
    for(; i<=n; ++k)
        temp[k] = data[i++];
    
    //拷贝 temp 到 data里
    for(i=0; i<k; ++i){
        data[start++] = temp[i];
    }
    free(temp);
}

void MSort(int data[], int left, int right){
    if(left < right){
        int mid = left + (right-left)/2;
        MSort(data, left, mid);
        MSort(data, mid+1, right);
        Merge(data, left, mid, right);
    }
}

int main(){
    //int a[] = {4,10,55,5,22,32,72,113};
    //int len = sizeof(a)/sizeof(a[0]);
    //int m = 2;
    //printArray(a,len);
    //Merge(a,0,m,len-1);
    //printArray(a,len);
    
    // int a[] = {1,2,3,4,9,15,16,21,45};
    // int b[] = {3,5,6,7,11,17,18,200};
    // int aLen = sizeof(a)/sizeof(a[0]);
    // int bLen = sizeof(b)/sizeof(b[0]);
    // int len = aLen+bLen;
    // int *res = (int*) malloc(len*sizeof(int));
    // Merge2(a,0,aLen-1,b,0,bLen-1, res);
    // printArray(res,len);
    // free(res);
    
    // int a[] = {4,10,55,5,22,32,72,113,200};
    // int len = sizeof(a)/sizeof(a[0]);
    // int m = 2;
    // printArray(a,len);
    // int res[100] = {0};
    // Merge2(a,0,m,a,m+1,len-1,res);
    // printArray(res,len);
    
    int a[]={3,7,9,2,1,0,15,10};
    int len = sizeof(a)/sizeof(a[0]);
    printArray(a,len);
    MSort(a,0,len-1);
    printArray(a,len);
    return 0;
}

--