歸并排序

基本思想                                                                                                

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

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

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

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

其實(shí)就只有兩步：

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

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

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

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

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

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

代碼實(shí)現(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++];  
}  

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

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

代碼實(shí)現(xiàn)                                                                                                 

//將有二個(gè)有序數(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); //再將二個(gè)有序數(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ù)列長(zhǎng)為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個(gè)合并有序數(shù)列的過(guò)程，時(shí)間復(fù)雜度

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

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

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

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

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

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

若從穩(wěn)定性來(lái)考慮，應(yīng)選取歸并排序，因?yàn)槎雅判蚝涂焖倥判蚨际遣环€(wěn)定的。

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

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