歸并排序

基本思想                                                                                                

歸并排序是建立在二路歸并和分治法的基礎(chǔ)上的一個高效排序算法,將已有序的子序列合并，得到完全有序的序列；即先使每個子序

列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

將待排序序列R[0...n-1]看成是n個長度為1的有序序列，將相鄰的有序表成對歸并，得到n/2個長度為2的有序表；將這些有序序列

再次歸并，得到n/4個長度為4的有序序列；如此反復(fù)進(jìn)行下去，最后得到一個長度為n的有序序列。所以呢，我們總結(jié)一下歸并排序

其實就只有兩步：

分解:將有序序列不斷地分裂，直到每個區(qū)間都只有一個數(shù)據(jù)為止.

合并:將兩個區(qū)間合并為一個有序的區(qū)間，一直合并知道只有一個區(qū)間為止.

圖是我偷來的，但是學(xué)習(xí)是認(rèn)真的.

分解的過程我們很容易想明白的，用遞歸就可以.但是我們今天最主要的步驟是合并，你要將兩個區(qū)間合并為一個有序的區(qū)間你會怎么思考呢？

這個非常簡單，只要從比較二個數(shù)列的第一個數(shù)，誰小就先取誰，取了后就在對應(yīng)數(shù)列中刪除這個數(shù)。然后再進(jìn)行比較，如果有數(shù)

列為空，那直接將另一個數(shù)列的數(shù)據(jù)依次取出即可。

代碼實現(xiàn):

//將有序數(shù)組a[]和b[]合并到c[]中  
void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
  int i, j, k;  
  
  i = j = k = 0;  
  while (i < n && j < m)  
  {  
    if (a[i] < b[j])  
      c[k++] = a[i++];  
    else  
      c[k++] = b[j++];   
  }  
  
  while (i < n)  
    c[k++] = a[i++];  
  
  while (j < m)  
    c[k++] = b[j++];  
}  

其實我們發(fā)現(xiàn)這種做法效率其實還是蠻高的，效率達(dá)到了O（N）.現(xiàn)在我們解決了合并的問題.

現(xiàn)在總的來看一下歸并排序的做法,通過先遞歸的分解數(shù)列(將數(shù)列分解成只有一個元素的區(qū)間)，再合并數(shù)列就完成了歸并排序。

代碼實現(xiàn)                                                                                                 

//將有二個有序數(shù)列a[first...mid]和a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
  int i = first, j = mid + 1;  
  int m = mid,  n = last;  
  int k = 0;  
    
  while (i <= m && j <= n)  
  {  
    if (a[i] <= a[j])  
      temp[k++] = a[i++];  
    else  
      temp[k++] = a[j++];  
  }  
    
  while (i <= m)  
    temp[k++] = a[i++];  
    
  while (j <= n)  
    temp[k++] = a[j++];  
    
  for (i = 0; i < k; i++)  
    a[first + i] = temp[i];  
}  
void mergesort(int a[], int first, int last, int temp[])  
{  
  if (first < last)  
  {  
    int mid = (first + last) / 2;  
    mergesort(a, first, mid, temp);  //左邊有序  
    mergesort(a, mid + 1, last, temp); //右邊有序  
    mergearray(a, first, mid, last, temp); //再將二個有序數(shù)列合并  
  }  
}  
  
bool MergeSort(int a[], int n)  
{  
  int *p = new int[n];  
  if (p == NULL)  
    return false;  
  mergesort(a, 0, n - 1, p);  
  delete[] p;  
  return true;  
}  

總結(jié)                                                                                                  

歸并排序的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個合并有序數(shù)列的過程，時間復(fù)雜度

可以記為O(N)，故一共為O(N*logN)。因為歸并排序每次都是在相鄰的數(shù)據(jù)中進(jìn)行操作，所以歸并排序在O(N*logN)的幾種排序方

法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。

算法名稱　　最差時間復(fù)雜度　　平均時間復(fù)雜度　　最優(yōu)時間復(fù)雜度　　空間復(fù)雜度　　穩(wěn)定性

歸并排序　　　　O(NlogN)　　　　O(NlogN)              O(NlogN)　　　　   O(n)　　　     穩(wěn)定

所有排序當(dāng)中用的最多的就是堆排序，快速排序，歸并排序.

若從空間復(fù)雜度來考慮：首選堆排序，其次是快速排序，最后是歸并排序。

若從穩(wěn)定性來考慮，應(yīng)選取歸并排序，因為堆排序和快速排序都是不穩(wěn)定的。

若從平均情況下的排序速度考慮，應(yīng)該選擇快速排序。

以上就是數(shù)據(jù)結(jié)構(gòu)中歸并排序的實例詳解，如有疑問請留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！