C++、C#、java算法學習日記06----堆排序思想（HeapSort）

C++、C#、java算法學習日記06----堆排序思想（HeapSort）

上一篇所學的 希爾排序 是對插入排序的一種高效優化，而堆排序則是對選擇排序的一種高效優化，也屬於選擇排序的一種，所以他的基本思想同 直接選擇排序 一樣也就是每次從數列中選出最大或最小的放到末尾或是開頭，但是堆排序的選擇過程要比 直接選擇排序 的選擇過程高效的多，采用了樹形結構來記錄每次的比較結果（可以省略重復的比較），大值總是作為父節點（最終形成大根堆），或是小值總是作為父節點（最終形成小根堆），最後堆頂元素就是最大或最小值。

基本思想：

將待排序數列 array[0....n] 調整為大根堆（這裡我們進行升序排列），也就是將數組調整為一顆父節點總是大於子節點的完全二叉樹，然後將堆頂元素 array[0]（也就是最大值）與末尾元素 array[n] 交換(這樣一交換剛拍好的大根堆就亂了)，再次調整選擇後的數組 array[0...array[n-1]] 為大根堆，經過n-1次這樣的循環後只剩下一個元素array[0]此時升序排序完成。

從上面的描述過程中可知，堆排序主要分為2個部分的循環，

調整堆：

本篇我們以大根堆為例（因為要做升序排序），上面也說了大根堆也就是一顆父節點總是大於子節點的完全二叉樹，所以具有完全二叉樹的所有性質。因此如果父節點為 array[i]，則它的2個子節點為array[2*i+1](左孩子)，array[2*i+2](右孩子)，並且父節點大於左右孩子。

比如將：array[]={16, 7, 3, 20, 17, 8 }調整為大根堆。

首先該數組用完全二叉樹表示為：

從最後一個父節點array[2]開始調整(與array[5]比較，交換)

最終結果：

（大根堆）此時數組array[]={20,17,8,7,16,3}

我們用C++代碼實現為：

#include

using namespace std;

void HeapAdjust(int *array,int nLength)
{
	int i;
	int Child,temp;
	//i為父節點下標，從最後一個父節點到第一個父節點
	for(i=(nLength/2-1);i>=0;i--)
	{
		for(;2*i+1


結果為： 20  17  8  7  16  3
 
首尾交換再調整：
          經過調整堆我們選出最大值也就是堆頂array[0]與array[5]交換，然後將被打亂的堆再經過上面的調整再交換，也就是調用n-1次 HeapAdujust()函數。
 
 
   堆排序的基本思想就是如此了，堆排序適合對海量的數據進行排序，當然了為了使效率更高你還可以定義k叉數，不過思想還是一樣的。下一篇中我們將隨機生成10000個數利用C++、C#、java 實現堆排序並查看用時記錄。