圖說 堆排序，堆排序

圖說 堆排序，堆排序

 用例：

將一組數據從大到小進行排列  10, 16, 18, 12, 11, 13, 15, 17, 14, 19  

　　 size=10

 步驟1.根據數組初始化堆

步驟2.從最後一個根節點（ 下標為(size-1-1)/2 ）開始往第一個根節點遍歷，依次將每個最小子樹排好序，建造一個小堆：

 步驟3.進行堆排序：將堆數組的首位置和末位置的數據交換，縮小范圍 以--size大小的范圍將堆頂數據下調，完成建堆

理解了整個思想，我們就來看代碼：
先實現一個下調函數用來建堆，並對堆進行調整：（本案例是從大到小進行排序，所以建的是小堆；若是要從小到大進行排序，則要按照大堆思想進行實現，對代碼稍微進行改進即可）

//下調
void AdjustDown(int *array, int parent, int size) 
{
	int left = parent * 2 + 1;
	int right = left + 1;
	while (left < size)
	{
		// 比較左右孩子，保證下標left為最小的節點下標
		if (right <size && array[right] < array[left])
		{
			left = right;
		}
		// 如果父節點大於左右孩子中較小的節點時，就交換這兩個節點，要保證兩個子節點都大於父節點
		if (left<size && array[parent]>array[left])
		{
			// 交換之後還需繼續 將相對較大的數循環向下調
			swap(array[left], array[parent]);
			parent = left;
			left = parent * 2 + 1;
			right = left + 1;
		}
		else
		{
			break;
		}
	}
}

　　堆排序：按照圖說的步驟來寫代碼，首先要初始化一個堆數組並對它進行排序，之後再一步步將堆頂與有效堆尾數據進行交換，並逐漸縮小堆的size，一組有序的數據就排好了！

//堆排序
int* HeapSort(int *heap, int size)
{
	for (int start = (size - 1 - 1) / 2; start >= 0; start--)
	{
		AdjustDown(heap, start, size);
	}
	for (int i = size - 1; i >= 0; --i)
	{
		swap(heap[0], heap[i]);
		AdjustDown(heap, 0, i);
	}
	return heap;
}