快捷導(dǎo)航

歸并排序的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)代碼

更新時(shí)間：2013年08月23日 10:16:21 作者：

以下是對(duì)歸并排序的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)代碼進(jìn)行了詳細(xì)的介紹，需要的朋友可以過(guò)來(lái)參考下

歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。值得注意的是歸并排序是一種穩(wěn)定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。

算法描述
歸并操作的工作原理如下：
第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

時(shí)間復(fù)雜度：
時(shí)間復(fù)雜度為O(nlogn) 這是該算法中最好、最壞和平均的時(shí)間性能。
空間復(fù)雜度為 O(n)
比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1。
賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)
歸并排序比較占用內(nèi)存，但卻效率高且穩(wěn)定的算法。
(以上摘抄自百度百科)

代碼實(shí)現(xiàn)
自頂向上實(shí)現(xiàn)：
//使用輔助數(shù)組實(shí)現(xiàn)歸并的過(guò)程

復(fù)制代碼代碼如下:

void MergeSort(int *aux, int *data, int l, int m, int h)
{
 int k=0, i=l, j=m+1;

 for(k=l; k<=h; k++)
 {
  if(i>m)     aux[k]=data[j++];
  else if(j>h)    aux[k]=data[i++];
  else if(data[i]<data[j])        aux[k]=data[i++];
  else    aux[k]=data[j++];
 }
 for(k=l; k<=h; k++)
  data[k]=aux[k];
}

用遞歸實(shí)現(xiàn)排序的過(guò)程(自頂向下歸并)

復(fù)制代碼代碼如下:

void Sort(int *aux, int *data, int l, int h)
{
 if(l<h)
 {
  int m=l+(h-l)/2;
  Sort(aux, data, l, m);
  Sort(aux, data, m+1, h);
  MergeSort(aux,data, l, m, h);
 }
}

用非遞歸實(shí)現(xiàn)排序的過(guò)程(自底向上歸并)

復(fù)制代碼代碼如下:

void NonRerMerSort(int *aux, int *data, int l, int h)
{
 int i=l, j;
 for(i=l; i<=h; i=2*i)
 {
  for(j=l; j<=h-i; j+=2*i)
   MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
 }
}

您可能感興趣的文章: