欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++堆排序算法的實(shí)現(xiàn)方法

 更新時(shí)間:2014年08月14日 09:18:52   投稿:shichen2014  
這篇文章主要介紹了C++堆排序算法的實(shí)現(xiàn)方法,很經(jīng)典的算法,需要的朋友可以參考下

 本文實(shí)例講述了C++實(shí)現(xiàn)堆排序算法的方法,相信對(duì)于大家學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法會(huì)起到一定的幫助作用。具體內(nèi)容如下:

 首先,由于堆排序算法說起來(lái)比較長(zhǎng),所以在這里單獨(dú)講一下。堆排序是一種樹形選擇排序方法,它的特點(diǎn)是:在排序過程中,將L[n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu),利用完全二叉樹中雙親節(jié)點(diǎn)和孩子節(jié)點(diǎn)之間的內(nèi)在關(guān)系,在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或最?。┑脑?。

一、堆的定義

堆的定義如下:n個(gè)關(guān)鍵字序列L[n]成為堆,當(dāng)且僅當(dāng)該序列滿足:
①L(i) <= L(2i)且L(i) <= L(2i+1)  或者  ②L(i) >= L(2i)且L(i) >= L(2i+1)   其中i屬于[1, n/2]。

滿足第①種情況的堆稱為小根堆(小頂堆),滿足第②種情況的堆稱為大根堆(大頂堆)。在大根堆中,最大元素存放在根結(jié)點(diǎn)中,且對(duì)任一非根結(jié)點(diǎn),它的值小于或等于其雙親結(jié)點(diǎn)值。小根堆則恰恰相反,小根堆的根結(jié)點(diǎn)存放的是最小元素。例如{16, 14, 10, 8, 7, 9, 3, 2}表示的大根堆:

                                 

二、構(gòu)造初始堆

堆排序的關(guān)鍵就是構(gòu)造初始堆。n個(gè)結(jié)點(diǎn)的完全二叉樹中,最后一個(gè)結(jié)點(diǎn)是第n/2(向下取整)個(gè)結(jié)點(diǎn)的孩子。所以構(gòu)造初始堆的流程是:對(duì)第n/2(向下取整)個(gè)結(jié)點(diǎn)為根的子樹進(jìn)行篩選(以大根堆為例,若根結(jié)點(diǎn)的關(guān)鍵字小于左右子女中關(guān)鍵字的較大者,則交換),使該子樹成為堆。之后向前依次對(duì)從n/2-1到1的各結(jié)點(diǎn)為根的子樹進(jìn)行篩選,看該結(jié)點(diǎn)值是否大于其左右子結(jié)點(diǎn)的值,若不是,將左右子結(jié)點(diǎn)中較大值與之交換,交換后可能會(huì)破壞下一級(jí)的堆,于是繼續(xù)采用上述方法構(gòu)造下一級(jí)的堆,直到以該結(jié)點(diǎn)為根的子樹構(gòu)成堆為止。反復(fù)利用上述調(diào)整堆的方法建堆,直到根結(jié)點(diǎn)。

由于在數(shù)組中下標(biāo)從0開始,所以在堆中i的左子結(jié)點(diǎn)為2*i+1,右子結(jié)點(diǎn)為2*i+2。下面是將某個(gè)結(jié)點(diǎn)i向下調(diào)整建堆的算法實(shí)現(xiàn):

void AdjustDown(ElementType A[], int i, int len) 
{ 
  ElementType temp = A[i]; // 暫存A[i] 
   
  for(int largest=2*i+1; largest<len; largest=2*largest+1) 
  { 
    if(largest!=len-1 && A[largest+1]>A[largest]) 
      ++largest;     // 如果右子結(jié)點(diǎn)大 
    if(temp < A[largest]) 
    { 
      A[i] = A[largest]; 
      i = largest;     // 記錄交換后的位置 
    } 
    else 
      break; 
  } 
  A[i] = temp;  // 被篩選結(jié)點(diǎn)的值放入最終位置 
} 
 

建堆,從n/2(向下取整)到1依次對(duì)各結(jié)點(diǎn)向下調(diào)整,當(dāng)然由于數(shù)組下標(biāo)從0開始,所以:

void BuildMaxHeap(ElementType A[], int len) 
{ 
  for(int i=len/2-1; i>=0; --i) // 從i=n/2-1到0,反復(fù)調(diào)整堆 
    AdjustDown(A, i, len); 
} 

三、堆排序

構(gòu)造初始堆成功以后,堆排序的思路就很簡(jiǎn)單了:首先將存放在L[n]中的n個(gè)元素建成初始堆,由于堆本身的特點(diǎn)(以大根堆為例),堆頂元素就是最大值。輸出堆頂元素后,通常將堆底元素送入堆頂,此時(shí)根結(jié)點(diǎn)已不滿足大根堆的性質(zhì),堆被破壞。這時(shí)將堆頂元素向下調(diào)整使其繼續(xù)保持大根堆的性質(zhì),再輸出堆頂元素。如此重復(fù),直到堆中僅剩下一個(gè)元素為止。算法實(shí)現(xiàn)如下:

void HeapSort(ElementType A[], int n) 
{ 
  BuildMaxHeap(A, n);    // 初始建堆 
  for(int i=n-1; i>0; --i) // n-1趟的交換和建堆過程  
  { 
    // 輸出最大的堆頂元素(和堆底元素交換) 
    A[0] = A[0]^A[i]; 
    A[i] = A[0]^A[i]; 
    A[0] = A[0]^A[i]; 
    // 調(diào)整,把剩余的n-1個(gè)元素整理成堆 
    AdjustDown(A, 0, i);   
  } 
} 

四、性能分析

時(shí)間復(fù)雜度:向下調(diào)整的時(shí)間與樹高有關(guān),為O(h)??梢宰C明在元素個(gè)數(shù)為n的序列上建堆,其時(shí)間復(fù)雜度為O(n)。之后還有n-1次向下調(diào)整操作,每次調(diào)整的時(shí)間為O(h),故在最好,最壞和平均情況下,堆排序的時(shí)間復(fù)雜度為O(nlogn)。

空間復(fù)雜度:僅使用了常數(shù)個(gè)輔助單元,空間復(fù)雜度為O(1)。

穩(wěn)定性:不穩(wěn)定。

相關(guān)文章

  • C 語(yǔ)言指針變量的運(yùn)算詳解

    C 語(yǔ)言指針變量的運(yùn)算詳解

    本文主要介紹 C語(yǔ)言指針變量運(yùn)算的知識(shí),這里整理了詳細(xì)的知識(shí)點(diǎn),并附示例代碼,有需要學(xué)習(xí)C語(yǔ)言指針的朋友可以參考下
    2016-08-08
  • 二叉查找樹的插入,刪除,查找

    二叉查找樹的插入,刪除,查找

    以下是對(duì)二叉查找樹的插入與刪除以及查找進(jìn)行了詳細(xì)的介紹,需要的朋友可以 過來(lái)參考下
    2013-09-09
  • C語(yǔ)言數(shù)組實(shí)現(xiàn)三子棋應(yīng)用實(shí)例

    C語(yǔ)言數(shù)組實(shí)現(xiàn)三子棋應(yīng)用實(shí)例

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言數(shù)組實(shí)現(xiàn)三子棋應(yīng)用實(shí)例,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-01-01
  • 零基礎(chǔ)詳解C語(yǔ)言指針進(jìn)階

    零基礎(chǔ)詳解C語(yǔ)言指針進(jìn)階

    在C語(yǔ)言和C++等語(yǔ)言中,數(shù)組元素全為指針變量的數(shù)組稱為指針數(shù)組,指針數(shù)組中的元素都必須具有相同的存儲(chǔ)類型、指向相同數(shù)據(jù)類型的指針變量。指針數(shù)組比較適合用來(lái)指向若干個(gè)字符串,使字符串處理更加方便、靈活
    2022-02-02
  • 如何利用tinyxml操縱xml及注意問題

    如何利用tinyxml操縱xml及注意問題

    這篇博客,我們?cè)敿?xì)講述如何利用tinyxml操縱xml。以及在操作的過程中,我們應(yīng)該注意的問題
    2013-01-01
  • 用C語(yǔ)言實(shí)現(xiàn)貪吃蛇小游戲

    用C語(yǔ)言實(shí)現(xiàn)貪吃蛇小游戲

    這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)貪吃蛇小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • 使用udp發(fā)送>=128K的消息會(huì)報(bào)ENOBUFS的錯(cuò)誤的解決方法

    使用udp發(fā)送>=128K的消息會(huì)報(bào)ENOBUFS的錯(cuò)誤的解決方法

    在項(xiàng)目中選擇了unix域的數(shù)據(jù)報(bào)套接口。在使用過程中碰到了如下,問題:發(fā)送<128K的消息時(shí),客戶、進(jìn)程可以正常收發(fā)消息;發(fā)送>=128K的消息時(shí),發(fā)送端(sendto)返回ENOBUFS的錯(cuò)誤。下面小編來(lái)詳細(xì)說下
    2019-05-05
  • C語(yǔ)言不定長(zhǎng)數(shù)組及初始化方法

    C語(yǔ)言不定長(zhǎng)數(shù)組及初始化方法

    今天小編就為大家分享一篇C語(yǔ)言不定長(zhǎng)數(shù)組及初始化方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧
    2018-07-07
  • c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)

    c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn)

    本文介紹了c++與python實(shí)現(xiàn)二分查找的原理及實(shí)現(xiàn),二分查找指首先將數(shù)組中間值和目標(biāo)值進(jìn)行比較,如果相等則返回;如果不相等,則選擇中間值左邊的一半或者右邊的一半進(jìn)行比較;不斷重復(fù)直到檢索完畢,下文相關(guān)資料需要的朋友可以參考一下
    2022-03-03
  • C語(yǔ)言文件操作函數(shù)freopen詳細(xì)解析

    C語(yǔ)言文件操作函數(shù)freopen詳細(xì)解析

    替換一個(gè)流,或者說重新分配文件指針,實(shí)現(xiàn)重定向。如果stream流已經(jīng)打開,則先關(guān)閉該流。如果該流已經(jīng)定向,則freopen將會(huì)清除該定向。此函數(shù)一般用于將一個(gè)指定的文件打開一個(gè)預(yù)定義的流:標(biāo)準(zhǔn)輸入、標(biāo)準(zhǔn)輸出或者標(biāo)準(zhǔn)出錯(cuò)
    2013-10-10

最新評(píng)論