目錄

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

1 排序基礎(chǔ)

1.1 排序的基本概念

2 排序算法

2.1 插入排序

1.思想

2.實現(xiàn)

3.效率分析

4.優(yōu)化

2.2 希爾排序

1.定義

2.實現(xiàn)

3.效率分析

3 交換排序

3.1 冒泡排序

1.定義

2.實現(xiàn)

3.效率分析

3.2 快速排序

1.算法思想

2.實現(xiàn)

3.效率分析

4 選擇排序

4.1 簡單選擇排序

1.定義

2.實現(xiàn)

3.效率分析

4.2 堆排序

1.根堆

2.根堆建立

3.堆排序

4.效率分析

4.3 堆排序插入刪除

1.插入

2.刪除

5 其他排序算法

5.1 歸并排序

1.原理

2.實現(xiàn)

3.效率分析

5.2 基數(shù)排序

1.定義

2.效率分析

3.適用領(lǐng)域

6 外部排序

6.1 外部排序

1.內(nèi)外存數(shù)據(jù)交換

2.外部排序

3.時間分析

4.算法優(yōu)化

6.2 敗者樹

1.算法思想

2.實現(xiàn)

6.3 置換-選擇排序

6.4 最佳歸并樹

---

1 排序基礎(chǔ) 1.1 排序的基本概念

排序：按關(guān)鍵字有序地排列表中的元素

評價指標(biāo)：時間與空間復(fù)雜度、算法穩(wěn)定性

分類：內(nèi)部排序（數(shù)據(jù)在內(nèi)存中）、外部排序

2 排序算法 2.1 插入排序 1.思想

算法思想：每次將一個待排序的記錄按其關(guān)鍵字大小插入到前面已排好序的子序列中，直到全部記錄插入完成

2.實現(xiàn)

void Insertsort(int a[],int n)
{
	int i,j = 0;
	for (i = 0; i< n; i++)      // 遍歷整個數(shù)組
	{
		if (a[i]< a[i - 1])     // 若當(dāng)前元素小于其前驅(qū)，進(jìn)入下一層循環(huán)
		{
			int temp = a[i];     // 因當(dāng)前元素應(yīng)位于其前驅(qū)之前，先存放在臨時變量中 
			for (j = i - 1; j >= 0 && a[j] >temp; --j)    // 遍歷該元素前驅(qū)之前的元素
			{
				a[j + 1] = a[j];   // 前驅(qū)依次后移
			}
			a[j+1] = temp;   // 將該元素放在比他大的前驅(qū)前
		}
	}
}

3.效率分析

空間復(fù)雜度O(1)

時間復(fù)雜度：O(n) ~ O(n^2)

平均時間復(fù)雜度：O(n^2)

穩(wěn)定性：穩(wěn)定

4.優(yōu)化

2.2 希爾排序 1.定義

希爾排序︰先將待排序表分割成若干子表，對各個子表分別進(jìn)行直接插入排序?？s小增量d，重復(fù)上述過程，直到d=1為止。?

2.實現(xiàn)

3.效率分析

空間復(fù)雜度：O(1)

最壞時間復(fù)雜度：O(n^2)

穩(wěn)定性：不穩(wěn)定

僅適用于順序表

3 交換排序 3.1 冒泡排序 1.定義

從后往前（或從前往后)兩兩比較相鄰元素的值，若為逆序（即A[i-1]>A[i])，則交換它們，直到序列比較完。稱這樣過程為“一趟”冒泡排序。

2.實現(xiàn)

3.效率分析

空間復(fù)雜度：O(1)

時間復(fù)雜度：最好O(n)，最壞O(n^2)，平均O(n^2)

穩(wěn)定性：穩(wěn)定

適用于鏈表排序

3.2 快速排序 1.算法思想

在待排序表L[1..n]中任取一個元素pivot作為樞軸(或基準(zhǔn)，通常取首元素)，通過一趟排序?qū)⒋判虮韯澐譃楠?dú)立的兩部分L[1..k-1]和LIk+1..n]，使得L1...k-1]中的所有元素小于pivot，Llk+1..n]中的所有元素大于等于pivot，則pivot放在了其最終位置L(k)上，這個過程稱為一次“劃分”。然后分別遞歸地對兩個子表重復(fù)上述過程，直至每部分內(nèi)只有一個元素或空為止，即所有元素放在了其最終位置上。

2.實現(xiàn)

3.效率分析

穩(wěn)定性：不穩(wěn)定

適用于鏈表排序

4 選擇排序 4.1 簡單選擇排序 1.定義

每一趟在待排序元素中選取關(guān)鍵字最小的元素加入有序子序列

2.實現(xiàn)

3.效率分析

空間復(fù)雜度：O(1)

時間復(fù)雜度：O(n^210)

穩(wěn)定性：不穩(wěn)定

適用于鏈表

4.2 堆排序 1.根堆

若n個關(guān)鍵字序列L[ 1...n]滿足下面某一條性質(zhì)，則稱為堆(Heap) :

若滿足：L(i)≥L(2i)且L(i)≥L(2i+1) (1 ≤i sn/2) —―大根堆(大頂堆)

若滿足:L(i)≤L(2i)且L(i)≤L(2i+1) (1 s i ≤n/2 ) —―小根堆(小頂堆)

將大（?。└芽醋黜樞虼鎯Φ耐耆鏄?，即根結(jié)點(diǎn)大（小）于左/右子樹結(jié)點(diǎn)。

2.根堆建立

檢查所有非終端結(jié)點(diǎn)（i<= [n/2]）是否滿足要求，若不滿足將當(dāng)前結(jié)點(diǎn)與更大的子樹結(jié)點(diǎn)互換。

3.堆排序

每一輪都將堆頂元素加入有序子序列（與待排序中的最后一個元素交換），并將待排序元素序列再次調(diào)整為根堆。

基于大根堆得到遞增序列

4.效率分析

若樹高為h，某結(jié)點(diǎn)在第i層，則將這個結(jié)點(diǎn)向下調(diào)整最多只需要“下墜”h-i層，關(guān)鍵字對比次數(shù)不超過2(h-i)

時間復(fù)雜度：建堆O(n) + 堆排序O(n1og_2n) =?O(n1og_2n)

空間復(fù)雜度：O(n)

穩(wěn)定性：不穩(wěn)定

4.3 堆排序插入刪除 1.插入

以小根堆為例，新元素放入表尾，與父節(jié)點(diǎn)對比，若新元素較小就交換，持續(xù)上升。

2.刪除

用堆底元素代替被刪除的元素，并將該元素進(jìn)行下墜交換。

5 其他排序算法 5.1 歸并排序

將兩個或多個有序序列合并

1.原理

2.實現(xiàn)

將一個序列拆分成兩個序列進(jìn)行多輪歸并排序

3.效率分析

時間復(fù)雜度：O(n*Log_2n)

空間復(fù)雜度：O(n)

5.2 基數(shù)排序 1.定義

第一輪以個位進(jìn)行分配，將各元素鏈接后得到按個位遞減排序的序列；次輪以十位進(jìn)行分配，將各元素鏈接后得到按十位遞減排序的序列；再次輪按百位進(jìn)行分配，得到按百位遞減排序的序列

2.效率分析

一輪分配O(n)，一輪手機(jī)O(r)，共d輪分配與收集

時間復(fù)雜度：O(d*(n + r))

空間復(fù)雜度：O(r)?

穩(wěn)定性：穩(wěn)定

3.適用領(lǐng)域

6 外部排序 6.1 外部排序 1.內(nèi)外存數(shù)據(jù)交換

2.外部排序

因數(shù)據(jù)元素過多，外存數(shù)據(jù)無法全部讀入內(nèi)存進(jìn)行排序，因此要進(jìn)行基于歸并排序的外部排序。

3.時間分析

外部排序時間開銷=讀寫外存的時間+內(nèi)部排序所需時間+內(nèi)部歸并所需時間

4.算法優(yōu)化

可以使用多路歸并，減少讀寫外存的時間。但內(nèi)存開銷與歸并所需時間會增加

6.2 敗者樹

多路歸并數(shù)增加，導(dǎo)致內(nèi)部歸并所需時間增加。

1.算法思想

可視為—棵完全二叉樹（多了一個頭頭)。k個葉結(jié)點(diǎn)分別是當(dāng)前參加比較的元素，非葉子結(jié)點(diǎn)用來記憶左右子樹中的“失敗者”，而讓勝者往上繼續(xù)進(jìn)行比較，一直到根結(jié)點(diǎn)。

2.實現(xiàn)

6.3 置換-選擇排序

6.4 最佳歸并樹

要使磁盤I/O次數(shù)最少，就要讓歸并樹的帶權(quán)路徑長度最小，構(gòu)造K叉哈夫曼樹。??

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

文章題目：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記（Ⅷ）：排序-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://weahome.cn/article/doggie.html