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

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

冒泡排序

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

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

1.算法描述

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

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

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

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

2.動圖展示

3.圖解展示

4.代碼實現(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)沒有發(fā)生交換，說明此時已經(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ù)雜度分析

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

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

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

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

插入排序

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

1.算法描述

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。

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

2.動圖展示

3.圖解展示

4.代碼實現(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ù)雜度分析

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

希爾排序

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

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

• 插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時，效率高，即可以達到線性排序的效率；
• 但插入排序一般來說是低效的，因為插入排序每次只能將數(shù)據(jù)移動一位

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

1.算法描述

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

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

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

2.動圖展示

3.圖解展示

或者：

4.代碼實現(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、時間復(fù)雜度：O(N^2)
希爾排序最壞的時間復(fù)雜度依然為 O ( N 2 )
但其能夠有效改善直接插入排序序列無序且長度大時的大長度數(shù)列移位。希爾排序中對于增量序列的選擇十分重要，直接影響到希爾排序的性能，本文使用的是希爾增量，還有 Hibbard 增量，時間復(fù)雜度為 O(N^1.5) 也可以認為是O ( N^log N)空間復(fù)雜度：O(1)
未借助其它輔助空間。

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

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

堆排序

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

1.算法描述

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

2.動圖展示

3.圖解展示

1.預(yù)備知識：

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

2.大根堆和小根堆：

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

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

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

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

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

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

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

所以上面兩個數(shù)組可以腦補成堆結(jié)構(gòu)，因為他們滿足堆的定義性質(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)造

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

假設(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é)點進行比較，如果插入的數(shù)比父結(jié)點大，則與父結(jié)點交換，否則一直向上交換，直到小于等于父結(jié)點，或者來到了頂端）

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

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

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

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

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

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

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

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

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

重點建堆的時間復(fù)雜度：因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間復(fù)雜度本來看的就是近似值，多幾個節(jié)點不影響最終結(jié)果)：

6.代碼實現(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ù)雜度分析

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

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

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

選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。 它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最?。ù螅┰?，然后放到已排序的序列的末尾。 以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零

1.算法描述

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

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

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

2.動圖展示

3.圖解展示

4.代碼實現(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ù)雜度

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

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

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

快速排序

快速排序是由東尼·霍爾所發(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ǔ)上的遞歸分治法。

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

1.算法簡介

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

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

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

2.動圖展示

3.圖解展示

• 挖坑法：

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

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

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

4.代碼實現(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);
 
}

下面我們來看一下前后指針法：

• 前后指針法：

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

對應(yīng)動圖：

對應(yīng)代碼實現(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);
 
}

• 左右指針法

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

對應(yīng)圖解：

對應(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) {//左右指針法
	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,并且使用的是左右指針法或者是挖坑法那么右邊要先走才能保證結(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án)
			--right;
		}
		a[left] = a[right];
		while (left < right && a[left] <= key) {//這里一定要加等于否則有些情況會死循環(huán)
			++left;
		}
		a[right] = a[left];
 
	}
	a[left] = key;
	return left;
}

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

比如：

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

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

• 快速排序非遞歸

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

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

對應(yīng)代碼實現(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);
		}
	}
 
}

時間復(fù)雜度

歸并排序：

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

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

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

1.算法分析

• 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；
• 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；
• 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；
• 重復(fù)步驟 3 直到某一指針達到序列尾；
• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾

2.動圖展示

3.圖解展示

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

合并相鄰有序子序列

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

對應(yīng)代碼實現(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;
 
}

非遞歸：

基本思路：看作是一顆倒過來的滿二叉樹，兩兩成對

實現(xiàn)思路

基本思路：

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

2、兩兩合并的規(guī)則是：將兩個相同序列長度的序列進行合并，合并后的序列長度double。

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

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

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

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

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

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

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

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

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

• 圖中灰色的箭頭代表無需合并，因為找不到配對的元素。
• 圖中墨藍色的箭頭代表兩個長度不相等的元素也需要進行合

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

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

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

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

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

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

對應(yīng)代碼實現(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) {//說明已經(jīng)排序完成
				break;
			}
 
			if (end2 >= n) {//修正區(qū)間
				end2 = n - 1;
			}
 
			_Merge(a, tmp, begin1, end1, begin2, end2);
 
		}
 
		gap *= 2;
	}
	delete[]tmp;
}

排序總結(jié)

如有錯誤請指正！?。?！

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

最新評論