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

 首先，由于堆排序算法說(shuō)起來(lái)比較長(zhǎng)，所以在這里單獨(dú)講一下。堆排序是一種樹(shù)形選擇排序方法，它的特點(diǎn)是：在排序過(guò)程中，將L[n]看成是一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹(shù)中雙親節(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)該序列滿(mǎn)足：
①L(i) <= L(2i)且L(i) <= L(2i+1)  或者  ②L(i) >= L(2i)且L(i) >= L(2i+1)   其中i屬于[1, n/2]。

滿(mǎn)足第①種情況的堆稱(chēng)為小根堆（小頂堆），滿(mǎn)足第②種情況的堆稱(chēng)為大根堆（大頂堆）。在大根堆中，最大元素存放在根結(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)的完全二叉樹(shù)中，最后一個(gè)結(jié)點(diǎn)是第n/2（向下取整）個(gè)結(jié)點(diǎn)的孩子。所以構(gòu)造初始堆的流程是：對(duì)第n/2（向下取整）個(gè)結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選（以大根堆為例，若根結(jié)點(diǎn)的關(guān)鍵字小于左右子女中關(guān)鍵字的較大者，則交換），使該子樹(shù)成為堆。之后向前依次對(duì)從n/2-1到1的各結(jié)點(diǎn)為根的子樹(shù)進(jìn)行篩選，看該結(jié)點(diǎn)值是否大于其左右子結(jié)點(diǎn)的值，若不是，將左右子結(jié)點(diǎn)中較大值與之交換，交換后可能會(huì)破壞下一級(jí)的堆，于是繼續(xù)采用上述方法構(gòu)造下一級(jí)的堆，直到以該結(jié)點(diǎn)為根的子樹(shù)構(gòu)成堆為止。反復(fù)利用上述調(diào)整堆的方法建堆，直到根結(jié)點(diǎn)。

由于在數(shù)組中下標(biāo)從0開(kāi)始，所以在堆中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開(kāi)始，所以：

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)已不滿(mǎ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趟的交換和建堆過(guò)程  
  { 
    // 輸出最大的堆頂元素（和堆底元素交換） 
    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í)間與樹(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)定。

最新評(píng)論