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)。
穩固性：不穩固。
