堆排序

?堆排序：堆排序是一個(gè)時(shí)間復(fù)雜度為O(nlogn)空間復(fù)雜度為O(1)的十分優(yōu)秀且非常穩(wěn)定的排序算法，不論是在最好還是最壞情況下，其時(shí)間復(fù)雜度都穩(wěn)定在O(nlogn),同時(shí)一般也可以用來快速求出一組數(shù)據(jù)中大或最小的前幾個(gè)數(shù)。

創(chuàng)新互聯(lián)公司是一家專業(yè)提供五家渠企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、網(wǎng)站設(shè)計(jì)、成都h5網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為五家渠眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

---

算法過程

?堆排序算法的過程主要可以分為三個(gè)部分，調(diào)整部分（也是最主要的過程）、建堆和排序。接下來詳細(xì)介紹這三個(gè)過程的步驟。
?1.調(diào)整過程：調(diào)整就是將一組數(shù)據(jù)，從非堆的狀態(tài)調(diào)整為堆的狀態(tài)。堆就是滿足如下定義的結(jié)構(gòu)(以大頂堆為例，大頂堆排序得到的升序序列)，左右孩子都小于自身，且其左右孩子所構(gòu)成的堆也滿足該定義。假設(shè)調(diào)整的是第i個(gè)數(shù)據(jù)，那么需要比較的就是arr[2i]與arr[2i+1]的數(shù)據(jù)的大小關(guān)系，將大于arr[i]的數(shù)據(jù)調(diào)整到i的位置，并且用此方法繼續(xù)去調(diào)整被調(diào)走的那個(gè)數(shù)據(jù)；
?2.建堆過程：當(dāng)調(diào)整的過程做好后，建堆也就十分簡(jiǎn)便了，只需要不斷地調(diào)用調(diào)整函數(shù)即可。每次從n/2的位置開始調(diào)整，依次往前，知道調(diào)整到1位置后結(jié)束該過程；
?3.排序過程：排序過程就是將前兩個(gè)過程結(jié)合起來。建堆，然后不斷地將堆頂數(shù)據(jù)交換到末尾，并且把堆的長(zhǎng)度減1，然后繼續(xù)調(diào)整，直到堆的長(zhǎng)度為1時(shí)停止；

---

Code

?請(qǐng)結(jié)合代碼加深對(duì)堆排序的過程的理解。

void swap(int&a,int&b)// 交換函數(shù) &為C++用法
{a = a^b;
	b = b^a;
	a = a^b;
}
void adjust(int*arr,int i,int n)// 調(diào)整函數(shù)
{int j,t = arr[i];
	while(1)
	{if(2*i+1<=n)// 左右孩子都有
		{	j = arr[2*i]>arr[2*i=1]?2*i:2*i+1;// 找出左右孩子大的一個(gè)
			if(arr[j]>t)// 比較是否比t大
			{		arr[i] = arr[j];
				i = j;
			}
			else // 否則跳出
				break;
		}
		else if(2*i==n)// 只有左孩子 此處的判斷條件極為重要！exceedingly crucial!!!
		{	if(arr[2*i]>t)
			{		arr[i] = arr[2*i];
				i *= 2;
			}
			break;// 只要進(jìn)入此判斷條件下一步必然要跳出
		}
	}
	arr[i] = t;// 將t放在找到的位置
} 
void buildHeap(int*arr,int n)// 從n/2處開始向上調(diào)整
{int i;
	for(i=n/2;i>0;i--)
		adjust(arr,i,n);
}
void heapSort(int*arr,int n)// heapSort 排序函數(shù)
{int i;
	buildHeap(arr,n);// 首先建堆
	for(i=n;i>0;i--)
	{swap(arr[1],arr[i--]);// 每次交換根結(jié)點(diǎn)到最后位置 并length--
		adjust(arr,i);
	}
}

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

本文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)——堆排序C語言-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://aaarwkj.com/article44/ccgphe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、靜態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、網(wǎng)站收錄、網(wǎng)頁設(shè)計(jì)公司、服務(wù)器托管

廣告

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