前言：
今天我們將講解我們數(shù)據(jù)結(jié)構(gòu)初階的最后一部分知識的學習，也是最為“炸裂”的知識---------排序算法的講解！?。?！

1.排序的概念及其運用

1.1排序的概念

排序：所謂排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。常見的內(nèi)部排序算法有：【插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、計數(shù)排序等】

外部排序：數(shù)據(jù)元素太多不能同時放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

1.2排序運用

要說起排序，在我們?nèi)粘Ｉ畹姆椒矫婷婵梢哉f都能看到。就拿我們平時網(wǎng)上買東西舉例，當我們挑選時我們總會按照個人的需求進行排序分類，例如當我們買電腦時，會看到下圖：

我們可以從很多的角度去選擇我們心儀的，可以根據(jù)價格，銷量等等，看榜單的排名一定層度上能反映出大眾都認可的東西?。?！

2.常見排序算法的實現(xiàn)

插入排序是一種非常直觀的排序算法。其基本思想就是將一個待排序的記錄按其關(guān)鍵字的大小插入前面以及排好序的子序列中，直到全部記錄插入完成。 由插入排序的思想可以引申出三個最重要的排序算法：【直接插入排序，折半插入排序和希爾排序】

2.1 插入排序

2.1.1直接插入排序

根據(jù)上面的插入排序思想，不難得出一種最簡單也是最直觀的直接插入排序算法。假設(shè)在排序過程中，待排序表L【1…n】在某次排序過程中的某一時刻狀態(tài)如下：

要將元素L[i]插入已有序的子序列L[1…i-1],需要執(zhí)行以下操作：
1）查找出L[i] 在L[1…i-1]中的插入位置k。
2）將L[k…i-1]中的所有元素依次向后移動一個位置。
3）將L[i] 賦值到L[k].

為了實現(xiàn)對 L [1… n ]的排序，可以將 L (2)~ L ( n ）依次插入前面已排好序的子序列，初始 L [1]可以視為是一個已排好序的子序列。上述操作執(zhí)行 n -1次就能得到一個有序的表。插入排序在實現(xiàn)上通常采用就地排序（空間復(fù)雜度為 O (1))，因而在從后向前的比較過程中，需要反復(fù)把已排序元素逐步向后挪位，為新元素提供插入空間。

我們通過舉例來具體解釋一哈步奏。假定初始序列為14, 33, 27, 10, 35, 19, 42, 44

（1）第一步：將第一個元素 14 看作是一個有序的子序列 {14}，將剩余元素逐個插入到此序列的適當位置：

（2）第二步： 將 33 插入到 {14} 中，由于 33 > 14，所以 33 應(yīng)該插入到 14 的后面，新的有序序列變?yōu)?{14,33}；

（3）第三步：將 27 插入到 {14, 33} 中，由于 27 < 33 同時 27 > 14，所以 27 應(yīng)該插入到 14 和 33 的中間，新的有序序列變?yōu)?{14, 27, 33}；

（4）第四步：將 10 插入到 {14, 27, 33} 中，經(jīng)過依次和 33、27、14 比較，最終斷定 10 應(yīng)該插入到 14之前，新的有序序列變?yōu)?{10, 14, 27, 33}；

（5）第五步：將 35 插入到 {10, 14, 27, 33} 中，由于 35 > 33，所以 35 應(yīng)該插入到 33之后，新的有序序列變?yōu)?{10, 14, 27, 33, 35}

（6）第六步： 將 19 插入到 {10, 14, 27, 33, 35} 中，經(jīng)過依次和 35、33、27、14 比較，最終斷定 19應(yīng)該插入到 14 和 27 之間，新的有序序列變?yōu)?{10, 14, 19, 27, 33, 35}；

（7）第七步：將 42 插入到 {10, 14, 19, 27, 33, 35} 中，由于 42 > 35，所以 42 應(yīng)插入到 35之后，新的有序序列變?yōu)?{10, 14, 19, 27, 33, 35, 42}；

（8）第八步： 將 44 插入到 {10, 14, 19, 27, 33, 35, 42} 中，由于 44 > 42，所以 44 應(yīng)插入到 42 之后，新的有序序列變?yōu)?{10, 14, 19, 27, 33, 35, 42, 44}。

經(jīng)過將各個待排序的元素插入到有序序列的適當位置，最終得到的就是一個包含所有元素的有序序列。

接下來我們通過動畫形象的演示：

解釋：

1.從第一個元素開始，該元素可以認為已經(jīng)被排序；
2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；
3.如果該元素（已排序）大于新元素，將該元素移到下一位置；
4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
5.將新元素插入到該位置后；
6.重復(fù)步驟2~5。

代碼如下：

void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
}

性能分析：

直接插入排序算法的性能分析如下：

空間效率：僅使用了常數(shù)個輔助單元，因而空間復(fù)雜度為 O (1)。
時間效率：在排序過程中，向有序子表中逐個地插入元素的操作進行了 n -1趟，每趟操作都分為比較關(guān)鍵字和移動元素，而比較次數(shù)和移動次數(shù)取決于待排序表的初始狀態(tài)

在最好情況下，表中元素已經(jīng)有序，此時每插入一個元素，都只需比較一次而不用移動元素，因而時間復(fù)雜度為 O ( n )。

在最壞情況下，表中元素順序剛好與排序結(jié)果中的元素順序相反（逆序），總的比較次數(shù)達到最大,總的移動次數(shù)也達到最大.

平均情況下，考慮待排序表中元素是隨機的，此時可以取上述最好與最壞情況的平均值作為平均情況下的時間復(fù)雜度，總的比較次數(shù)與總的移動次數(shù)均約為N^2／4。

因此，直接插入排序算法的時間復(fù)雜度為 O（N^2）

穩(wěn)定性：由于每次插入元素時總是從后向前先比較再移動，所以不會出現(xiàn)相同元素相對位置發(fā)生變化的情況，即直接插入排序是一個穩(wěn)定的排序方法。

適用性：直接插入排序算法適用于順序存儲和鏈式存儲的線性表。為鏈式存儲時，可以從前往后查找指定元素的位置。

注意：大部分排序算法都僅適用于順序存儲的線性表

2.1.2希爾排序( 縮小增量排序 )

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩(wěn)定排序算法。

從前面的分析可知，直接插入排序算法的時間復(fù)雜度為O(n^2)，但若待排序序列為“正序”時，其時間復(fù)雜度可以提升為O(n)。由此可見它更適用于基本有序的排序表和數(shù)據(jù)量不大的排序表。希爾排序正是基于以上兩點分析對直接插入排序進行改造得來的?。?！

希爾排序法的基本思想是：
先選定一個整數(shù)，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進行排序。然后，取，重復(fù)上述分組和排序的工作。當?shù)竭_=1時，所有記錄在統(tǒng)一組內(nèi)排好序。

我們通過舉例來說明次算法的結(jié)題思路：

算法步驟：

選擇一個增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列個數(shù) k，對序列進行 k 趟排序；

每趟排序，根據(jù)對應(yīng)的增量 ti，將待排序列分割成若干長度為 m 的子序列，分別對各子表進行直接插入排序。僅增量因子為 1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

動畫展示：

代碼如下：

void ShellSort(int* a, int n)
{
	// gap > 1 預(yù)排序
	// gap == 1 直接插入排序
	int gap = n;
	while (gap > 1)
	{
		// gap = gap / 2; 

		// gap = gap / 3;  // 9  8 不能保證最后一次一定是1
		gap = gap / 3 + 1;  // 9  8


		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}

			a[end + gap] = tmp;
		}
	}
}

希爾排序的特性總結(jié)：

1. 希爾排序是對直接插入排序的優(yōu)化。
2. 當gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就
   會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復(fù)雜度都不固定：
4. 《數(shù)據(jù)結(jié)構(gòu)(C語言版)》— 嚴蔚敏
   《數(shù)據(jù)結(jié)構(gòu)-用面相對象方法與C++描述》— 殷人昆
   

穩(wěn)定性：當相同關(guān)鍵字的記錄被劃分到不同的字表時，可能會改變它們之前的相對排序，因此希爾排序是一種不穩(wěn)定的排序算法。

適用性：希爾排序算法僅適用于線性表為順序存儲的情況。

2.2 選擇排序

選擇排序的基本思想是：

每一趟（如第 i 趟）在后面 n - i + l ( i =1,2,…, n -1）個待排序元素中選取關(guān)鍵字最小的元素，作為有序子序列的第 i 個元素，直到第 n - l 趟做完，待排序元素只剩下1個，就不用再選了。

2.2.1直接選擇排序

選擇排序是一種簡單直觀的排序算法，無論什么數(shù)據(jù)進去都是 O(n2)的時間復(fù)雜度。所以用到它的時候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間。

根據(jù)上面選擇排序的思想，可以很直觀地得出簡單選擇排序算法的思想：
假設(shè)排序表為 L [1… n ]，第 i 趟排序即從 L [ i … n ］中選擇關(guān)鍵字最小的元素與 L ( i ）交換，每一趟排序可以確定一個元素的最終位置，這樣經(jīng)過 n -1趟排序就可使得整個排序表有序。

算法步驟:

首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。

再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

動態(tài)圖展示：

代碼如下：

// 任何情況都是O(N^2)  包括有序或接近有序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
			maxi = mini;

		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}

直接選擇排序的特性總結(jié)：

空間效率：僅使用常數(shù)個輔助單元，故空間效率為 O (1)。
時間效率：從上述偽碼中不難看出，在簡單選擇排序過程中，元素移動的操作次數(shù)很少，不會超過3( n -1）次，最好的情況是移動0次，此時對應(yīng)的表已經(jīng)有序；但元素間比較的次數(shù)與序列的初始狀態(tài)無關(guān)，始終是 n ( n -1)/2次，因此時間復(fù)雜度始終是 O ( n^2)。

穩(wěn)定性：在第 i 趟找到最小元素后，和第 i 個元素交換，可能會導致第1個元素與其含有相同關(guān)鍵字元素的相對位置發(fā)生改變。因此，簡單選擇排序是一種不穩(wěn)定的排序方法。

2.2.2堆排序

在之前的博客中，我們已經(jīng)詳細了解了堆排序的概念以及運用。具體大家可以閱讀：堆排序的詳解

2.3交換排序

基本思想：所謂交換，就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來對換這兩個記錄在序列中的位置。

交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

2.3.1冒泡排序

冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢"浮"到數(shù)列的頂端。

作為最簡單的排序算法之一，冒泡排序給我的感覺就像 Abandon 在單詞書里出現(xiàn)的感覺一樣，每次都在第一頁第一位，所以最熟悉。冒泡排序還有一種優(yōu)化算法，就是立一個 flag，當在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序。但這種改進對于提升性能來說并沒有什么太大作用。

冒泡排序的基本思想是：

從后往前（或從前往后）兩兩比較相鄰元素的值，若為逆序（即 A [ i -1]> A [ i ])，則交換它們，直到序列比較完。我們稱它為第一趟冒泡，結(jié)果是將最小的元素交換到待排序列的第一個位置（或?qū)⒆畲蟮脑亟粨Q到待排序列的最后一個位置），關(guān)鍵字最小的元素如氣泡一般逐漸往上"漂浮"直至"水面"（或關(guān)鍵字最大的元素如石頭一般下沉至水底）。下一趟冒泡時，前一趟確定的最小元素不再參與比較，每趟冒泡的結(jié)果是把序列中的最小元素（或最大元素）放到了序列的最終位置．…．這樣最多做 n -1趟冒泡就能把所有元素排好序。

所示為冒泡排序的過程，第一趟冒泡時：27<49，不交換：13<27，不交換：76>13,交換：97>13，交換：65>13，交換；38>13，交換；49>13，交換。通過第一趟冒泡后，最小元素已交換到第一個位置，也是它的最終位置。第二趟冒泡時對剩余子序列采用同樣方法進行排序，以此類推，到第五趟結(jié)束后沒有發(fā)生交換，說明表已有序，冒泡排序結(jié)束。

算法步驟

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。

針對所有的元素重復(fù)以上的步驟，除了最后一個。

持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

動態(tài)圖展示如下：

代碼如下：

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;

		for (int i = 1; i < n-j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}

		// 一趟冒泡過程中，沒有發(fā)生交換，說明已經(jīng)有序了，不需要再處理
		if (exchange == 0)
		{
			break;
		}
	}
}

冒泡排序的性能分析如下：

空間效率：僅使用了常數(shù)個輔助單元，因而空間復(fù)雜度為 O (1)。

時間效率：當初始序列有序時，顯然第一趟冒泡后 flag 依然為 false （本趟冒泡沒有元素交換），從而直接跳出循環(huán)，比較次數(shù)為 n -1，移動次數(shù)為0，從而最好情況下的時間復(fù)雜度為 O ( n )：當初始序列為逆序時，需要進行 n - l 趟排序，第 i 趟排序要進行 n - i 次關(guān)鍵字的比較，而且每次比較后都必須移動元素3次來交換元素位置。這種情況下:

冒泡排序總的比較次數(shù)為n(n-1)/2，移動次數(shù)為n(n-1)/2次；

從而，最壞情況下的時間復(fù)雜度為 O ( n^2)，其平均時間復(fù)雜度也為 O(n^2）。

穩(wěn)定性：冒泡排序是一種穩(wěn)定的排序方法。

注意：冒泡排序中所產(chǎn)生的有序子序列一定是全局有序的（不同于直接插入排序），也就是說，有序子序列中的所有元素的關(guān)鍵字一定小于或大于無序子序列中所有元素的關(guān)鍵字，這樣每趟排序都會將一個元素放置到其最終的位置上。

2.3.2 快速排序(重點）

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。

快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。

快速排序又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。

其基本思想為：

任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復(fù)該過程，直到所有元素都排列在相應(yīng)位置上為止。

1. hoare版本（即左右指針法）

思想：

一趟排序過程就是一個交替搜索和替換的過程。任取待排序元素序列中的某元素作為基準值（一般是兩邊的元素，我們這里選擇最左邊），然后我們把key放到合適的位置，使得（左邊比key小，右邊比key大【升序】），讓最右邊的元素先移動找比key小的，左邊找比key大的，然后交換left和right的值，直到left和right相遇即止，相遇后交換key和left（right）任意一個位置的值。

我們通過畫圖來進行了解：

當?shù)谝淮巫笥抑羔樝嘤龊蟮奈恢脮r，基準值就被交換到了中間，接著呢繼續(xù)對左右區(qū)間進行重復(fù)的操作，首先直至左區(qū)間有序后，會進行回調(diào)；此時再去遞歸右區(qū)間，當右區(qū)間也有序之后，那整體也就有序了

注意：

左邊做key,可以讓左邊先走嗎？

不可以左邊做key必須讓右邊先走，右邊(right)是找比key小的，找到小的停下來，即使相遇也能保證right位置的值小于key的

動圖展示：

代碼如下：

// Hoare
int PartSort1(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	int keyi = left;
	while (left < right)
	{
		// 右邊先走，找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}

		// 左邊再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	Swap(&a[left], &a[keyi]);
	keyi = left;

	return keyi;
}

大家分析上述代碼，會發(fā)現(xiàn)有缺陷的地方？

1.待排序列呈現(xiàn)有序的情況，如果key后面的每個數(shù)都比key小或大的話，那left向后面找或right向前面找，就會產(chǎn)生越界訪問的問題，為了防止這樣情況的產(chǎn)生，我們選擇在if語句的判斷部分加個邏輯與&&保證left小于right，以免產(chǎn)生越界訪問的問題。

2.快速排序除了對【有序序列】進行排序會退化之外，還有一點就是它需要進行層層遞歸，那既然是遞歸，就需要調(diào)用函數(shù)；既然要調(diào)用函數(shù)，那就需要建立棧幀，一旦建立棧幀會出現(xiàn)棧溢出的情況。

第一種方法就是三數(shù)取中，三數(shù)取中就是為了讓我們選取的key在序列中的位置盡量靠中間.?三數(shù)取中，當中的三數(shù)指的是：最左邊的數(shù)、最右邊的數(shù)以及中間位置的數(shù)。三數(shù)取中就是取這三個數(shù)當中，值的大小居中的那個數(shù)作為該趟排序的key。這就確保了我們所選取的數(shù)不會是序列中的最大或是最小值了。

代碼如下：

// 三數(shù)取中
// begin  mid  end
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else // a[begin] > a[mid]
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

注意：
當大小居中的數(shù)不在序列的最左或是最右端時，我們不是就以居中數(shù)的位置作為key的位置，而是將key的值與最左端的值進行交換，這樣key就還是位于最左端了，所寫代碼就無需改變，而只需在單趟排序代碼開頭加上以下兩句代碼即可：

int midIndex = GetMidIndex(a, begin, end);//獲取大小居中的數(shù)的下標
	Swap(&a[begin], &a[midIndex]);//將該數(shù)與序列最左端的數(shù)據(jù)交換
	//以下代碼保持不變...

對于三數(shù)取中法，是在開頭優(yōu)化；
而第二種小區(qū)間優(yōu)化法，則是在結(jié)尾優(yōu)化

小區(qū)間優(yōu)化是為了讓遞歸深度不要太深，因為數(shù)據(jù)量過大以后，我們遞歸的深度就會增加，遞歸建立的棧幀數(shù)量會隨著遞歸深度的增加而增加，又因為?？臻g本身就小，很容易造成棧溢出的問題。當遞歸區(qū)間的數(shù)據(jù)量較小時，我們不采用遞歸解決他們，而是換成直接插入的方法來解決較小數(shù)據(jù)量的排序。

//小區(qū)間優(yōu)化
if ((end - begin + 1) < 15)
{
	//在數(shù)據(jù)量少的時候改用直接插入排序
	InsertSort(a + begin, end - begin + 1);
}

2.挖坑法

思想：

1、選出一個數(shù)據(jù)（一般是最左邊或是最右邊的）存放在key變量中，在該數(shù)據(jù)位置形成一個坑。
2、還是定義一個left和一個right，left從左向右走，right從右向左走。（若在最左邊挖坑，則需要R先走；若在最右邊挖坑，則需要L先走）。
3、在走的過程中，若R遇到小于key的數(shù)，則將該數(shù)拋入坑位，并在此處形成一個坑位，這時left再向后走，若遇到大于key的數(shù)，則將其拋入坑位，又形成一個坑位，如此循環(huán)下去，直到最終L和R相遇，這時將key拋入坑位即可。（選取最左邊的作為坑位）

經(jīng)過一次單趟排序，最終也使得key左邊的數(shù)據(jù)全部都小于key，key右邊的數(shù)據(jù)全部都大于key。

然后也是將key的左序列和右序列再次進行這種單趟排序，如此反復(fù)操作下去，直到左右序列只有一個數(shù)據(jù)，或是左右序列不存在時，便停止操作。

動態(tài)展示：

代碼如下：

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[mid]);

	int left = begin, right = end;
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		// 右邊找小，填到左邊坑里面
		while (left < right && a[right] >= key)
		{
			--right;
		}

		a[hole] = a[right];
		hole = right;

		// 左邊找大，填到右邊坑里面
		while (left < right && a[left] <= key)
		{
			++left;
		}

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;
	return hole;
}

3.前后指針法

思想：

前后指針法的單趟排序的基本步驟如下： ?
1、選出一個key，一般是最左邊或是最右邊的。
2、起始時，prev指針指向序列開頭，cur指針指向prev+1。
3、若cur指向的內(nèi)容小于key，則prev先向后移動一位，然后交換prev和cur指針指向的內(nèi)容，然后cur指針++；若cur指向的內(nèi)容大于key，則cur指針直接++。如此進行下去，直到cur指針越界，此時將key和prev指針指向的內(nèi)容交換即可。

經(jīng)過一次單趟排序，最終也能使得key左邊的數(shù)據(jù)全部都小于key，key右邊的數(shù)據(jù)全部都大于key。

然后也還是將key的左序列和右序列再次進行這種單趟排序，如此反復(fù)操作下去，直到左右序列只有一個數(shù)據(jù)，或是左右序列不存在時，便停止操作。

單趟的動圖演示：

上述遞歸實現(xiàn)的局限性可能在于：
當數(shù)據(jù)量特別大時，可能會導致棧溢出(棧漲的速度為logn，也可能是我多慮了，漲地其實挺慢的)。
為了解決上面可能出現(xiàn)的問題，我們可以將遞歸實現(xiàn)轉(zhuǎn)換為非遞歸實現(xiàn)，我們知道任何遞歸的過程都可以轉(zhuǎn)化為一個迭代的過程，而轉(zhuǎn)化的關(guān)鍵在于如何使用迭代來模擬整個遞歸的處理。

觀察上面的遞歸處理過程，我們可以看到：每一次排序函數(shù)的調(diào)用都會再次重新調(diào)用兩次新的排序函數(shù)，然后系統(tǒng)會按照調(diào)用順序一步一步地進行處理和返回，而調(diào)用排序函數(shù)的關(guān)鍵在于必須將排序的范圍告訴函數(shù)。

這個過程很像一個排隊處理的過程，于是我們可以使用隊列進行遞歸的模擬，而隊列中的信息存儲要處理的范圍即可。當隊列不為空時，表示還有范圍未處理；隊列為空時，表示所有的范圍都已經(jīng)處理完畢，也即確定了所有元素的位置，完成了排序工作。

我們利用棧的相關(guān)思想來進行實現(xiàn)：

void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (StackEmpty(&st) != 0)
{
 right = StackTop(&st);
 StackPop(&st);
 left = StackTop(&st);
 StackPop(&st);
 
 if(right - left <= 1)
 continue;
 int div = PartSort1(a, left, right);
 // 以基準值為分割點，形成左右兩部分：[left, div) 和 [div+1, right)
 StackPush(&st, div+1);
 StackPush(&st, right);
 
 StackPush(&st, left);
 StackPush(&st, div);
}
 
 StackDestroy(&s);
}

快速排序算法的性能分析如下：

空間效率：由于快速排序是遞歸的，需要借助一個遞歸工作找來保存每層遞歸調(diào)用的必要信息，其容量應(yīng)與遞歸調(diào)用的最大深度一致。最好情況下為 O ( logzn )；最壞情況下，因為要進行 n - l 次遞歸調(diào)用，所以棧的深度為 O ( n )：平均情況下，棧的深度為 O ( logn)。

時間效率：快速排序的運行時間與劃分是否對稱有關(guān)，快速排序的最壞情況發(fā)生在兩個區(qū)域分別包含 n -1個元素和0個元素時，這種最大限度的不對稱性若發(fā)生在每層遞歸上，即對應(yīng)于初始排序表基本有序或基本逆序時，就得到最壞情況下的時間復(fù)雜度為 O ( n^2)。

有很多方法可以提高算法的效率：

一種方法是盡量選取一個可以將數(shù)據(jù)中分的樞軸元素，如從序列的頭尾及中間選取三個元素，再取這三個元素的中間值作為最終的樞軸元素：

或者隨機地從序列的頭尾及中間選取三個元素，再取這三個元素的中間值作為最終的樞軸元素；有隨機吧從當前表中選取樞軸元素，這樣做可使得最壞情況在實際排序中幾乎不會發(fā)生。

在最理想的狀態(tài)下，即 Partition (）可能做到最平衡的劃分，得到的兩個子問題的大小都不可能大于 n /2，在這種情況下，快速排序的運行速度將大大提升，此時，時間復(fù)雜度為 O (nlog2n)。好在快速排序平均情況下的運行時間與其最佳情況下的運行時間很接近，而不是接近其最壞情況下的運行時間?？焖倥判蚴撬袃?nèi)部排序算法中平均性能最優(yōu)的排序算法。

穩(wěn)定性：在劃分算法中，若右端區(qū)間有兩個關(guān)鍵字相同，且均小于基準值的記錄，則在交換到左端區(qū)間后，它們的相對位置會發(fā)生變化，即快速排序是一種不穩(wěn)定的排序方法。例如，表 L =(3,2,2)，經(jīng)過一趟排序后 L =(2,2,3)，最終排序序列也是 L =(2,2,3)，顯然，2與2的相對次序已發(fā)生了變化。

注意：在快速排序算法中，并不產(chǎn)生有序子序列，但每趟排序后會將樞軸（基準）元素放到其最終的位置上。

2.4 歸并排序

歸并排序與上述基于交換、選擇等排序的思想不一樣，"歸并"的含義是將兩個或兩個以上的有序表組合成一個新的有序表。假定待排序表含有 n 個記錄，則可將其視為 n 個有序的子表，每個子表的長度為1，然后兩兩歸并，得到「 n /27個長度為2或」的有序表；繼續(xù)兩兩歸并．…．如此重復(fù)，直到合并成一個長度為 n 的有序表為止，這種排序方法稱為2路歸并排序。

兩路歸并核心步奏：

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
自下而上的迭代；

以下為一個兩路歸并的例子：

算法步驟：

申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；

設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；

重復(fù)步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

遞歸版本：

// 時間復(fù)雜度：O(N*logN)
// 空間復(fù)雜度：O(N)
// [begin, end]
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid] [mid+1, end] 遞歸讓子區(qū)間有序
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	// 歸并[begin, mid] [mid+1, end]
	//...

	int begin1 = begin, end1 = mid;
	int begin2 = mid+1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int)*(end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	_MergeSort(a, 0, n - 1, tmp);


	free(tmp);
	tmp = NULL;
}

非遞歸版本：

歸并排序的非遞歸算法并不需要借助棧來完成，我們只需要控制每次參與合并的元素個數(shù)即可，最終便能使序列變?yōu)橛行颍?br> ?
當然，以上例子是一個待排序列長度比較特殊的例子，我們?nèi)羰窍雽懗鲆粋€廣泛適用的程序，必定需要考慮到某些極端情況：
情況一：
?當最后一個小組進行合并時，第二個小區(qū)間存在，但是該區(qū)間元素個數(shù)不夠gap個，這時我們需要在合并序列時，對第二個小區(qū)間的邊界進行控制。
?
情況二：
?當最后一個小組進行合并時，第二個小區(qū)間不存在，此時便不需要對該小組進行合并。
?
情況三：
?當最后一個小組進行合并時，第二個小區(qū)間不存在，并且第一個小區(qū)間的元素個數(shù)不夠gap個，此時也不需要對該小組進行合并。
?
只要把控好這三種特殊情況，寫出歸并排序的非遞歸算法便輕而易舉了。

代碼如下：

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	// 歸并每組數(shù)據(jù)個數(shù)，從1開始，因為1個認為是有序的，可以直接歸并
	int rangeN = 1;
	while (rangeN < n)
	{
		for (int i = 0; i < n; i += 2 * rangeN)
		{
			// [begin1,end1][begin2,end2] 歸并
			int begin1 = i, end1 = i + rangeN - 1;
			int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1;
			printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
			int j = i;

			// end1 begin2 end2 越界
			// 修正區(qū)間  ->拷貝數(shù)據(jù) 歸并完了整體拷貝 or 歸并每組拷貝
			if (end1 >= n)
			{
				end1 = n - 1;
				// 不存在區(qū)間
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				// 不存在區(qū)間
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
		}

		// 也可以整體歸并完了再拷貝
		memcpy(a, tmp, sizeof(int)*(n));

		rangeN *= 2;
	}

	free(tmp);
	tmp = NULL;
}

動態(tài)圖展示：

2路歸并排序算法的性能分析如下：

空間效率： Merge (）操作中，輔助空間剛好為 n 個單元，所以算法的空間復(fù)雜度為 O ( n )。
時間效率：每趟歸并的時間復(fù)雜度為 O ( n )，共需進行「 logznl 趟歸并，所以算法的時間復(fù)雜度為 O ( nlogn ).

穩(wěn)定性：由于 Merge (）操作不會改變相同關(guān)鍵字記錄的相對次序，所以2路歸并排序算法是一種穩(wěn)定的排序方法。

2.5 計數(shù)排序

思想：
計數(shù)排序又稱為鴿巢原理，是對哈希直接定址法的變形應(yīng)用。 顧名思義，該算法不是通過比較數(shù)據(jù)的大小來進行排序的，而是通過統(tǒng)計數(shù)組中相同元素出現(xiàn)的次數(shù)，然后通過統(tǒng)計的結(jié)果將序列回收到原來的序列中。操作步驟：

1. 統(tǒng)計相同元素出現(xiàn)次數(shù)
2. 根據(jù)統(tǒng)計的結(jié)果將序列回收到原來的序列中

計數(shù)排序的特征

當輸入的元素是 n 個 0 到 k 之間的整數(shù)時，它的運行時間是 Θ(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。

注：計數(shù)排序只適用于數(shù)據(jù)范圍較集中的序列的排序，若待排序列的數(shù)據(jù)較分散，則會造成空間浪費，并且計數(shù)排序只適用于整型排序，不適用與浮點型排序。

算法的步驟如下：
（1）找出待排序的數(shù)組中最大和最小的元素
（2）統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項
（3）對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）
（4）反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去1

動態(tài)展示：

代碼如下：

//計數(shù)排序
void CountSort(int* a, int n)
{
	int min = a[0];//記錄數(shù)組中的最小值
	int max = a[0];//記錄數(shù)組中的最大值
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;//min和max之間的自然數(shù)個數(shù)（包括min和max本身）
	int* count = (int*)calloc(range, sizeof(int));//開辟可儲存range個整型的內(nèi)存空間，并將內(nèi)存空間置0
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//統(tǒng)計相同元素出現(xiàn)次數(shù)（相對映射）
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	int i = 0;
	//根據(jù)統(tǒng)計結(jié)果將序列回收到原來的序列中
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
	free(count);//釋放空間
}

計數(shù)排序算法的性能分析如下：

1. 計數(shù)排序在數(shù)據(jù)范圍集中時，效率很高，但是適用范圍及場景有限。
2. 時間復(fù)雜度：O(MAX(N,范圍))
3. 空間復(fù)雜度：O(范圍)
4. 穩(wěn)定性：穩(wěn)定

3.各種內(nèi)部排序算法比較及運用

3.1內(nèi)部排序算法的比較

前面討論的排序算法很多，對各算法的比較也是愛考的內(nèi)容。一般基于三個因素進行對比：時空復(fù)雜度、算法的穩(wěn)定性、算法的過程特征。

從時間復(fù)雜度看：

簡單選擇排序、直接插入排序和冒泡排序平均情況下的時間復(fù)雜度都為 O ( n^2)，且實現(xiàn)過程也較簡單.

直接插入排序和冒泡排序最好情況下的時間復(fù)雜度可以達到 O ( n )

而簡單選擇排序則與序列的初始狀態(tài)無關(guān)。
希爾排序作為插入排序的拓展，對較大規(guī)模的排序都可以達到很高的效率，但目前未得出其精確的漸近時間。
堆排序利用了一種稱為堆的數(shù)據(jù)結(jié)構(gòu)，可在線性時間內(nèi)完成建堆，且在 O ( nlogn ）內(nèi)完成排序過程。

快速排序基于分治的思想，雖然最壞情況下快速排序時間會達到 O ( n )，但快速排序平均性能可以達到 O ( nlogn )，在實際應(yīng)用中常常優(yōu)于其他排序算法。

歸并排序同樣基于分治的思想，但由于其分割子序列與初始序列的排列無關(guān)，因此它的最好、最壞和平均時間復(fù)雜度均為 O ( nlogn )。

從空間復(fù)雜度看：

簡單選擇排序、插入排序、冒泡排序、希爾排序和堆排序都僅需要借助常數(shù)個輔助空間。

快速排序在空間上只使用一個小的輔助棧，用于實現(xiàn)遞歸，平均情況下大小為 O ( logn )，當然在最壞情況下可能會增長到 O ( n )。

2路歸并排序在合并操作中需要借助較多的輔助空間用于元素復(fù)制，大小為 O ( n )，雖然有方法能克服這個缺點，但其代價是算法會很復(fù)雜而且時間復(fù)雜度會增加。

從穩(wěn)定性看：插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的排序方法，而簡單選擇排序、快速排序、希爾排序和堆排序都是不穩(wěn)定的排序方法。平均時間復(fù)雜度為 O ( nlogn ）的穩(wěn)定排序算法只有歸并排序，對于不穩(wěn)定的排序方法，只要舉出一個不穩(wěn)定的實例即可。對于排序方法的穩(wěn)定性，小伙伴們應(yīng)能從算法本身的原理上去理解，而不應(yīng)拘泥于死記硬背。

排序算法復(fù)雜度及穩(wěn)定性分析：

3.2內(nèi)部排序算法的運用

通常情況，對排序算法的比較和應(yīng)用應(yīng)考慮以下情況。

1）選取排序方法需要考慮的因素

①待排序的元素數(shù)目 n
②元素本身信息量的大小。
③關(guān)鍵字的結(jié)構(gòu)及其分布情況。
④穩(wěn)定性的要求。
⑤語言工具的條件，存儲結(jié)構(gòu)及輔助空間的大小等。

2）排序算法小結(jié)

①若 n 較小，可采用直接插入排序或簡單選擇排序。由于直接插入排序所需的記錄移動次數(shù)較簡單選擇排序的多，因而當記錄本身信息量較大時，用簡單選擇排序較好。

②若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒泡排序為宜。

③若 n 較大，則應(yīng)采用時間復(fù)雜度為 O ( nlogn ）的排序方法：【快速排序、堆排序或歸并排序】?？焖倥判虮徽J為是目前基于比較的內(nèi)部排序方法中最好的方法，當待排序的關(guān)鍵字隨機分布時，快速排序的平均時間最短。堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況，這兩種排序都是不穩(wěn)定的。若要求排序穩(wěn)定且時間復(fù)雜度為 O ( nlogn )，則可選用歸并排序。

④在基于比較的排序方法中，每次比較兩個關(guān)鍵字的大小之后，僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的 n 個關(guān)鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要 O ( nlogn / n ）的時間。

⑥若 n 很大，記錄的關(guān)鍵字位數(shù)較少所可以分解時，采用基數(shù)排序較好。

⑥當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可用鏈表作為存儲結(jié)構(gòu)。

4 選擇題講解

1.有字符序列 FBJGEAIDCH，現(xiàn)在打算對它按字母的字典順序用希爾排序進行排序，那么在第一趟后（步長為5）的序列為（ ）
A.CAEBFDIGJH
B.AIDCHFBJGE
C.ABDCEFIJGH
D.BFJGEAIDCH

解答：

希爾排序按照步長把元素進行小組劃分，每個小組元素進行插入排序。

所以如果步長為5，則整個數(shù)組被會劃分成5組數(shù)據(jù)：

FA BI JD GC EH

所以一趟排序之后的結(jié)果為：

ABDCEFIJGH
所以選C

2.下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（ ）

① 選擇排序
② 歸并排序
③ 快速排序
④ 堆排序

A.①④
B.①②④
C.①③④
D.①②③④

解析：

選擇排序每次選一個最值，放在最終的位置

快速排序每次基準值的位置也可以確定

堆排序每次堆頂元素的位置也可以確定

所以這三種方法都可以每次至少確定一個元素的位置

而歸并排序每次都需要對n個元素重新確定位置，所以不能保證每次都能確定一個元素位置，有可能每次排序所有元素的位置都為發(fā)生變化。

所以選C

3.以下哪種排序算法對[1, 3, 2, 4, 5, 6, 7, 8, 9]進行排序最快（ ）
A.直接插入排序
B.快速排序
C.歸并排序
D.堆排序

解析：

次序列接近有序，所以如果是插入排序，時間復(fù)雜度逼近O(n)

快排： 逼近O(n^2)

歸并和堆排仍然是nlogn

所以選A

4.對數(shù)字序列28 16 32 12 60 2 5 72進行升序的快速排序（以第一個關(guān)鍵碼為基準的方法），一次劃分后的結(jié)果為（ ）
A.2 5 12 16 28 60 32 72
B.2 16 5 12 28 60 32 72
C.2 16 12 5 28 60 32 72
D.5 16 2 12 28 32 60 72

解析：

快速排序以基準值為中心，對元素進行劃分，這里以28為基準值，則小于28的和大于28的進行交換，完成一次劃分

首先：32和5交換： 28 16 5 12 60 2 32 72

然后60和2交換： 28 16 5 12 2 60 32 72

最后28和最后一個小于28的元素進行交換：

    2 16 5 12 28 60 32 72

5.使用選擇排序?qū)﹂L度為100的數(shù)組進行排序，則比較的次數(shù)為（ ）
A.5050
B.4950
C.4851
D.2475

解析：

選擇排序，每次都要在未排序的所有元素中找到最值，

如果有n個元素，則

第一次比較次數(shù)： n - 1

第二次比較次數(shù)： n - 2

…

第n - 1次比較次數(shù)： 1

所有如果n = 100

則比較次數(shù)的總和：99 + 98 + … + 1

共4950次。

好了，小伙伴們，以上就是排序的全部知識內(nèi)容了。如果對大家有幫助希望多多支持喲?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-402926.html

到了這里，關(guān)于【排序算法】數(shù)據(jù)結(jié)構(gòu)排序詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！