歸并排序

博學，切問，近思--詹子知 (http://blog.csdn.net/zhiqiangzhan) 

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（divide and conquer）的一個非常典型的應用。歸并排序算法以o（nlogn）最壞情形運作時間運作，而所使用的比較次數幾乎是最優的。但它的一個顯著問題就是需要額外的存儲空間來輔助排序，空間複雜度是o(n)的，與quicksort和heapsort相比就遜色了不少，不過也可以實作空間複雜度為o（1）的歸并排序，這将增加比較操作和交換操作的次數。歸并排序可以使用在外部排序上：一般兩路的外部排序是從源檔案裡讀出記憶體大小的一塊，然後在記憶體中排序，在放回檔案裡，這樣生成若幹檔案。然後在從其中兩個檔案中讀資料，按照merge的方式寫到另一個檔案中去。這一步根本用不到輔助空間。唯一可能用到輔助空間的地方是前面的一步，即将一塊資料在記憶體中排序。

歸并操作

歸并操作(merge)，也叫歸并算法，指的是将兩個已經排序的序列合并成一個序列的操作。

歸并操作的工作原理如下：

1.     申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列

2.    設定兩個指針，最初位置分别為兩個已經排序序列的起始位置

3.    比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4.    重複步驟3直到某一指針達到序列尾

5.    将另一序列剩下的所有元素直接複制到合并序列尾

歸并排序

歸并排序具體工作原理如下（假設序列共有n個元素）:

1.     将序列每相鄰兩個數字進行歸并操作（merge），形成floor(n / 2)個序列，排序後每個序列包含兩個元素

2.    将上述序列再次歸并，形成floor(n / 4)個序列，每個序列包含四個元素

3.    重複步驟2，直到所有元素排序完畢  

算法示範1 （非遞歸版本）: 

#include<stdio.h>

#include<stdlib.h> 

void merge(int[], int[], int, int);

void mergesort(int[], int); 

int main(void){

       int a[] = {26, 5, 37, 1, 61, 11, 59, 15, 48, 19};

       int i, len = 10;

       printf("source data is: ");

       for(i = 0; i < len; i++){

              printf("[%2d]", a[i]);

       }

       printf("/n");

       mergesort(a, len);

       printf("after sort, the data is: ");

              printf("%4d", a[i]);

       return 0;

} 

void display(int a[], int k, int n){  

       int i, count = 1;

       for(i = 1; i <= n; i++){

              if((i == n) && (i % (2 * k) != 0)){

                     printf("%4d]", a[i - 1]);

              }else{

                     if((i % (2 * k)) == 1){

                            printf("[%2d", a[i - 1]);

                     }else if(i % (2 * k) == 0){

                            printf("%4d]", a[i -1]);

                     }else{

                            printf("%4d", a[i - 1]);

                     }

              }    

void mergesort(int a[], int n){

       int *t, k = 1;

       if((t = malloc(sizeof(int) * n)) == null){

              printf("allocate array space failure!");

              exit(1);

       }    

       while(k < n){

              merge(a, t, k, n);

              display(a, k, n);

              k <<= 1;

       free(t);

void merge(int src[], int dest[], int k, int n){

       int i, j;

       int s1 = 0, s2 = k, e1, e2;

       int m = 0;

       while(s1 + k < n){

              e1 = s2;

              e2 = (s2 + k < n) ? s2 + k : n;

              for(i = s1, j = s2; i < e1 && j < e2; m++){

                     if(src[i] <= src[j]){

                            dest[m] = src[i++];

                            dest[m] = src[j++];

                     }                  

              }

              while(i < e1){

                     dest[m++] = src[i++];

              while(j < e2){

                     dest[m++] = src[j++];

              s1 = e2;

              s2 = s1 + k;

       for(i = 0; i < n; i++){

              src[i] = dest[i];

算法示範2（遞歸版本）:

#include<stdlib.h>  

void merge(int a[], int l, int m, int r){

       int* t;

       int i = l, j = m + 1, k = 0;

       if((t = malloc(sizeof(int) * (r - l + 1))) == null){

              printf("allocate memory failure!");

       while(i <= m && j <= r){

              if(a[i] > a[j]){

                     t[k++] = a[j++];

                     t[k++] = a[i++];

       if(i > m){

              while(j <= r){

       }else{

              while(i <= m){

       for(i = l, k = 0; i <= r; i++, k++){

              a[i] = t[k];

}

void sort(int a[], int l, int r){

       int m;

       if(l < r){

              m = (l + r) / 2;      

              sort(a, l, m);

              sort(a, m + 1, r);

              merge(a, l, m, r);

}  

       sort(a, 0, n-1);