c語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)---關(guān)于實(shí)現(xiàn)各種排序算法-創(chuàng)新互聯(lián)

(1) 時(shí)間效率

算法的效率取決于增量的取值，這是一個(gè)未解決的數(shù)學(xué)難題。 希爾增量般的取值是d=[n/2」， 并且最后一個(gè)增量- 定為1。排序中子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列。當(dāng)增量采用Hibbard增量時(shí)，,希爾排序的時(shí)間復(fù)雜度為0(n的1.5次方)希爾排序時(shí)間復(fù)雜度的下界是O(nlog2n)。

(2) 空間效率

本算法只需要個(gè)輔助空間， 用來(lái)作為“哨兵”，所以空間復(fù)雜度 S(n)=O(1)。

(3)穩(wěn)定性

在不同子序列的插入排序過(guò)程中，相同的元素可能在各自的插入序列中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以希爾排序是不穩(wěn)定的排序方法。

快速排序是基于分治法的一種排序方法，是對(duì)冒泡排序的一種改進(jìn)，他是目前內(nèi)部排序中排序速度較快的一種方法。

基本思想：通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均不大于另一部分的關(guān)鍵字，可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序的目的

內(nèi)部排序：排序記錄放在計(jì)算機(jī)存儲(chǔ)器里面進(jìn)行的

進(jìn)們快速排序的具體過(guò)程如下。

對(duì)R[s], . R[t]中的記錄進(jìn)行一趟快速排序， 附設(shè)兩個(gè)指針low 和high,設(shè)置一個(gè)板軸記錄R[0]=R[s]，pivotkey=R[s] .key。

①令10ow=s, high=t,并保存low位置的記錄。

②從high所指位置起向low所指位置方向搜索，找到第1個(gè)關(guān)鍵字不大于pivotkey的記錄，放在low位置處，并使low++。

③從low所指位置起向high所指位置方向搜索，找到第1個(gè)關(guān)鍵字不小于pivotkey的記錄，放在high位置處，并使high--。

④重復(fù)②、③兩步，直至low=high為止(此時(shí)整個(gè)序列被分成有序的前后兩塊)。⑤將軸元素放在low位置處。

⑥再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止。每一趟快速排序，都可將樞軸元素放在其最終的位置上。

例如，待排序的初始關(guān)鍵字序列為(28, 35，12, 19, 46, 54, 12, 39)，進(jìn)行快速排的過(guò)程如圖:

教材上是線性表實(shí)現(xiàn)的，而且有點(diǎn)復(fù)雜，我就用到之前的方法寫(xiě)的代碼，也是相同的思想

void quick_sort(int*num,int l,int r){
	if(r<=l) return;
	int x=l,y=r,z=num[l];
	while(x=z)--y;
		if(x>len;
	for(int i = 0; i< len; i++){
		cin >>arry[i];
	}
	//Insert(arry, len);
	//Bubble(arry, len);
	quick_sort(arry, 0, len-1);
	for(int i = 0; i< len; i++){
		cout<< arry[i]<< " ";
	}
	return 0;
 }

選擇排序基本思想：每一趟從待排序的記錄中選出關(guān)鍵字最小記錄，按順序放在已排好序的子序列的最后，直到全部記錄排序完畢。

簡(jiǎn)單選擇排序是選擇排序中最簡(jiǎn)單的-種排序方法，其基本思想是:第i(1≤i

簡(jiǎn)單選擇排序的具體過(guò)程如下。

①讓i等于1。

②取R[i].key,依次與記錄R[i+1]~R[n]的關(guān)鍵字進(jìn)行比較，找出從第i條記錄到第n條記錄中關(guān)鍵字最小的記錄L.R[j]，交換L.R[i]與L.R[j],使第i個(gè)位置上的記錄成為從第i個(gè)記錄起到第n個(gè)記錄為止的記錄序列中關(guān)鍵字最小的記錄。

③讓i的值增加1,轉(zhuǎn)向②，直到對(duì)R[n-1].key與R[n].key進(jìn)行比較并進(jìn)行相應(yīng)的處理為止，最終得到一一個(gè)有序的序列。

void selet(int *a, int len){
	for(int i = 0; i< len-1; i++){
		int k = i;
		for(int j=i+1; j< len; j++){
			if(a[k] >a[j])
			k = j;
		}
		swap(a[k], a[i]);
	}
	
	return;
} 
int main()
{
	int len;
	cin >>len;
	for(int i = 0; i< len; i++){
		cin >>arry[i];
	}
	//Insert(arry, len);
	//Bubble(arry, len);
	//quick_sort(arry, 0, len-1);
	selet(arry, len);
	for(int i = 0; i< len; i++){
		cout<< arry[i]<< " ";
	}
	return 0;
 }

堆排序是對(duì)簡(jiǎn)單選擇的改進(jìn)，主要是為了減少排序過(guò)程中記錄的比較次數(shù)。在堆排序中，將待排序列邏輯上看作是一顆完全二叉樹(shù)，并用堆來(lái)選擇待排序列的極值，從而達(dá)到最終的排序目的。

堆的定義：對(duì)于含有n個(gè)元素的序列，若其對(duì)應(yīng)的關(guān)鍵字序列，滿足下列關(guān)系：

若將順序存儲(chǔ)的待排序中的關(guān)鍵字序列看作是一棵完全二叉樹(shù)，則堆的含義表明：完全二叉樹(shù)中所有非終端結(jié)點(diǎn)的值均不小于（或者不大于）其左、右孩子結(jié)點(diǎn)的值，相應(yīng)的這樣的完全二叉樹(shù)稱(chēng)為大（或者?。╉敹?。即堆頂元素為序列中的大值（或者最小值）

將無(wú)序序列建成- 個(gè)堆，得到關(guān)鍵字大(或最小)的記錄，輸出堆頂元素后，將剩余的n-1個(gè)元素重新建成一個(gè)堆，則可得到n個(gè)元素中關(guān)鍵字次大(或次小)的記錄，重復(fù)執(zhí)行該操作，最終得到一個(gè)有序序列，這個(gè)過(guò)程就稱(chēng)為堆排序。

實(shí)現(xiàn)堆排序需要解決如下兩個(gè)問(wèn)題。

①初建堆，即如何將一個(gè)無(wú)序序列建成一個(gè)堆。

②調(diào)整堆，即如何在輸出堆頂元素后，調(diào)整剩余元素成為一個(gè)新堆。

先考慮堆的調(diào)整問(wèn)題。設(shè)當(dāng)前所使用的堆為大頂堆，首先將堆頂元素與最后一個(gè)元素進(jìn)行交換。此時(shí)，不包含最后一個(gè)元素的完全二叉樹(shù)就失去了堆的性質(zhì)，不再是一個(gè)堆了，但根結(jié)點(diǎn)的左右子樹(shù)均為堆，因此可以從根結(jié)點(diǎn)開(kāi)始，自上而下進(jìn)行調(diào)整。

將堆頂元素與左右子樹(shù)的根結(jié)點(diǎn)中關(guān)鍵字較大者進(jìn)行比較，若堆頂元素小于子樹(shù)根結(jié)點(diǎn)的值，則堆頂結(jié)點(diǎn)與子樹(shù)根結(jié)點(diǎn)交換。因?yàn)榻粨Q可能又破壞了該子樹(shù)的堆的性質(zhì)，則重復(fù)上述調(diào)整過(guò)程，直至調(diào)整到該子樹(shù)滿足堆的性質(zhì)為止。最壞情況下調(diào)整到葉子結(jié)點(diǎn)才結(jié)束。圖8-9給出了輸出堆頂元素及堆的調(diào)整過(guò)程(假設(shè)結(jié)點(diǎn)中的值就是關(guān)鍵字的值，(b)圖到(d)圖中用雙箭頭線顯示了下一步要進(jìn)行的交換)。

關(guān)于調(diào)整過(guò)程：

堆排序：

若想要將一個(gè)無(wú)序序列排列成一個(gè)遞增的有序序列，可以在堆排序的算法中先建立一個(gè)大頂堆，將堆頂元素和最后一個(gè)元素交換，然后再調(diào)整成一個(gè)大頂堆，重復(fù)直到整個(gè)序列有序?yàn)橹埂?/p>

void heap(int a[], int s, int m) {
	//把s到m序列調(diào)整成一個(gè)大頂堆 
	int k = a[s];
	for(int i = 2*s; i<= m; i *= 2){
		if(i=0; i--){
		heap(a, i, len);
	}
	for(int i = len; i >1; i--){
		swap(a[0], a[len-1]);//交換最后一個(gè)和首個(gè)
		heap(a, 0, i-1); //重新調(diào)整 
	}
	return;
}

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

當(dāng)前題目：c語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)---關(guān)于實(shí)現(xiàn)各種排序算法-創(chuàng)新互聯(lián)
轉(zhuǎn)載源于：http://muchs.cn/article34/dpjipe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、小程序開(kāi)發(fā)、網(wǎng)站內(nèi)鏈、網(wǎng)站策劃、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(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í)需注明來(lái)源： 創(chuàng)新互聯(lián)