学步园

不喜欢一般的归并排序算法中的合并部分，虽然简单，但是需要先拷贝两个需要归并的有序数组，麻烦。借鉴插入排序的思想，实现归并，空间复杂度为O(1)。

相关链接：

http://baike.baidu.com/view/90797.htm

http://www.cnblogs.com/jillzhang/archive/2007/09/16/894936.html

http://www.programfan.com/blog/article.asp?id=2539

/*
* 归并排序，归并部分没有采用算法导论中的一半方法，使用了一个空间复杂度为O(1)的方式 
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define N 10
#define N_RAND 200

void Merge(int *a, int p, int r, int q){
    int i,j,k,tmp;
    /*这是归并两个有序数组的实现*/
    for(i=p,j=r+1;j<=q;++i){
        if(a[i]>a[j]){
            tmp=a[j];
            for(k=j;k>i;--k){
                a[k]=a[k-1];  //元素逐个后移，类似插入排序 
            }
            a[k]=tmp;
            j++;
        }
    }
}

void MergeSort(int *a, int p, int q){
    if(p<q){
        int r=(p+q)/2;
        MergeSort(a,p,r);
        MergeSort(a,r+1,q);
        Merge(a,p,r,q);
    }
} 

int main(){
    int i, a[N];      
    srand((unsigned)time(NULL));    
    for(i=0;i<N;i++){
        a[i]=rand()%N_RAND;
        printf("%d ",a[i]);       
    }
    printf("\n");
    MergeSort(a,0,N-1);
    for(i=0;i<N;i++){
        printf("%d ",a[i]);       
    }
    printf("\n");   
    system("pause");
    return 0;       
}