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

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

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)堆排序的前提是我們要寫一堆。那這想想都很麻煩，我們都知道排序算法那么多，我們何必選擇這種算法呢？

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

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

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

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

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

過程分析如下：

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

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

過程分析如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

過程：

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

parent = (child-1)/2。我們用size計算：child = size -1。因此parent = (size-1-1)/2。我們一直向上找就可以將數(shù)組變成一個堆。因此向下調(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ù)組上進行遍歷因此沒有開辟新的空間。因此空間復(fù)雜度為O(1)。

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

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

過程：

1、把第一個數(shù)和最后一個數(shù)交換，由于是大堆，堆頂?shù)臄?shù)據(jù)一定是最大的數(shù)據(jù)。和最后一個數(shù)交換后，最大的數(shù)據(jù)就到了最后一個。

2、再對前N-1個數(shù)進行向下調(diào)整建立新的大堆，次大的數(shù)放在了堆頂，我們再讓堆頂?shù)脑睾妥詈笠粋€元素交換（這個最后一個不是數(shù)組的最后一個，是堆中的最后一個，使用end進行控制）。

3、當end到0的時候，說明已經(jīng)排完了。

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

1.5堆排序?qū)崿F(xiàn)代碼

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

1.6演示結(jié)果

總結(jié)

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之堆排序優(yōu)化算法的文章就介紹到這了,更多相關(guān)C語言堆排序優(yōu)化算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論