<meter id="pryje"><nav id="pryje"><delect id="pryje"></delect></nav></meter>
          <label id="pryje"></label>

          新聞中心

          比較型排序算法總結(jié)

          作者: 時(shí)間:2016-12-01 來(lái)源:網(wǎng)絡(luò) 收藏
          排序是算法中最基礎(chǔ)的問(wèn)題之一,經(jīng)典的排序算法是前人不斷總結(jié)得到的,基于比較的方法是比較直觀的方式,主要存在插入法排序、堆排序、增量排序(shell排序)、歸并排序、快速排序,每一種排序算法都有自己的優(yōu)缺點(diǎn),比如插入法排序適用于那些長(zhǎng)度短的排序,對(duì)于長(zhǎng)的表,有些愛莫能助啊,堆排序主要是依據(jù)了二叉堆的特性,但是創(chuàng)建堆的過(guò)程也是一個(gè)復(fù)雜的問(wèn)題,增量排序的過(guò)程是一個(gè)不斷精確的過(guò)程,但是目前也只是一個(gè)經(jīng)驗(yàn)方式。歸并排序是一個(gè)遞歸的問(wèn)題,采用分治的思想實(shí)現(xiàn),但是這種算法需要額外的存儲(chǔ)空間,快速排序雖然是實(shí)踐中比較常用的算法,但是對(duì)于有序的數(shù)組采用快速排序就是災(zāi)難。比較型算法的時(shí)間復(fù)雜度最優(yōu)也只能到達(dá)O(NlogN)。

          插入排序算法:該算法的復(fù)雜度為O(N^2),需要比對(duì)N-1趟,最壞情況下,每一趟比對(duì)的元素個(gè)數(shù)會(huì)隨著i的增加而增加。比如進(jìn)行到了第k+1趟,實(shí)際上就是假設(shè)了前k個(gè)元素是有序的,這時(shí)候只需要將a[k+1]與a[k]比較,如果a[k+1]大于a[k]則說(shuō)明a[k+1]是目前最大的數(shù),如果a[k+1] < a[k].這時(shí)說(shuō)明a[k]的位置不對(duì),需要往后移動(dòng),也就是a[k+1]中保存a[k]的值,可以將a[k+1]的值與a[k]交換。然后比較a[k]與a[k-1],直到找到該元素的合適位置。

          本文引用地址:http://www.ex-cimer.com/article/201612/324512.htm

          void insertSort(int *a, int size)
          {
          int i = 0, j = 0, tmp = 0;
          for(i = 1; i < size; ++ i)
          {
          tmp = a[i];
          for(j = i; j > 0 && tmp < a[j-1]; --j)
          a[j] = a[j - 1];
          a[j] = tmp;
          }
          }

          增量排序(shell 排序):該算法的復(fù)雜度要略小于插入排序算法,但是也基本上認(rèn)為是亞O(N^2)。實(shí)現(xiàn)的基本過(guò)程如下,選擇一個(gè)較大的增量gap,一般選擇為數(shù)組長(zhǎng)度的一般作為起始的增量。然后從當(dāng)前增量作為起始下標(biāo)開始訪問(wèn),比較a[i]和a[i-gap],如果a[i] a[0],這是已經(jīng)處理過(guò)的。如果a[i] > a[i-gap]則不處理。減小gap,一般去gap = gap/2。重新進(jìn)行上面的操作,直到gap = 1,因?yàn)檫@時(shí)候已經(jīng)滿足a[i]

          voidshellSort(int *a, int size)
          {
          int i = 0, j = 0, gap = 0.
          int tmp = 0;

          /*選擇合適的增量*/
          for(gap = size / 2; gap > 0; gap /= 2 )
          {
          /*以增量為下標(biāo)進(jìn)行比較*/
          for( i = gap ; i < size ; ++ i)
          {
          /*找到比較數(shù)的位置*/
          tmp = a[i];
          for(j = i; j >= gap && tmp < a[j - gap]; j -= gap)
          a[j] = a[j - gap];/*更新a[j-gap]的位置*/
          a[j] = tmp; /*找到比較數(shù)的位置*/
          }
          }
          }

          堆排序:堆排序的實(shí)現(xiàn)主要是采用了最小堆或者最大堆的特性,堆中的根元素肯定是最小元素或者最大元素,刪除其中的根元素實(shí)質(zhì)上就找到了最大/最小值。這樣通過(guò)N次刪除就找到了一個(gè)有序序列。我們知道在二叉堆中刪除和插入操作采用了上慮和下慮的方式,每次刪除和插入操作的時(shí)間復(fù)雜度為O(logN)。但是堆排序存在一個(gè)堆的創(chuàng)建問(wèn)題,這個(gè)創(chuàng)建是非常的浪費(fèi)時(shí)間的,時(shí)間復(fù)雜度為O(N),這樣一個(gè)堆排序的操作事件大約為O(NlogN)。相比前面的兩種方式要快速。實(shí)現(xiàn)的過(guò)程如下,分配一個(gè)新的內(nèi)存空間,遍歷元素N,創(chuàng)建一個(gè)二叉堆數(shù)組,然后執(zhí)行N次刪除操作,刪除的元素添加到原來(lái)的內(nèi)存空間中,實(shí)現(xiàn)了數(shù)組的排序操作,這種方式時(shí)間復(fù)雜度上有所減小,但是空間復(fù)雜度上卻有了很大的增加,存儲(chǔ)容量增加了近一倍。

          聰明的解決方式根據(jù)堆的性質(zhì),刪除一個(gè)元素就會(huì)釋放最后的一個(gè)存儲(chǔ)單元,這時(shí)候?qū)h除的元素保存到釋放存儲(chǔ)單元中,然后刪除一個(gè)元素就保存到釋放的內(nèi)存中去,就能避免存儲(chǔ)量增加的問(wèn)題。但是這時(shí)候出現(xiàn)的序列就是一個(gè)反序,但總歸是有序序列。當(dāng)然也可以通過(guò)創(chuàng)建(Max)堆來(lái)得到min序列,創(chuàng)建(Min)堆來(lái)得到max序列。因此堆排序的基本模型就是創(chuàng)建一個(gè)堆,刪除堆元素的操作過(guò)程。

          堆排序是非常穩(wěn)定的算法,他平均使用的比較只比最壞情形下指出的略少,堆排序總是使用至少NlogN-O(N)次排序,而且存在能夠到達(dá)這個(gè)界的輸入數(shù)據(jù)。

          void max_heapify(int *a,int index, int size)
          {
          int child = LEFTSON(index);

          int tmp = a[index];

          for(; LEFTSON(index) < size ; index = child)
          {
          child = LEFTSON(index);
          if(child != size - 1 && a[child] < a[child + 1])
          child ++;

          /***************************
          * 提升兒子到父結(jié)點(diǎn),
          * 兒子結(jié)點(diǎn)的位置上存在空穴,
          * 需要繼續(xù)比較
          **************************/
          if(a[child] > tmp)
          a[index] = a[child];
          else/*不需要提升*/
          break;
          }
          /*保存結(jié)點(diǎn)的位置找到*/
          a[index] = tmp;
          }

          void Build_Maxheap(int *a, int size)
          {
          int step = 0;

          /***************************************
          * (size-1)/2實(shí)質(zhì)是找到a[size-1]的父結(jié)點(diǎn),
          * 也就是倒數(shù)第二層,堆的創(chuàng)建過(guò)程是一個(gè)
          * 由低層到高層逐漸創(chuàng)建的過(guò)程
          **************************************/
          for(step = (size - 1) / 2 ; step >= 0; -- step)
          max_heapify(a, step, size);
          }

          void heapSort(int *a, int size)
          {
          int i = 0;
          /*創(chuàng)建堆*/
          Build_Maxheap(a,size);

          for(i = size - 1; i > 0; --i)
          {
          /*swap(a[i],a[0])*/
          a[i] = a[i] + a[0];
          a[0] = a[i] - a[0];
          a[i] = a[i] - a[0];
          /*更新堆的結(jié)構(gòu)*/
          max_heapify(a,0,i);
          }
          }

          歸并排序:該算法的時(shí)間復(fù)雜度為O(NlogN),使用的比較次數(shù)幾乎是最優(yōu)的,是遞歸算法的經(jīng)典例子。

          這個(gè)算法的基本操作是合并兩個(gè)已經(jīng)排序的表,因?yàn)檫@兩個(gè)表是已經(jīng)排序的,所以若將輸出放到第三個(gè)表中則該算法可以通過(guò)對(duì)輸入數(shù)據(jù)一趟排序來(lái)完成。基本的合并算法是取兩個(gè)輸入數(shù)組A和B,一個(gè)輸出數(shù)組C以及3個(gè)計(jì)數(shù)器(Actr、Bctr、Cctr),他們開始于對(duì)應(yīng)數(shù)組的開始端,A[Actr]和B[Bctr]的較小者復(fù)制到C[ctr]中的一下一個(gè)位置,相關(guān)的計(jì)數(shù)器向前推進(jìn)一步,當(dāng)兩個(gè)輸入表有一個(gè)用完,則將另一個(gè)表中剩余的部分拷貝到C中。

          由于該算法的前提是兩個(gè)已經(jīng)排序的表,但實(shí)際上的輸入肯定不能滿足條件,因此需要采用分治策略,所謂“分”就是將輸入表分成兩個(gè)表進(jìn)行處理,對(duì)兩個(gè)表分別采用分治進(jìn)行排序。所謂“治”就是按照上述的算法合并兩個(gè)排序表得到一個(gè)完整的排序表。由上面的分析可以知道,每一次分治都存在分開和合并操作,是經(jīng)典的遞歸問(wèn)題。需要注意的是在歸并算法中臨時(shí)數(shù)組的處理問(wèn)題,采用動(dòng)態(tài)存儲(chǔ)的方式可能要簡(jiǎn)單好一些,但是需要注意內(nèi)存的釋放,避免內(nèi)存泄露。

          void mergeSort(int * a, int left, int right)
          {
          int i = 0;
          int *atmp = NULL;
          int *Actr = NULL, *Bctr = NULL, *Cctr = NULL;

          /*遞歸退出條件*/
          if(left >= right)
          return;

          atmp = (int *)calloc((right - left + 1) / 2,sizeof(int));
          if(NULL == atmp)
          return;

          for(i = 0; i < (right - left + 1) / 2 ; ++ i)
          atmp[i] = a[left + i];

          mergeSort(atmp,0,i - 1);
          mergeSort(a, left + i, right);

          Actr = atmp;
          Bctr = a + left + i;
          Cctr = a + left;

          while(Actr != atmp + i && Bctr != a + right + 1)
          {
          if(*Actr <= *Bctr)
          *Cctr++ = *Actr++;
          else
          *Cctr++ = *Bctr++;
          }
          while(Actr != atmp + i)
          *Cctr ++ = *Actr++;
          while(Bctr != a + right + 1)
          *Cctr ++ = *Bctr ++;

          free(atmp);
          atmp = NULL;
          }

          歸并算法的時(shí)間復(fù)雜度的推導(dǎo)過(guò)程:

          其中時(shí)間復(fù)雜度公式滿足如下的等式T(N)=2T(N/2)+N,其中的N為合并操作的時(shí)間,推導(dǎo)過(guò)程如下:


          歸并排序存在的問(wèn)題是,它很難應(yīng)用于主存排序,主要問(wèn)題在于合并兩個(gè)排列的表需要線性附加內(nèi)存,在整個(gè)算法中還需要花費(fèi)將數(shù)據(jù)復(fù)制到臨時(shí)數(shù)組在復(fù)制回來(lái)這樣的一些附加操作,其結(jié)果是嚴(yán)重減慢了排序的速度。

          快速排序:是實(shí)踐中最快的已知排序算法,它的平均運(yùn)行時(shí)間是O(NlogN),算法之所以快是因?yàn)榉浅>珶捄透叨葍?yōu)化的內(nèi)部循環(huán),但是最壞的性能是O(N^2),將堆排序與快速排序結(jié)合,可以在堆排序的O(NlogN)最壞運(yùn)行時(shí)間下,得到幾乎所有輸入的最快運(yùn)行時(shí)間。

          快速排序也是一種分治的遞歸算法,通常包括4個(gè)步驟:

          1、如果數(shù)組S中元素個(gè)數(shù)為0或者1個(gè),則直接返回

          2、取數(shù)組S中的一個(gè)數(shù)v作為樞紐元。

          3、將數(shù)組S-v劃分成兩個(gè)不相交的集合,其中S1:x <= v, S2: x > v.這一步需要注意不要寫成是S1:x<=v,S2:x>=v,能減少很多的麻煩。

          4、返回{quickSort(S1) , v, quickSort(S2)}。

          上面的四步就完成了數(shù)組的快速排序,可見快速排序也是一個(gè)遞歸的過(guò)程,需要將多個(gè)子集進(jìn)行。

          快速排序的實(shí)現(xiàn)主要是第三步的實(shí)現(xiàn),如何實(shí)現(xiàn)將數(shù)據(jù)分成兩個(gè)集合的操作。實(shí)現(xiàn)的方式如下:

          假設(shè)選擇的樞紐元pivot是數(shù)組的開始值a[0],那么將兩個(gè)下標(biāo)i,j分別表示數(shù)組的第1個(gè)數(shù)a[1](i = 1)和最后一個(gè)數(shù)a[N](j = N),如果i < j,也就是數(shù)組長(zhǎng)度大于2個(gè)時(shí),將指向第一個(gè)數(shù)a[1]和樞紐元pivot進(jìn)行比較,如果小于等于樞紐元?jiǎng)t說(shuō)明當(dāng)前值是S1集合的,因此不需要移動(dòng),增加i指向下一個(gè)數(shù)a[2],直到找到大于樞紐元的數(shù)a[i],則i暫停增加,這時(shí)操作另一個(gè)下標(biāo)j,比較j表征的數(shù)a[j]是否大于樞紐元pivot,如果大于則說(shuō)明當(dāng)前的數(shù)屬于S2,不需要移動(dòng),減小j,直到找到小于等于樞紐元的數(shù)a[j],如果i < j,則說(shuō)明這兩個(gè)數(shù)是需要改變位置的,因此調(diào)整兩個(gè)數(shù)的位置swap(a[p],a[q]),然后接著上面的方法移動(dòng)兩個(gè)下標(biāo),并完成相應(yīng)的交換操作,當(dāng)兩個(gè)下標(biāo)表征相同的位置(j == i,這種情況是pivot = a[i])或者j < i(這種情況是不存在相同元素pivot != a[i])以后,說(shuō)明集合分類操作已經(jīng)完成,后一個(gè)j指向的位置就是當(dāng)前樞紐元的位置,這時(shí)候小于j的下標(biāo)的數(shù)據(jù)就是S1,而大于j的下標(biāo)的數(shù)據(jù)就是S2。因此還需要將樞紐元a[0]與a[j]交換,得到樞紐元的位置。對(duì)于這種數(shù)組元素較大的情況,此時(shí)的j一般認(rèn)為都是滿足a[j] <= pivot。(等于的情況也是可能存在的)。


          上一頁(yè) 1 2 下一頁(yè)

          關(guān)鍵詞: 比較型排序算

          評(píng)論


          技術(shù)專區(qū)

          關(guān)閉
          看屁屁www成人影院,亚洲人妻成人图片,亚洲精品成人午夜在线,日韩在线 欧美成人 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();