在瀏覽本篇博文的小伙伴可先淺看一下上篇堆和堆排序的思想：

戳這里可跳轉上篇文~~

1.堆排序優(yōu)化算法

要堆堆排序算法進行優(yōu)化我們首先要明白之前我們所寫的堆排序有什么可以優(yōu)化的地方或者說哪里寫的不夠好？

void HeapSort(int* a, int size)
{
	//小堆
	HP hp;
	HeapInit(&hp);
	//O(N*logN)
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	//O(N*logN)
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestory(&hp);
}

這是我們之前寫的堆排序，我們能夠發(fā)現(xiàn)，如果我們要實現(xiàn)堆排序的前提是我們要寫一堆。那這想想都很麻煩，我們都知道排序算法那么多，我們何必選擇這種算法呢？

其次我們再來分析一下建堆的時間復雜度：

1.1建堆的時間復雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明 ( 時間復雜度本來看的就是近似值，多幾個節(jié)點不影響最終結果) ：

因為我們要進行優(yōu)化建堆，在這里分析一下向下調整建堆和向上調整建堆的時間復雜度。

1.1.1 向下調整建堆：O(N)

過程分析如下：

因此向下調整建堆的時間復雜度為O(n)。

1.1.2 向上調整建堆：O(N*logN)

過程分析如下：

 因此向上調整建堆的時間復雜度為O(N*logN)。

1.2堆排序的復雜度

1.2.1原堆排序的時間復雜度

我們來看原堆排序的代碼中使用了向上調整建堆，因此原排序的時間復雜度為O(N*logN)

1.2.2原堆排序的空間復雜度

因為我們要建立一個堆，我們實現(xiàn)堆是使用數(shù)組實現(xiàn)，因此假設有要排序元素個數(shù)為N，空間復雜度為O(N)。

1.3堆排序優(yōu)化算法的復雜度

堆排序的優(yōu)化算法主要是對空間復雜度進行優(yōu)化。由于我們之前建堆都要開辟新的數(shù)組，因此我們是否可以在原數(shù)組上直接建堆，無需再開辟新的空間建堆呢？答案當然是可以的。以下使用的正是在原數(shù)組上直接建堆。

1.3.1 堆排序優(yōu)化算法的時間復雜度

由于使用堆排序，我們要利用堆的特點，每次取堆頂?shù)脑亍Ｒ虼嗣看稳⊥陻?shù)據(jù)后都要對堆進行調整。再次我們有向上調整和向下調整兩種算法，我們需要對這兩種算法分別分析選出一個 更優(yōu)的調整算法。

1.3.1.1向上調整--建堆 O(N*logN)

由于我們是對原數(shù)組之間建堆，因此我們如果要是用向上調整，在剛剛我們所分析的建堆的時間復雜度是O(N*logN)。

實現(xiàn)代碼：

	向上調整--建堆  O(N*logN)
	int n = 1;
	while (n<size)
	{
		AdjustUp(a, n++);
	}

1.3.1.2向下調整-建堆 O(N)

由于向下調整的前提條件是左子樹和右子樹都已經(jīng)是一個堆，但是一個數(shù)組并不能保證是一個堆，那么我們不能直接對數(shù)組使用向下調整。因此我們需要將節(jié)點的左子樹右子樹變成堆再進行向下調整。因此我們可以我們可以倒著來。

過程：

1、葉子節(jié)點不要調，因為一個節(jié)點可以看成堆。因此我們從倒數(shù)的第一個非葉子節(jié)點開始調整。如果找到倒數(shù)第一個非葉子節(jié)點。那就是用最后一個節(jié)點找他的父節(jié)點就是最后一個非葉子節(jié)點。

parent = (child-1)/2。我們用size計算：child = size -1。因此parent = (size-1-1)/2。我們一直向上找就可以將數(shù)組變成一個堆。因此向下調整建堆的復雜度為O(N)。分析如上：

	//向下調整--建堆  O(N)
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, size, i);
	}

1.3.2 堆排序優(yōu)化算法的空間復雜度

由于我們是在原數(shù)組上進行遍歷因此沒有開辟新的空間。因此空間復雜度為O(1)。

1.4堆排序實現(xiàn)邏輯

如果升序建小堆，最小的數(shù)已經(jīng)在堆頂,剩下的數(shù)關系打亂,需要重新建堆,建堆最好也要O(N)，再選出次小的,不斷建堆選數(shù),如果這樣,還不如直接遍歷選數(shù)??！因此升序要建大堆?。?/strong>利用刪除的思想來玩。

	//升序要建大堆,
	size_t end = size - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}

void HeapSort(int* a, int size)
{
	//向下調整--建堆  O(N)
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, size, i);
	}
 
	//如果升序建小堆,最小的數(shù)已經(jīng)在堆頂,剩下的數(shù)關系打亂,需要重新建堆,建堆最好也要O(N)
	//再選出次小的,不斷建堆選數(shù),如果這樣,還不如直接遍歷選數(shù)?。?
 
	//升序要建大堆,
	size_t end = size - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
 
int main()
{
	int a[] = { 4,2,1,3,5,7,9,8,6};
	HeapSort(a,sizeof(a)/sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
  
	return 0;
}