C語言版堆排序代碼講解（超級詳細(xì)）-創(chuàng)新互聯(lián)

先說什么是堆呢，堆是一種完全二叉樹，它分為大堆和小堆，堆的表示最好用數(shù)組表示，因為它是完全二叉樹，不存在分支為空

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),柳南企業(yè)網(wǎng)站建設(shè),柳南品牌網(wǎng)站建設(shè),網(wǎng)站定制,柳南網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,柳南網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

做堆之前，要熟練掌握兩個公式? parent=（child-1）/2；

child=parent*2+1;

這里我們拿升序的代碼舉例，記住，升序就要大堆，降序就要小堆，具體為何看代碼注釋

這里建議先看代碼，代碼看不懂再看圖解

AdjustUp的圖解---這個圖解的過程得配合HeapPush這個函數(shù)看，插入一個，就調(diào)整一次，這里的child永遠(yuǎn)是數(shù)組最后一個元素

以此類推，只要記住child永遠(yuǎn)是數(shù)組最后一個，然后插入一次調(diào)整一次就行了

AdjustDown圖解--建議這個函數(shù)的圖解配合Heapsort函數(shù)的第一個循環(huán)看更好，我寫的可能跟那個函數(shù)的意思不一樣，不過都大同小異，理解了我的圖解，再想一下就好了

以此類推

Heapsort圖解

?
#include#include#include
typedef int HPDataType;
//先創(chuàng)建一個堆的結(jié)構(gòu)體
typedef struct Heap
{
	HPDataType* a;
	int size;//元素的個數(shù)
	int capacity;//這塊空間的大承受元素的限度，說到這里有的小伙伴可能還是不懂，那么我就來舉個例子吧
	//比如你創(chuàng)建了一塊空間，可以容下10個元素，這時候有一個數(shù)組里面有5個元素，那么相對于這個結(jié)構(gòu)體來說，size就是5，capacity就是10
}HP;
//對堆進行初始化，這個大家應(yīng)該都能理解，我也不解釋了
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交換函數(shù)，下面會用到多次交換，所以我就寫了一個交換函數(shù)，交換函數(shù)大家應(yīng)該都能理解，我也不多解釋了
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//這個函數(shù)是向上調(diào)整
void AdjustUp(int* a, int child)
{
	//child就是最后一個元素的下標(biāo)，然后用公式把他的parent求出來
	int parent = (child - 1) / 2;
	while (child >0)
	//這里有人會問了，為什么不能是parent>=0,而是child>0呢
	//你想，由大括號里面的這兩個公式
	// child = parent;
	//parent = (child - 1) / 2;
	//到最后，parent=0的時候，把parent賦值給child，然后這時候child就是0了
	//然后parent = (child - 1) / 2的時候，child是0，（0-1）/2還是0；
	//所以只要控制child>0就好了
	{
		if (a[child] >a[parent])//記住，大堆這里就改成>，小堆就是<，a[child]和a[parent]的順序最好不要變（可以變），容易給自己搞懵?。?		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//這個函數(shù)是往數(shù)組堆的結(jié)構(gòu)體里面的那個HPDataType* a里面一個一個放進去main()函數(shù)里的數(shù)組arr中的元素
void HeapPush(HP* hp, int x)
{
	if (hp->size == hp->capacity)//如果這個時候size跟capacity（這塊空間的元素的個數(shù)跟這塊空間所能承受的元素的大限度相等了）
	{
		//就需要擴容了，如果空間所能承受的元素的大限度是0，那么就擴容四個空間
		//如果空間所能承受的元素的大限度不是0，那么就在原來空間所能承受大限度的基礎(chǔ)上再擴容一倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		 //下面這個語句的意思就是增容
		//為什么tmp的類型是 HPDataType*呢？？我們接著往下看，realloc的意思就是把一個空間，在它原有的基礎(chǔ)上
		//增容到realloc的括號里面的逗號后面那個對象的大小，這里也就是sizeof(HPDataType) * newcapacity
		//增容到sizeof(HPDataType) * newcapacity這么大
		//回到剛才那個問題，這里結(jié)構(gòu)體的int* a你可以認(rèn)為是一個數(shù)組
		//[(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity)]的意思要把數(shù)組里面的元素增容到這么大，然后將這個賦值給tmp,
		// 這時候tmp就可以認(rèn)為成一個數(shù)組了，這個數(shù)組里面的元素的大容量比a數(shù)組里面的大
		//并且tmp在下一步要賦值給a
		


		//有的人想問了，為什么不直接寫(hp->a,newcapacity)呢，我自己的理解是，我們創(chuàng)建的堆的結(jié)構(gòu)體里面
		//a數(shù)組里面的數(shù)據(jù)類型都是HPDataType，這里我把int給typedef成HPDataType，也就是說HPDataType也占四個字節(jié)
		//你的一個數(shù)組里面就算是有int類型的元素，但是他們每個元素都是4個字節(jié)，比如你有一個10個元素的數(shù)組，它里面是40個字節(jié)，同樣
		//你增容后的數(shù)組也要按照字節(jié)來算，計算機里面是按照字節(jié)的，不是按照元素個數(shù)的
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)//判斷一下tmp是否增容成功了
		{
			printf("realloc failed\n");
			exit (-1);
		}
		hp->a = tmp;//相當(dāng)于把tmp數(shù)組的容量大小賦值給a數(shù)組了
		hp->capacity = newcapacity;//然后把newcapacity的值賦給capacity
	}
	hp->a[hp->size] = x;//hp->size就是數(shù)組最后一個元素的后面緊挨著的那個空間
	hp->size++;//插入了之后，元素的個數(shù)+1

	//下面這個向上調(diào)整可以加上可以不加上
	// hp->a就是把a這個數(shù)組傳過去，hp->size-1就是最后一個元素的下標(biāo)
	//AdjustUp(hp->a,hp->size-1);
}
//打印函數(shù)，把元素一個個打印出來，驗證你的代碼是否正確
void Print(HP* hp, int sz)
{
	for (int i = 0; i< sz; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}//這個是向下調(diào)整
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//這里child沒分左右孩子，默認(rèn)為左孩子
	while (child< n)
	{
		//child+1肯定是右孩子
		if (child + 1< n && a[child + 1] >a[child])//還是一樣，大堆就是a[child + 1] >a[child]，小堆就是<，順序最好別變，否則易懵
		{
			child++;
		}
		if (a[child] >a[parent])//大堆就是a[child] >a[parent]，小堆就是<
		{
			Swap(&a[child], &a[parent]);
			parent = child;//相應(yīng)的順序大家看AdjustUp,思想都差不多
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(HP* hp, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		//(n - 1 - 1)的意思就是，最后一個孩子的父親，n-1是最后一個孩子，把它看成N
		//然后（N）-1/2不就是我說的公式嘛
		//這個時候arr數(shù)組中的元素都已經(jīng)相應(yīng)的插入到a里面去了，但是還是亂序，不知道它是大堆還是小堆，這里我們要把它調(diào)成大堆，因為是升序
		//i= (n - 1 - 1) / 2意味著我們只需要從倒數(shù)第一個非葉子結(jié)點調(diào)整，如果我們從葉子結(jié)點調(diào)整的話，葉子結(jié)點也沒有孩子呀，碼農(nóng)們想一下
		//這時候i--的意思就是調(diào)整完倒數(shù)第一個非葉子結(jié)點之后，就開始調(diào)整倒數(shù)第二個非葉子結(jié)點
	{
		//hp->a表示傳數(shù)組，n表示傳元素的個數(shù)，i表示開始調(diào)整大堆的位置
		AdjustDown(hp->a, n, i);
	}
	//上一行代碼---也就是}這個大括號的右半部分結(jié)束之后，我們的大堆就調(diào)好了
	//下一行代碼就是要開始排序了
	for (int end = n - 1; end >0; end--)
	{
		//你想，hp->a[0]肯定是這個堆里面的大的一個，然后把這個大的一個跟堆里面最后一個進行交換
		Swap(&hp->a[0], &hp->a[end]);
		//換完了之后，最后一個換到了第一個，這個時候亂序了，肯定不是大堆了，這個時候就開始把第一個向下調(diào)整
		//hp->a表示傳數(shù)組，end表示傳元素的個數(shù)，0表示開始調(diào)整大堆的位置
		AdjustDown(hp->a, end, 0);
		//調(diào)整完了之后又是一個大堆了，這個時候數(shù)組最后一個元素大，所以end--，這個時候相當(dāng)于不要數(shù)組最后一個元素了，大的已經(jīng)找到了
		//然后，這個不要最后一個元素之后，第一個元素就是大的了，然后再進行循環(huán)
		
		
		//為什么end不是>=0呢，你想，假如有5個數(shù)字，大的4個數(shù)字都找出來了，最后一個肯定是最小的呀
	}
}
int main()
{
	HP hp;
	HeapInit(&hp);
	int arr[] = { 50,20,90,100,1,65,88 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i< sz; i++)//把這個數(shù)組里面的元素一個個插入到HPDataType* a里面去
	{
		HeapPush(&hp,arr[i]);
	}
	Print(&hp, sz);
	Heapsort(&hp, sz);
	Print(&hp, sz);
	return 0;
}

?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：C語言版堆排序代碼講解（超級詳細(xì)）-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://muchs.cn/article0/dcjoio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計公司、網(wǎng)頁設(shè)計公司、面包屑導(dǎo)航、網(wǎng)站策劃、標(biāo)簽優(yōu)化、網(wǎng)站收錄

廣告

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

網(wǎng)站優(yōu)化排名