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

創(chuàng)新互聯(lián)是創(chuàng)新、創(chuàng)意、研發(fā)型一體的綜合型網(wǎng)站建設公司，自成立以來公司不斷探索創(chuàng)新，始終堅持為客戶提供滿意周到的服務，在本地打下了良好的口碑，在過去的十多年時間我們累計服務了上千家以及全國政企客戶，如木包裝箱等企業(yè)單位，完善的項目管理流程，嚴格把控項目進度與質量監(jiān)控加上過硬的技術實力獲得客戶的一致夸獎。

大堆：每個父節(jié)點都大于孩子節(jié)點。

最小堆：每個父節(jié)點都小于孩子節(jié)點。

堆排序的思想：對于給定的N個數(shù)據(jù)，初始時把這些記錄看作是一顆順序存儲的二叉樹，然后將其調整為一個大堆，然后將堆的最后一個元素與堆頂元素（即二叉樹的根節(jié)點）進行交換，堆的最后一個元素即為大記錄；接著將（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)
{
	//找到第一個非葉子節(jié)點構建堆
	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;
}

程序運行結果：

    

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

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

新聞標題：用C++實現(xiàn)堆排序-創(chuàng)新互聯(lián)
鏈接地址：http://chinadenli.net/article44/dggphe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、做網(wǎng)站、App設計、網(wǎng)站收錄、品牌網(wǎng)站制作、響應式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)