堆排序，學(xué)習(xí)了整整一天才把這個(gè)排序徹底搞明白……

首先第一點(diǎn)，堆排序是直接選擇排序的一種優(yōu)化排序算法。由于直接排序算法的遍歷次數(shù)過多，導(dǎo)致直接排序算法的時(shí)間復(fù)雜度為O(N^2)，不適合排大量數(shù)據(jù)，堆排序應(yīng)運(yùn)而生。

堆排序（Heap Sort）進(jìn)行的改進(jìn)是能夠保存一部分在每次遍歷整個(gè)數(shù)組找出最大（小）值、次大（小）值，主要利用的就是完全二叉樹這種數(shù)據(jù)結(jié)構(gòu)。（后面說是如何保存這些數(shù)據(jù)的）

堆排序最重要的知識(shí)點(diǎn)無非兩個(gè)：

1、向下調(diào)整算法

2、堆的邏輯結(jié)構(gòu)是一棵完全二叉樹

先從定義開始學(xué)習(xí)：

向下調(diào)整算法：顧名思義就是從上到下進(jìn)行數(shù)據(jù)的調(diào)整，可以將完全二叉樹調(diào)整為最大堆與最小堆（這兩種堆也同時(shí)被稱為“大頂堆”和“小頂堆”）這種算法的前提是：根節(jié)點(diǎn)的左右兩棵子樹均以建成最大（小）堆。

最大堆：所有的父節(jié)點(diǎn)都大于子結(jié)點(diǎn)

最小堆：所有的父節(jié)點(diǎn)都小于子結(jié)點(diǎn)

完全二叉樹：從上到下、從左到右依次排列的一種樹（即從第一層到第n-1層都是滿的，只有第n層不滿且從左到右排列數(shù)據(jù)）

（以建小堆為例）看一種典型的示例：

向下調(diào)整算法就是處理這種完全二叉樹的一種算法，經(jīng)過這種算法可將此數(shù)組建成最小堆。

先從根節(jié)點(diǎn)開始處理：

9 為父（根）節(jié)點(diǎn)，0，1都是其子節(jié)點(diǎn)，0 < 1；所以將0與9作一次交換；父節(jié)點(diǎn)同時(shí)下移至子節(jié)點(diǎn)，子節(jié)點(diǎn)變?yōu)樾赂腹?jié)點(diǎn)的子節(jié)點(diǎn)：（p = parent, c = child）

9 為父（根）節(jié)點(diǎn)，2，3都是其子節(jié)點(diǎn)，2 < 3；所以將2與9作一次交換；父節(jié)點(diǎn)同時(shí)下移至子節(jié)點(diǎn)，子節(jié)點(diǎn)變?yōu)樾赂腹?jié)點(diǎn)的子節(jié)點(diǎn)：

9 為父（根）節(jié)點(diǎn)，6 是其子節(jié)點(diǎn)，6< 9；所以將6與9作一次交換；父節(jié)點(diǎn)同時(shí)下移至子節(jié)點(diǎn)，子節(jié)點(diǎn)變?yōu)樾赂腹?jié)點(diǎn)的子節(jié)點(diǎn)：

發(fā)現(xiàn)此時(shí)新的子節(jié)點(diǎn)已經(jīng)越界，故停止向下調(diào)整；整個(gè)堆現(xiàn)已完成建堆成為最小堆！

這便是所謂的“向下調(diào)整算法”。

了解了以上知識(shí)后，還得知道父節(jié)點(diǎn)與子結(jié)點(diǎn)的表示方法：

leftchild = parent * 2 + 1;

rightchild = parent * 2 + 2;

parent = (leftchild - 1) /2;

下面代碼實(shí)戰(zhàn)：

//向下調(diào)整：
//根節(jié)點(diǎn)左右子樹必須已經(jīng)成堆
void AdjustDown(int a[], int n, int parent)
{
	int child = parent * 2 + 1;
	//左孩子不能越界
	while (child < n)
	{
		//如果只有左孩子，那就不用判斷兩個(gè)孩子的大小，直接判斷左孩子和父親的大小
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		//向下調(diào)整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

簡(jiǎn)單的交換函數(shù)：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

堆排序的思想現(xiàn)在已經(jīng)有了雛形：

將一個(gè)數(shù)組想象成堆，建堆，然后將堆頂最大（小）值置于堆底作為有序數(shù)據(jù)，這時(shí)會(huì)新形成一個(gè)堆，比之前的堆少一個(gè)數(shù)據(jù)，并且只有根節(jié)點(diǎn)的那棵小樹未成堆，左右子樹已形成大（小）堆，用一次向下調(diào)整算法即可將新堆再次建成最大（小）堆。

現(xiàn)在的問題是我們選擇建一個(gè)最大堆還是最小堆呢？

我們不妨假設(shè)建了最小堆，也即上面我們剛剛構(gòu)建好的堆：

不難發(fā)現(xiàn)這樣是將最小值篩選出來，再向下調(diào)整，選出次小值，這樣一來會(huì)得到降序的一個(gè)數(shù)組，反之，若使用最大堆，會(huì)得到一個(gè)升序的數(shù)組。

我們建大堆來得到一個(gè)升序數(shù)組，現(xiàn)有此無序數(shù)組：

//數(shù)組
int a[] = { 5,9,6,1,7,2,0,4,3,8 };
//元素個(gè)數(shù)
int n = (int)sizeof(a) / sizeof(a[0]);

第一步就是建堆：

我們會(huì)發(fā)現(xiàn)：這樣“不聽話”的數(shù)組顯然不符合向下調(diào)整算法的前提條件，所以我們可以從這個(gè)數(shù)組中找能用這個(gè)算法的地方：從后向前去調(diào)整，最后一個(gè)葉子節(jié)點(diǎn)？一個(gè)數(shù)據(jù)，不需要調(diào)整；

最后一個(gè)父節(jié)點(diǎn)？他將會(huì)有0-2個(gè)子節(jié)點(diǎn)，而且只有這三個(gè)數(shù)據(jù)，不管怎么“不聽話”，這個(gè)最小單位會(huì)滿足“根的左右子樹成堆”的這個(gè)條件，下一次再將這個(gè)父節(jié)點(diǎn)-1，即可實(shí)現(xiàn)對(duì)前一個(gè)父節(jié)點(diǎn)進(jìn)行向下調(diào)整，循環(huán)此步驟直至真正的根節(jié)點(diǎn)，這時(shí)整個(gè)數(shù)組會(huì)被建成最大堆。

void HeapSort(int a[], int n)
{
    //建堆
	int parent = (n - 1 - 1) / 2;
	while (parent >= 0)
	{
		AdjustDown(a, n, parent);
		parent--;
	}
}

第二步就是排序：

建成堆后，我們需要進(jìn)行數(shù)據(jù)的交換形成有序數(shù)據(jù)區(qū)。

void HeapSort(int a[], int n)
{
    //建堆
	int parent = (n - 1 - 1) / 2;
	while (parent >= 0)
	{
		AdjustDown(a, n, parent);
		parent--;
	}
	//已經(jīng)成最大堆,不用再從最后一個(gè)父節(jié)點(diǎn)建堆
	//每次只用改變根節(jié)點(diǎn)的堆（根左右堆已為最大堆）
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

堆排序完畢！

整個(gè)代碼分享：

#include <stdio.h>
void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//向下調(diào)整：
//根節(jié)點(diǎn)左右子樹必須已經(jīng)成堆
void AdjustDown(int a[], int n, int parent)
{
	int child = parent * 2 + 1;
	//左孩子不能越界
	while (child < n)
	{
		//如果只有左孩子，那就不用判斷兩個(gè)孩子的大小，直接判斷左孩子和父親的大小
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		//向下調(diào)整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int a[], int n)
{
	int parent = (n - 1 - 1) / 2;
	while (parent >= 0)
	{
		AdjustDown(a, n, parent);
		parent--;
	}
	//已經(jīng)成最大堆,不用再從最后一個(gè)父節(jié)點(diǎn)建堆
	//每次只用改變根節(jié)點(diǎn)的堆（根左右堆已為最大堆）
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
void print(int* a, int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
int main()
{
	int a[] = { 5,9,6,1,7,2,0,4,3,8 };
	int n = (int)sizeof(a) / sizeof(a[0]);
	HeapSort(a, n);
	print(a, n);
	return 0;
}