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

戳這里可跳轉(zhuǎn)上篇文~~

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

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

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);
}

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

其次我們?cè)賮?lái)分析一下建堆的時(shí)間復(fù)雜度：

1.1建堆的時(shí)間復(fù)雜度

因?yàn)槎咽峭耆鏄?shù)，而滿二叉樹(shù)也是完全二叉樹(shù)，此處為了簡(jiǎn)化使用滿二叉樹(shù)來(lái)證明 ( 時(shí)間復(fù)雜度本來(lái)看的就是近似值，多幾個(gè)節(jié)點(diǎn)不影響最終結(jié)果) ：

因?yàn)槲覀円M(jìn)行優(yōu)化建堆，在這里分析一下向下調(diào)整建堆和向上調(diào)整建堆的時(shí)間復(fù)雜度。

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

過(guò)程分析如下：

因此向下調(diào)整建堆的時(shí)間復(fù)雜度為O(n)。

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

過(guò)程分析如下：

 因此向上調(diào)整建堆的時(shí)間復(fù)雜度為O(N*logN)。

1.2堆排序的復(fù)雜度

1.2.1原堆排序的時(shí)間復(fù)雜度

我們來(lái)看原堆排序的代碼中使用了向上調(diào)整建堆，因此原排序的時(shí)間復(fù)雜度為O(N*logN)

1.2.2原堆排序的空間復(fù)雜度

因?yàn)槲覀円⒁粋€(gè)堆，我們實(shí)現(xiàn)堆是使用數(shù)組實(shí)現(xiàn)，因此假設(shè)有要排序元素個(gè)數(shù)為N，空間復(fù)雜度為O(N)。

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

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

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

由于使用堆排序，我們要利用堆的特點(diǎn)，每次取堆頂?shù)脑?。因此每次取完?shù)據(jù)后都要對(duì)堆進(jìn)行調(diào)整。再次我們有向上調(diào)整和向下調(diào)整兩種算法，我們需要對(duì)這兩種算法分別分析選出一個(gè) 更優(yōu)的調(diào)整算法。

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

由于我們是對(duì)原數(shù)組之間建堆，因此我們?nèi)绻怯孟蛏险{(diào)整，在剛剛我們所分析的建堆的時(shí)間復(fù)雜度是O(N*logN)。

實(shí)現(xiàn)代碼：

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

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

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

過(guò)程：

1、葉子節(jié)點(diǎn)不要調(diào)，因?yàn)橐粋€(gè)節(jié)點(diǎn)可以看成堆。因此我們從倒數(shù)的第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)整。如果找到倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)。那就是用最后一個(gè)節(jié)點(diǎn)找他的父節(jié)點(diǎn)就是最后一個(gè)非葉子節(jié)點(diǎn)。

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

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

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

由于我們是在原數(shù)組上進(jìn)行遍歷因此沒(méi)有開(kāi)辟新的空間。因此空間復(fù)雜度為O(1)。

1.4堆排序?qū)崿F(xiàn)邏輯

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

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

void HeapSort(int* a, int size)
{
	//向下調(diào)整--建堆  O(N)
	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, size, i);
	}
 
	//如果升序建小堆,最小的數(shù)已經(jīng)在堆頂,剩下的數(shù)關(guān)系打亂,需要重新建堆,建堆最好也要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;
}