閱讀407 返回首頁    go 阿裏雲 go 技術社區[雲棲]

歸並排序

博學，切問，近思--詹子知 (https://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("/n");

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

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

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

       }

       printf("/n");

       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]);

                     }

              }    

       }

       printf("/n");

} 

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++];

                     }else{

                            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<stdio.h>

#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!");

              exit(1);

       }

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

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

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

              }else{

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

              }

       }

       if(i > m){

              while(j <= r){

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

              }

       }else{

              while(i <= m){

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

              }

       }

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

              a[i] = t[k];

       }

       free(t);

}

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);

       }

}  

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

       sort(a, 0, n-1);

}

 

最後更新：2017-04-02 04:00:24

  上一篇：go Oracle數據安全解決方案（1）——透明數據加密TDE
  下一篇：go C#二進製輸出數據