數據結構——堆排序C語言-創新互聯

堆排序

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

創新互聯公司是一家專業提供五家渠企業網站建設,專注與成都做網站、網站設計、成都h5網站建設、小程序制作等業務。10年已為五家渠眾多企業、政府機構等服務。創新互聯專業的建站公司優惠進行中。

---

算法過程

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

---

Code

?請結合代碼加深對堆排序的過程的理解。

void swap(int&a,int&b)// 交換函數 &為C++用法
{a = a^b;
	b = b^a;
	a = a^b;
}
void adjust(int*arr,int i,int n)// 調整函數
{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;// 找出左右孩子大的一個
			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;// 只要進入此判斷條件下一步必然要跳出
		}
	}
	arr[i] = t;// 將t放在找到的位置
} 
void buildHeap(int*arr,int n)// 從n/2處開始向上調整
{int i;
	for(i=n/2;i>0;i--)
		adjust(arr,i,n);
}
void heapSort(int*arr,int n)// heapSort 排序函數
{int i;
	buildHeap(arr,n);// 首先建堆
	for(i=n;i>0;i--)
	{swap(arr[1],arr[i--]);// 每次交換根結點到最后位置 并length--
		adjust(arr,i);
	}
}

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

本文標題：數據結構——堆排序C語言-創新互聯
文章轉載：http://m.kartarina.com/article44/ccgphe.html

成都網站建設公司_創新互聯，為您提供外貿建站、靜態網站、自適應網站、網站收錄、網頁設計公司、服務器托管

廣告

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