程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++堆排序算法的完成辦法

C++堆排序算法的完成辦法

編輯：關於C++

C++堆排序算法的完成辦法。本站提示廣大學習愛好者：（C++堆排序算法的完成辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是C++堆排序算法的完成辦法正文

本文實例講述了C++完成堆排序算法的辦法，信任關於年夜家進修數據構造與算法會起到必定的贊助感化。詳細內容以下：

起首，因為堆排序算法說起來比擬長，所以在這裡零丁講一下。堆排序是一種樹形選擇排序辦法，它的特色是：在排序進程中，將L[n]算作是一棵完整二叉樹的次序存儲構造，應用完整二叉樹中雙親節點和孩子節點之間的內涵關系，在以後無序區當選擇症結字最年夜（或最小）的元素。

1、堆的界說

堆的界說以下：n個症結字序列L[n]成為堆，當且僅當該序列知足：
①L(i) <= L(2i)且L(i) <= L(2i+1) 或許 ②L(i) >= L(2i)且L(i) >= L(2i+1) 個中i屬於[1, n/2]。

知足第①種情形的堆稱為小根堆（小頂堆），知足第②種情形的堆稱為年夜根堆（年夜頂堆）。在年夜根堆中，最年夜元素寄存在根結點中，且對任一非根結點，它的值小於或等於其雙親結點值。小根堆則恰好相反，小根堆的根結點寄存的是最小元素。例如{16, 14, 10, 8, 7, 9, 3, 2}表現的年夜根堆：

2、結構初始堆

堆排序的症結就是結構初始堆。n個結點的完整二叉樹中，最初一個結點是第n/2（向下取整）個結點的孩子。所以結構初始堆的流程是：對第n/2（向下取整）個結點為根的子樹停止挑選（以年夜根堆為例，若根結點的症結字小於閣下後代中症結字的較年夜者，則交流），使該子樹成為堆。以後向前順次對從n/2-1到1的各結點為根的子樹停止挑選，看該結點值能否年夜於其閣下子結點的值，若不是，將閣下子結點中較年夜值與之交流，交流後能夠會損壞下一級的堆，因而持續采取上述辦法結構下一級的堆，直到以該結點為根的子樹組成堆為止。重復應用上述調劑堆的辦法建堆，直到根結點。

因為在數組中下標從0開端，所以在堆中i的左子結點為2*i+1，右子結點為2*i+2。上面是將某個結點i向下調劑建堆的算法完成：

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;     // 假如右子結點年夜 
    if(temp < A[largest]) 
    { 
      A[i] = A[largest]; 
      i = largest;     // 記載交流後的地位 
    } 
    else 
      break; 
  } 
  A[i] = temp;  // 被挑選結點的值放入終究地位 
}

建堆，從n/2（向下取整）到1順次對各結點向下調劑，固然因為數組下標從0開端，所以：

void BuildMaxHeap(ElementType A[], int len) 
{ 
  for(int i=len/2-1; i>=0; --i) // 從i=n/2-1到0，重復調劑堆 
    AdjustDown(A, i, len); 
}

3、堆排序

結構初始堆勝利今後，堆排序的思緒就很簡略了：起首將寄存在L[n]中的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]; 
    // 調劑，把殘剩的n-1個元素整頓成堆 
    AdjustDown(A, 0, i);   
  } 
}

4、機能剖析

時光龐雜度：向下調劑的時光與樹高有關，為O(h)。可以證實在元素個數為n的序列上建堆，當時間龐雜度為O(n)。以後還有n-1次向下調劑操作，每次調劑的時光為O(h)，故在最好，最壞戰爭均情形下，堆排序的時光龐雜度為O(nlogn)。

空間龐雜度：僅應用了常數個幫助單位，空間龐雜度為O(1)。

穩固性：不穩固。

關於C++