前言

快速排序是交換排序中的一種，是Hoare于1962年提出的一種二叉樹結構的交換排序方法，類似于二叉樹的前序遍歷，

主要思想：
■ 任取待排序元素序列中的某元素作為關鍵字，
■ 按照該關鍵字將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，
■ 然后將左右子序列重復該程序，直到所有元素都排列在相應位置上為止，

區間劃分左右部分常見方式

1、雙指標法

實作程序：如下圖 ！

程序總結：
■先將begin的索引作為keyIndex記錄下來，然后使用兩個指標，一個指向end，一個指向begin，
■讓end指標先走，找比arr[keyIndex]小的值，然后begin指標開始走，找比arr[keyIndex]大的值，
■然后將begin指標和end指標找到的值交換，重復上述程序直到begin和end指標相遇，
■最后將a[end]和a[keyIndex]交換，

C語言代碼實作

int PartSort1(int* a, int begin, int end) {
	int keyIndex = begin;
	//注意一定要讓end先移動
	while (begin < end) {
		while (begin < end && a[end] >= a[keyIndex]) end--;//注意這個地方一定要取等
		while (begin < end && a[begin] <= a[keyIndex]) begin++;//注意這個地方一定要取等
		swap(a + begin, a + end);
	}
	swap(a + end, a + keyIndex);
	return begin;
}

注意代碼中的細節

代碼中注釋地方一定要取等

看這種情況，如下圖！！

選最左邊的值為關鍵字，一定要讓end先走，相反選最右邊的值，讓begin先走

究其原理：哪個指標先走，關鍵字最后就與那個指標找的值交換，我們的end指標是找的比key小的值，而begin找的是比key大的值，我們的關鍵字是第一個，所以最后要將比關鍵字小的值換到關鍵字現在的位置上，所以要讓end先走，如果我們選取最后一個作為關鍵字，那么就要讓begin先走，

2、挖坑法

實作程序：如下圖 ！

程序總結：
■先將a[begin]的key值保留下來形成坑，然后使用兩個指標，一個指向end，一個指向begin，
■讓end指標先走，找比key小的值，讓a[begin]=a[end]，此時end位置形成新坑，然后begin指標開始走，找比key大的值，然后讓a[end]=a[begin]，此時end指標形成新坑，
■重復上述程序，最后讓begin和end指標相遇，
■最后a[begin]=key，將key的值填入坑當中，

C語言代碼實作

int PartSort2(int* a, int begin, int end) {
	int key= a[begin];
	while (begin < end) {
		//一定要然end先走
		while (begin < end && a[end] >= key) end--;//一定要讓a[end]>=key，一定要取等，
		a[begin] = a[end];
		while (begin < end && a[begin] <= key) begin++;//一定要讓a[begin]<=key，一定要取等，
		a[end] = a[begin];
	}
	a[begin] = key;
	return begin;
}

注意代碼中的細節

代碼中注釋地方一定要取等

看這種情況，如下圖！！

選最左邊的值為關鍵字，一定要讓end先走，相反選最右邊的值，讓begin先走

究其原理：我們選取第一個元素作為坑，所以要選擇比key小的值來覆寫坑，所以要讓end先走，如果我們選最后一個作為坑，那么我們就要讓begin先走，

3、前后指標法

實作程序：如下圖 ！

程序總結：
■先將a[end]的最為關鍵字，然后使用兩個指標，一個指標prev指向begin-1，一個指標cur指向begin，
■當a[cur]<a[end]時，++prev，然后交換a[prev]和a[cur]的值，
■重復上述程序，直到cur==end，
■最后++prev，然后a[++prev]和a[end]交換，

C語言代碼實作

int PartSort3(int* a, int begin, int end) {
	int prev = begin- 1, cur = end;
	while (cur < end) {
		if (a[cur] < a[end] && ++prev!=cur) {
			swap(a + prev, a + cur);
		}
		cur++;
	}
	swap(&a[++prev],&a[end]);
	return prev;
}

遞回實作快速排序

C語言代碼實作

void QuickSort(int* a, int left, int right) {
	assert(a);
	if (left >= right) {
		return;
	}
	int partition = PartSort2(a,left,right);//隨便呼叫上面三種單區間排序方法，類似于二叉樹的前序遍歷，
	QuickSort(a,left,partition-1);
	QuickSort(a, partition+1, right);
}

三數取中優化排序時間復雜度

特殊情況看下圖 ！

我們發現當序列有序時，如果再采取上面的方法，那么時間復雜度將是N^2，所以此時我們選取 前中后 中值為中間的值和關鍵字的位置進行交換，那么我們再進行排序的序列的時間復雜度基本上被優化為N*logN，

C語言代碼實作

int GetMindIndex(int* a, int begin, int end) {
	int mid = (begin + end) >> 1;
	if (a[mid] < a[begin]) {
		if (a[begin] < a[end]) {
			return begin;
		}
		else if (a[end]<a[mid]) {
			return mid;
		}
		else {
			return end;
		}
	}
	else {//a[mid] >= a[begin]
		if (a[begin] > a[end]) {
			return begin;
		}
		else if (a[mid] < a[end]) {
			return mid;
		}
		else return end;
	}
}
int PartSort2(int* a, int begin, int end) {
	int minIndex = GetMindIndex(a, begin,end);
	swap(a + begin, a + minIndex);
	int key= a[begin];
	while (begin < end) {
		//一定要然end先走
		while (begin < end && a[end] >= key) end--;//一定要讓a[end]>=key，一定要取等，
		a[begin] = a[end];
		while (begin < end && a[begin] <= key) begin++;//一定要讓a[begin]<=key，一定要取等，
		a[end] = a[begin];
	}
	a[begin] = key;
	return begin;
}

非遞回實作快速排序

遞回實作快速排序的缺陷

■ 效率稍低：遞回建立堆疊幀有所消耗，但是對于現代計算機，這個被優化得維護其微可以忽略不計，但是資料大了之后還是有所消耗，

■ 容易導致堆疊溢位：遞回最大得缺陷是，當堆疊幀的深度太深，那么可能導致堆疊溢位，因為系統堆疊空間一般不大在M級別，如果我們使用資料結構模擬非遞回，資料是存盤在堆上的，堆是G級別的空間，

遞回該非遞回的方法

■ 用回圈一些簡單遞回才能改回圈：斐波拉契數列求解等，，

■ 堆疊模擬存盤資料非遞回，其實遞回的主要思想就是堆疊，只不過遞回是使用的系統堆疊，

C++代碼

void QuickSortNonR(int* a, int left, int right) {
	stack<int> stk;
	stk.push(right);
	stk.push(right);
	while (!stk.empty()) {
		int begin=stk.top();
		stk.pop();
		int end = stk.top();
		stk.pop();
		int partition = PartSort02(a,begin,end);
		if (begin<partition-1) {
			stk.push(partition - 1);
			stk.push(begin);
		}
		if (partition+1 < end) {
			stk.push(end);
			stk.push(partition - 1);
		}
	}
}

快速排序的特性總結

1. 快速排序整體的綜合性能和使用場景都是比較好的，如果加了三數取中，那么我們還能較好的避開最壞的情況，所以才敢叫做叫快速排序，

2. 平均時間復雜度：O(NlogN)，最好情況：O(NlogN)，最壞情況：O(N^N)，

3. 空間復雜度：O(logN)~O(N)，

4. 穩定性：不穩定，