用C++實現堆排序

堆數據結構是一種數組對象，它可以被視為一顆完全二叉樹結構。

最大堆：每個父節點都大于孩子節點。

最小堆：每個父節點都小于孩子節點。

堆排序的思想：對于給定的N個數據，初始時把這些記錄看作是一顆順序存儲的二叉樹，然后將其調整為一個最大堆，然后將堆的最后一個元素與堆頂元素（即二叉樹的根節點）進行交換，堆的最后一個元素即為最大記錄；接著將（N-1）個元素（即不包括最大記錄）重新調整為一個最大堆，再將堆頂元素與堆的最后一個元素進行交換后得到次大的記錄，重復該過程直到調整的堆只剩下一個元素為止，該元素即為最小記錄，此時可得到一個有序序列。

堆排序主要包括兩個過程：一是構建堆；二是交換堆頂元素與最后一個元素的位置。

程序如下：

#include<iostream>
#include<assert.h>
using namespace std;

void AdjustDown(int *array,int size,int root)
{
	assert(array);
	int child = 2 * root + 1;
	while (child < size)
	{
		if (child + 1 < size&&array[child] < array[child + 1])
		{
			++child;
		}
		if (array[child]>array[root])
		{
			swap(array[root],array[child]);
			root = child;
			child = 2 * root + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int *array, int size, int root)
{
	//找到第一個非葉子節點構建堆
	for (int i = (size - 2) / 2; i >= 0; --i)
	{
		AdjustDown(array,size,0);
	}
	for (int i = 0; i < size; ++i)
	{
		swap(array[0],array[size-1-i]);
		AdjustDown(array,size-1-i,0);
	}
}

int main()
{
	int array[10] = {12,10,16,6,8,9,11,9,7,13};
	for (int i = 0; i < 10; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	HeapSort(array,10,0);
	for (int i = 0; i < 10; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl;
	return 0;
}

程序運行結果：

        堆排序方法對記錄較少的文件效果一般，但對于 記錄較多的文件還是很有效的，其運行時間主要耗費在創建堆和反復調整堆上。堆排序即使在最壞的情況下，其時間復雜度也為O（N*logN）。