(1) 時間效率

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

(2) 空間效率

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

(3)穩(wěn)定性

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

快速排序是基于分治法的一種排序方法，是對冒泡排序的一種改進，他是目前內部排序中排序速度較快的一種方法。

基本思想：通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分的關鍵字均不大于另一部分的關鍵字，可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序的目的

內部排序：排序記錄放在計算機存儲器里面進行的

進們快速排序的具體過程如下。

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

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

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

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

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

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

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

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

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;
 }

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

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

簡單選擇排序的具體過程如下。

①讓i等于1。

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

③讓i的值增加1,轉向②，直到對R[n-1].key與R[n].key進行比較并進行相應的處理為止，最終得到一一個有序的序列。

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;
 }

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

堆的定義：對于含有n個元素的序列，若其對應的關鍵字序列，滿足下列關系：

若將順序存儲的待排序中的關鍵字序列看作是一棵完全二叉樹，則堆的含義表明：完全二叉樹中所有非終端結點的值均不小于（或者不大于）其左、右孩子結點的值，相應的這樣的完全二叉樹稱為大（或者?。╉敹选＜炊秧斣貫樾蛄兄械拇笾担ɑ蛘咦钚≈担?/p>

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

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

①初建堆，即如何將一個無序序列建成一個堆。

②調整堆，即如何在輸出堆頂元素后，調整剩余元素成為一個新堆。

先考慮堆的調整問題。設當前所使用的堆為大頂堆，首先將堆頂元素與最后一個元素進行交換。此時，不包含最后一個元素的完全二叉樹就失去了堆的性質，不再是一個堆了，但根結點的左右子樹均為堆，因此可以從根結點開始，自上而下進行調整。

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

關于調整過程：

堆排序：

若想要將一個無序序列排列成一個遞增的有序序列，可以在堆排序的算法中先建立一個大頂堆，將堆頂元素和最后一個元素交換，然后再調整成一個大頂堆，重復直到整個序列有序為止。

void heap(int a[], int s, int m) {
	//把s到m序列調整成一個大頂堆 
	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]);//交換最后一個和首個
		heap(a, 0, i-1); //重新調整 
	}
	return;
}

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

當前題目：c語言實現(xiàn)數(shù)據(jù)結構---關于實現(xiàn)各種排序算法-創(chuàng)新互聯(lián)
轉載源于：http://aaarwkj.com/article34/dpjipe.html

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

廣告

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