排序是非常重要的內(nèi)容，一般來(lái)說(shuō)，我們經(jīng)常用到的也就是十大排序，如圖所示

按照比較類和非比較類又可以分為：

冒泡排序

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢"浮"到數(shù)列的頂端。

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

1.算法描述

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

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

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

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

2.動(dòng)圖展示

3.圖解展示

4.代碼實(shí)現(xiàn)

void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				
				swap(a[j], a[j + 1]);
			}
		}
	
	}
}

5.冒泡排序的優(yōu)化

如果我們的冒泡排序比較了一圈之后發(fā)現(xiàn)沒(méi)有發(fā)生交換，說(shuō)明此時(shí)已經(jīng)有序了。我們就可以退出循環(huán)。

void BubbleSort(int* a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int flag = 1;
		for (int j = 0; j < n - 1 - i; j++) {
			if (a[j] > a[j + 1]) {
				flag = 0;
				swap(a[j], a[j + 1]);
			}
		}
		if (flag) {
			break;
		}
	}
}

6.復(fù)雜度分析

時(shí)間復(fù)雜度：O（N^2)

若數(shù)組為倒序，即所有的輪次都必須執(zhí)行完（最壞情況），比較次數(shù)為 n-1 + n-2 +...+ 1 = n(n-1)/2，交換次數(shù)與比較次數(shù)相同，所以時(shí)間復(fù)雜度為O(N^2)。

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

穩(wěn)定性：插入排序是穩(wěn)定的排序算法，滿足條件nums[j] > nums[j + 1]才發(fā)生交換，這個(gè)條件可以保證值相等的元素的相對(duì)位置不變

插入排序

插入排序是指在待排序的元素中，假設(shè)前面n-1(其中n>=2)個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個(gè)數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個(gè)數(shù)的這個(gè)序列也是排好順序的。 按照此法對(duì)所有元素進(jìn)行插入，直到整個(gè)序列排為有序的過(guò)程，稱為插入排序 。插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴，但它的原理應(yīng)該是最容易理解的了，因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂。插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

1.算法描述

將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。

從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面）

2.動(dòng)圖展示

3.圖解展示

4.代碼實(shí)現(xiàn)

void Insert(int* a, int n)
{
	for (int i = 0; i < n - 1; i++) {
 
		int j = 0;
		int tmp = a[i + 1];
 
		for (j = i; j >= 0 && tmp < a[j]; j--) {
			a[j + 1] = a[j];
		}
		a[j + 1] = tmp;
	}
}

或者也可以這樣寫，這樣寫邏輯更清晰：

void Insert(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;
	}
}

5.復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n2)
• 空間復(fù)雜度：O(1)，只需要一個(gè)額外空間用于交換
• 穩(wěn)定性：插入排序是穩(wěn)定的排序算法，滿足條件nums[j] > nums[j + 1]才發(fā)生交換，這個(gè)條件可以保證值相等的元素的相對(duì)位置不變

希爾排序

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

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率；
• 但插入排序一般來(lái)說(shuō)是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄"基本有序"時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

1.算法描述

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

按增量序列個(gè)數(shù) k，對(duì)序列進(jìn)行 k 趟排序；

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

2.動(dòng)圖展示

3.圖解展示

或者：

4.代碼實(shí)現(xiàn)

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

5.復(fù)雜度分析

1、時(shí)間復(fù)雜度：O(N^2)
希爾排序最壞的時(shí)間復(fù)雜度依然為 O ( N 2 )
但其能夠有效改善直接插入排序序列無(wú)序且長(zhǎng)度大時(shí)的大長(zhǎng)度數(shù)列移位。希爾排序中對(duì)于增量序列的選擇十分重要，直接影響到希爾排序的性能，本文使用的是希爾增量，還有 Hibbard 增量，時(shí)間復(fù)雜度為 O(N^1.5) 也可以認(rèn)為是O ( N^log N)空間復(fù)雜度：O(1)
未借助其它輔助空間。

穩(wěn)定性分析：
與直接插入排序不同，希爾排序中的分組插入可能導(dǎo)致順序移位。

所以，插入排序是穩(wěn)定的排序算法。

堆排序

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

1.算法描述

① 將待排序的序列構(gòu)造成一個(gè)最大堆，此時(shí)序列的最大值為根節(jié)點(diǎn)
② 依次將根節(jié)點(diǎn)與待排序序列的最后一個(gè)元素交換
③ 再維護(hù)從根節(jié)點(diǎn)到該元素的前一個(gè)節(jié)點(diǎn)為最大堆，如此往復(fù)，最終得到一個(gè)遞增序列 先將初始的R[0…n-1]建立成最大堆，此時(shí)是無(wú)序堆，而堆頂是最大元素。
再將堆頂R[0]和無(wú)序區(qū)的最后一個(gè)記錄R[n-1]交換，由此得到新的無(wú)序區(qū)R[0…n-2]和有序區(qū)R[n-1]，且滿足R[0…n-2].keys ≤ R[n-1].key
由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無(wú)序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。
直到無(wú)序區(qū)只有一個(gè)元素為止。

2.動(dòng)圖展示

3.圖解展示

1.預(yù)備知識(shí)：

堆的結(jié)構(gòu)可以分為大根堆和小根堆，是一個(gè)完全二叉樹，而堆排序是根據(jù)堆的這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種排序，下面先來(lái)看看什么是大根堆和小根堆

2.大根堆和小根堆：

性質(zhì)：每個(gè)結(jié)點(diǎn)的值都大于其左孩子和右孩子結(jié)點(diǎn)的值，稱之為大根堆；每個(gè)結(jié)點(diǎn)的值都小于其左孩子和右孩子結(jié)點(diǎn)的值，稱之為小根堆。如下圖

對(duì)應(yīng)成數(shù)組便是：

4.堆的一些基本性質(zhì)

查找數(shù)組中某個(gè)數(shù)的父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)，比如已知索引為i的數(shù)，那么

1.父結(jié)點(diǎn)索引：(i-1)/2（這里計(jì)算機(jī)中的除以2，省略掉小數(shù)）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

所以上面兩個(gè)數(shù)組可以腦補(bǔ)成堆結(jié)構(gòu)，因?yàn)樗麄儩M足堆的定義性質(zhì)：

大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

5.堆的構(gòu)造

將無(wú)序數(shù)組構(gòu)造成一個(gè)大根堆（升序用大根堆，降序就用小根堆）

假設(shè)存在以下數(shù)組

主要思路：第一次保證0~0位置大根堆結(jié)構(gòu)（廢話），第二次保證0~1位置大根堆結(jié)構(gòu)，第三次保證0~2位置大根堆結(jié)構(gòu)...直到保證0~n-1位置大根堆結(jié)構(gòu)（每次新插入的數(shù)據(jù)都與其父結(jié)點(diǎn)進(jìn)行比較，如果插入的數(shù)比父結(jié)點(diǎn)大，則與父結(jié)點(diǎn)交換，否則一直向上交換，直到小于等于父結(jié)點(diǎn)，或者來(lái)到了頂端）

插入6的時(shí)候，6大于他的父結(jié)點(diǎn)3，即arr(1)>arr(0)，則交換；此時(shí)，保證了0~1位置是大根堆結(jié)構(gòu)，如下圖：

插入8的時(shí)候，8大于其父結(jié)點(diǎn)6，即arr(2)>arr(0),則交換；此時(shí)，保證了0~2位置是大根堆結(jié)構(gòu)，如下圖

插入5的時(shí)候，5大于其父結(jié)點(diǎn)3，則交換，交換之后，5又發(fā)現(xiàn)比8小，所以不交換；此時(shí)，保證了0~3位置大根堆結(jié)構(gòu)，如下圖

插入7的時(shí)候，7大于其父結(jié)點(diǎn)5，則交換，交換之后，7又發(fā)現(xiàn)比8小，所以不交換；此時(shí)整個(gè)數(shù)組已經(jīng)是大根堆結(jié)構(gòu)

此時(shí)，我們已經(jīng)得到一個(gè)大根堆，下面將頂端的數(shù)與最后一位數(shù)交換，然后將剩余的數(shù)再構(gòu)造成一個(gè)大根堆

此時(shí)最大數(shù)8已經(jīng)來(lái)到末尾，則固定不動(dòng)，后面只需要對(duì)頂端的數(shù)據(jù)進(jìn)行操作即可，拿頂端的數(shù)與其左右孩子較大的數(shù)進(jìn)行比較，如果頂端的數(shù)大于其左右孩子較大的數(shù)，則停止，如果頂端的數(shù)小于其左右孩子較大的數(shù)，則交換，然后繼續(xù)與下面的孩子進(jìn)行比較

下圖中，5的左右孩子中，左孩子7比右孩子6大，則5與7進(jìn)行比較，發(fā)現(xiàn)5<7，則交換；交換后，發(fā)現(xiàn)5已經(jīng)大于他的左孩子，說(shuō)明剩余的數(shù)已經(jīng)構(gòu)成大根堆，后面就是重復(fù)固定最大值，然后構(gòu)造大根堆

如下圖：頂端數(shù)7與末尾數(shù)3進(jìn)行交換，固定好7，

剩余的數(shù)開始構(gòu)造大根堆 ，然后頂端數(shù)與末尾數(shù)交換，固定最大值再構(gòu)造大根堆，重復(fù)執(zhí)行上面的操作，最終會(huì)得到有序數(shù)組

重點(diǎn)建堆的時(shí)間復(fù)雜度：因?yàn)槎咽峭耆鏄?，而滿二叉樹也是完全二叉樹，此處為了簡(jiǎn)化使用滿二叉樹來(lái)證明(時(shí)間復(fù)雜度本來(lái)看的就是近似值，多幾個(gè)節(jié)點(diǎn)不影響最終結(jié)果)：

6.代碼實(shí)現(xiàn)

void AdjustDown(int*a,int root,int n) {
	int parent = root;
	int child = 2 * parent + 1;//向下調(diào)整算法
	while (child < n) {
		if (child+1<n&&a[child] < a[child + 1]) {
			++child;
		}
		if (a[child] > a[parent]) {
			swap(a[child], a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
 
	  }
}
 
void  HeapSort(int* a, int n) {
	for (int i = (n - 2) / 2; i >= 0; i--) {
		 AdjustDown(a, i, n);       
	}
	int end = n - 1;
	while (end>0) {
		swap(a[0], a[end]);
		AdjustDown(a, 0, end);
		end--;
	}
 
}

7.復(fù)雜度分析

時(shí)間復(fù)雜度：O（N*log N)

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

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

選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。 它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰?，然后放到已排序的序列的末尾?以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零

1.算法描述

首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。

再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。

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

2.動(dòng)圖展示

3.圖解展示

4.代碼實(shí)現(xiàn)

void SelectSort(int* a, int n) {
	int left = 0;
	int right = n - 1;
	int minIndex = left, maxIndex = left;
	while (left < right) {
 
 
		for (int i = left; i <= right; i++) {
			if (a[i] < a[minIndex]) {
				minIndex = i;
			}
			if (a[i] > a[maxIndex]) {
				maxIndex = i;
			}
		}
		
		swap(a[left], a[minIndex]);
		if (left == maxIndex) {//如果max和left位置重疊，修正一下
			maxIndex = minIndex;
		}
		swap(a[right], a[maxIndex]);
		left++;
		right--;
	}
}

5.復(fù)雜度

時(shí)間復(fù)雜度：O（N^2)

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

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

快速排序

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

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

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

快速排序的名字起的是簡(jiǎn)單粗暴，因?yàn)橐宦牭竭@個(gè)名字你就知道它存在的意義，就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一了。雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n2)，但是人家就是優(yōu)秀，在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n logn) 的排序算法表現(xiàn)要更好，可是這是為什么呢，我也不知道。好在我的強(qiáng)迫癥又犯了，查了 N 多資料終于在《算法藝術(shù)與信息學(xué)競(jìng)賽》上找到了滿意的答案：快速排序的最壞運(yùn)行情況是 O(n2)，比如說(shuō)順序數(shù)列的快排。但它的平攤期望時(shí)間是 O(nlogn)，且 O(nlogn) 記號(hào)中隱含的常數(shù)因子很小，比復(fù)雜度穩(wěn)定等于 O(nlogn) 的歸并排序要小很多。所以，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言，快速排序總是優(yōu)于歸并排序。

1.算法簡(jiǎn)介

從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot）;

重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；

2.動(dòng)圖展示

3.圖解展示

• 挖坑法：

挖坑法：
1、定義begin和end分別指向數(shù)據(jù)的第一個(gè)元素和最后一個(gè)元素，找一個(gè)基準(zhǔn)值key（一般三數(shù)取中法）,置array[begin]的位置上的值為基準(zhǔn)值，并為第一個(gè)坑。
2、end從后往前走，找比key小的值，找到之后，將array[end]賦值給array[begin]，填充begin位置的坑，此時(shí)end位置為一個(gè)新的

3、begin從前往后走，找比key大的值，找到之后，將array[begin]賦值給array[end]，填充end位置的坑，此時(shí)begin位置為一個(gè)坑
4、此類方法依次填坑，當(dāng)begin和end相遇，則循環(huán)結(jié)束，將key的值填最后一個(gè)坑。

上面這種種單趟排序的方法我們稱為挖坑法

4.代碼實(shí)現(xiàn)

int partition2(int* a, int left, int right) {
	int mid = GetMindIndex(a, left, right);//三數(shù)取中
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}

三數(shù)取中代碼：

int GetMindIndex(int* a, int left, int right) {
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}

總代碼：

int GetMindIndex(int* a, int left, int right) {//三數(shù)取中
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
、
 
int partition2(int* a, int left, int right) {//挖坑法
	int mid = GetMindIndex(a, left, right);
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}
 
 
void QuickSort(int* a, int left, int right) {//快速排序
	if (left >= right)
		return;
	int mid = partition2(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
 
}

下面我們來(lái)看一下前后指針?lè)ǎ?/p>

• 前后指針?lè)ǎ?/li>

1、選擇一個(gè)基準(zhǔn)值key，定義兩個(gè)指針prev和cur（prev指向pPcur的前一個(gè)位置）
2、當(dāng)cur標(biāo)記的元素比key小時(shí)，prev和cur同時(shí)走，當(dāng)cur標(biāo)記的元素比key大時(shí)，只有cur繼續(xù)向前走（此時(shí)prev停下來(lái)），當(dāng)cur走到標(biāo)記的元素比key值小時(shí)，cur停下，prev向前走一步，此時(shí)交換arr[cur]和arr[prev],然后，cur繼續(xù)往前走。
3、當(dāng)cur走出界了，將prev位置的值與key交換。

對(duì)應(yīng)動(dòng)圖：

對(duì)應(yīng)代碼實(shí)現(xiàn)：

int partition3(int* a, int left, int right) {
	int cur = left + 1;
	int prev = left;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur) {
			swap(a[cur], a[prev]);
		  }
		++cur;
	}
	swap(a[prev], a[key]);
	return prev;
}

總代碼：

int GetMindIndex(int* a, int left, int right) {
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
 
 
 
int partition3(int* a, int left, int right) {
	int cur = left + 1;
	int prev = left;
	int key = left;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur) {
			swap(a[cur], a[prev]);
		  }
		++cur;
	}
	swap(a[prev], a[key]);
	return prev;
}
 
 
 
 
void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;
	int mid = partition2(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
 
}

• 左右指針?lè)?/li>

1、定義兩個(gè)指針begin（指向首元素）和end（指向尾元素），找一個(gè)基準(zhǔn)值key（一般三數(shù)取中法），置于序列的第一個(gè)元素，也就是begin的位置。
2、end從后往前走找比基準(zhǔn)值小的元素（找到后也停下），begin從前往后走找比基準(zhǔn)值key大的元素（找到后停下），
然后，交換arr[begin]和arr[end]，依次循環(huán)操作。
3、當(dāng)begin與end相遇，將array[begin]或array[end]與基準(zhǔn)值交換。

對(duì)應(yīng)圖解：

對(duì)應(yīng)代碼：

int partition(int* a, int start,int end) {
	int mid = GetMindIndex(a, start, end);
	int key = start;
	swap(a[key], a[mid]);
	while (start < end){
		while (start<end && a[end]>=a[key]) {
			--end;
		}
		while (start < end && a[start] <= a[key]) {
			++start;
		}
		swap(a[start], a[end]);
	 }
	swap(a[key], a[start]);
	return start;
}

代碼匯總：

int GetMindIndex(int* a, int left, int right) {//三數(shù)取中
	int mid = (left + right) >> 1;
	if (a[left] < a[mid]) {
		if (a[mid] < a[right]) {
			return mid;
		}
		else if (a[left] > a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
	else {
		if (a[mid] > a[right]) {
			return mid;
		}
		else if (a[left] < a[right]) {
			return left;
		}
		else {
			return right;
		}
	}
}
 
 
int partition(int* a, int start,int end) {//左右指針?lè)?
	int mid = GetMindIndex(a, start, end);
	int key = start;
	swap(a[key], a[mid]);
	while (start < end){
		while (start<end && a[end]>=a[key]) {
			--end;
		}
		while (start < end && a[start] <= a[key]) {
			++start;
		}
		swap(a[start], a[end]);
	 }
	swap(a[key], a[start]);
	return start;
}
 
 
void QuickSort(int* a, int left, int right) {
	if (left >= right)
		return;
	int mid = partition2(a, left, right);
	QuickSort(a, left, mid - 1);
	QuickSort(a, mid + 1, right);
 
}

快速排序需要注意的是：

如果選取左邊做key,并且使用的是左右指針?lè)ɑ蛘呤峭诳臃敲从疫呉茸卟拍鼙ＷC結(jié)果的正確性

int partition2(int* a, int left, int right) {//挖坑法
	int mid = GetMindIndex(a, left, right);
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {//這里一定要加等于否則有些情況會(huì)死循環(huán)
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {//這里一定要加等于否則有些情況會(huì)死循環(huán)
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}

挖坑法也是一樣的要加等于如果不加等于在某些極端情況下會(huì)死循環(huán)

比如：

5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

那么它就會(huì)死循環(huán)！?。。。。。。。。?/p>

• 快速排序非遞歸

在數(shù)據(jù)結(jié)構(gòu)中，即使遞歸能解決的，我們也有必要掌握非遞歸的方法。我們知道，堆空間比棧的空間大得多，當(dāng)我們?cè)跅Ｖ羞f歸調(diào)函數(shù)，會(huì)增加棧的開銷，棧幀會(huì)多。導(dǎo)致棧溢出程序崩潰。而在堆上遞歸調(diào)用函數(shù)，即使大的遞歸調(diào)用也不會(huì)使程序崩潰。這在安全方面就解決了棧溢出的問(wèn)題。

遞歸就是自上而下，再自下而上。也就滿足了我們數(shù)據(jù)結(jié)構(gòu)中的棧。所以這里我們可以借助棧來(lái)實(shí)現(xiàn)非遞歸的快速排序。

對(duì)應(yīng)代碼實(shí)現(xiàn)：

 
int partition2(int* a, int left, int right) {
	int mid = GetMindIndex(a, left, right);
	
	int key = a[left];
	swap(key, a[mid]);
	while (left < right) {
		while (left < right && a[right] >= key) {
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}
 
 
 
void QuickSortNonR(int* a, int n) {
	int right = n - 1;
	int left = 0;
	stack<int>ans;
	ans.push(right);
	ans.push(left);
	while (!ans.empty()) {
		int left = ans.top();
		ans.pop();
		int right = ans.top();
		ans.pop();
		int mid = partition(a, left, right);
		if (left + 1 < mid) {
			ans.push(mid - 1);
			ans.push(left);
		}
		if (mid + 1 < right) {
			ans.push(right);
			ans.push(mid + 1);
		}
	}
 
}

時(shí)間復(fù)雜度

歸并排序：

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

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

• 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；
• 自下而上的迭代；然而，在 JavaScript 中這種方式不太可行，因?yàn)檫@個(gè)算法的遞歸深度對(duì)它來(lái)講太深了。說(shuō)實(shí)話，我不太理解這句話。意思是 JavaScript 編譯器內(nèi)存太小，遞歸太深容易造成內(nèi)存溢出嗎？還望有大神能夠指教。和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是 O(nlogn) 的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。

1.算法分析

• 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列；
• 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
• 比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
• 重復(fù)步驟 3 直到某一指針達(dá)到序列尾；
• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

2.動(dòng)圖展示

3.圖解展示

可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實(shí)現(xiàn)（也可采用迭代的方式去實(shí)現(xiàn)）。分階段可以理解為就是遞歸拆分子序列的過(guò)程，遞歸深度為log2n。

合并相鄰有序子序列

再來(lái)看看治階段，我們需要將兩個(gè)已經(jīng)有序的子序列合并成一個(gè)有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個(gè)已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來(lái)看下實(shí)現(xiàn)步驟

對(duì)應(yīng)代碼實(shí)現(xiàn)：

 
void _MerageSort(int* a, int* tmp , int left, int right) {
	if (left >= right)return;
	int mid = (left + right) >> 1;
	_MerageSort(a,tmp, left, mid);
	_MerageSort(a,tmp, mid + 1, right);
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int index = left;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[index++] = a[begin1++];
		}
		else {
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1<=end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[index++] = a[begin2++];
	}
	for (int i = left; i <= right; i++) {
		a[i] = tmp[i];
	}
 }
 
 
 
 
 
void MerageSort(int* a, int n) {
	
	int* tmp = new int[n];
	_MerageSort(a, tmp, 0, n - 1);
delete[] tmp;
 
}

非遞歸：

基本思路：看作是一顆倒過(guò)來(lái)的滿二叉樹，兩兩成對(duì)

實(shí)現(xiàn)思路

基本思路：

1、在State0初始狀態(tài)時(shí)，兩兩合并，合并用到的算法是“合并有序的數(shù)組 merge sorted array”。即每次合并得到的都是有序的數(shù)組。

2、兩兩合并的規(guī)則是：將兩個(gè)相同序列長(zhǎng)度的序列進(jìn)行合并，合并后的序列長(zhǎng)度double。

第一趟合并（merge 1）調(diào)用了4次merge sorted array，得到了4個(gè)有序的數(shù)組："5, 8"，"3, 9"，"6, 4"，"1, 4"（每個(gè)合并后的序列長(zhǎng)度為2）

第二趟合并（merge 2）調(diào)用了2次merge sorted array，得到了2個(gè)有序的數(shù)組："3, 5, 8, 9"，"1, 4, 6, 11''（每個(gè)合并后的序列長(zhǎng)度為4）

3、按步驟1的思想以此類推，經(jīng)過(guò)多次合并最終得到有序的數(shù)組，也就是State3。

可以看出經(jīng)過(guò)一共3趟合并，最終得到有序的數(shù)組。

可以看出每趟要執(zhí)行的合并次數(shù)不同，第一趟合并執(zhí)行4次，第二趟合并執(zhí)行2次，第三趟合并行1次。

看了上述的算法思想，可以知道算法可以設(shè)計(jì)成兩層循環(huán)

• 外層循環(huán)遍歷趟數(shù)
• 內(nèi)層循環(huán)遍歷合并次數(shù)

但是我們會(huì)發(fā)現(xiàn)排序元素的個(gè)數(shù)不一定是2^i

如圖可知，一般數(shù)組元素的個(gè)數(shù)不一定是2i個(gè)。右邊多出的"10, 7, 2"子樹可以視作一般情況的情形。雖然元素個(gè)數(shù)不一定是2i個(gè)，但是任意元素個(gè)數(shù)的n，必然可以拆分成2j + m個(gè)元素的情形（數(shù)學(xué)條件不去深究）由圖可知，特殊情形思想中的兩兩合并的規(guī)則不能滿足一般情況的合并需求

• 圖中灰色的箭頭代表無(wú)需合并，因?yàn)檎也坏脚鋵?duì)的元素。
• 圖中墨藍(lán)色的箭頭代表兩個(gè)長(zhǎng)度不相等的元素也需要進(jìn)行合

將上述的合并需求稱為長(zhǎng)短合并，容易知道長(zhǎng)短合并僅存在1次或0次。

下面討論的合并前/后的序列長(zhǎng)度特指兩兩合并后得到的序列長(zhǎng)度。

合并循環(huán)設(shè)計(jì)：

雖然一般情形與特殊情形的合并規(guī)則有差別（一般情形復(fù)雜），但是可以設(shè)計(jì)一個(gè)通用的合 并趟數(shù)條件。

設(shè)置變量：記錄每趟合并后序列的長(zhǎng)度，其中k是趟次

• 通過(guò)觀察發(fā)現(xiàn)：每次合并后序列的大小有規(guī)律，第一趟后合并的序列大小都是2，第二趟合并后的序列大小都是4，以此類推..
• "10, 7, 2"這三個(gè)元素組合而成的序列長(zhǎng)度雖然不滿足上述的規(guī)律，但是并不影響趟數(shù)的計(jì)算。24 = 16 ≥ 11，4趟后循環(huán)結(jié)束。
• 可以設(shè)計(jì)成：if 最后合并后的序列長(zhǎng)度≥實(shí)際元素的個(gè)數(shù)n，這時(shí)可以說(shuō)明循環(huán)結(jié)束

對(duì)應(yīng)代碼實(shí)現(xiàn)：

void _Merge(int* a, int* tmp, int begin1, int end1, int begin2, int end2) {
	int i = begin1;
	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2) {
		if (a[begin1] < a[begin2]) {
			tmp[index++] = a[begin1++];
		}
		else {
			tmp[index++] = a[begin2++];
		}
	}
	while (begin1 <= end1) {
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2) {
		tmp[index++] = a[begin2++];
	}
 
	for (; i <= end2; i++) {
		a[i] = tmp[i];
	}
}
void mergeSort(int* a, int n) {
	int* tmp = new int[n];
	int gap = 1;
	while (gap < n) {
 
		for (int i = 0; i < n; i+=2*gap) {
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (begin2 >= n) {//說(shuō)明已經(jīng)排序完成
				break;
			}
 
			if (end2 >= n) {//修正區(qū)間
				end2 = n - 1;
			}
 
			_Merge(a, tmp, begin1, end1, begin2, end2);
 
		}
 
		gap *= 2;
	}
	delete[]tmp;
}

排序總結(jié)

如有錯(cuò)誤請(qǐng)指正?。。?！

到此這篇關(guān)于深入學(xué)習(xí)C語(yǔ)言中常見的八大排序 的文章就介紹到這了,更多相關(guān)C語(yǔ)言 八大排序 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！