快速排序（Quick Sort）
算法思想：在待排序表L[1...n]中任取一個元素pivot作為基準，通過一趟排序?qū)判虮韯澐譃楠毩⒌膬刹糠諰[1...k-1]和L[k+1...n]媳维，使得L[1...k-1]中所有元素小于pivot冰肴，L[k+1...n]中所有元素大于或等于pivot粉寞，則pivot放在了其最終位置L(k)上，這個過程稱為一趟快速排序肮之。而后分別遞歸地對兩個子表重復(fù)上述過程捣作，直至每部分內(nèi)只有一個元素或空為止测柠，即所有元素放在了最終的位置上主卫。
算法演示：
基本代碼如下：
// 對arr[l...r]部分進行partition操作
// 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template<typename T>
int __partition(T arr[], int l, int r) {
T v = arr[l];
// arr[l+1...j] < v; arr[j+1...i) > v
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr[j + 1], arr[i]);
j++;
}
}
swap(arr[l], arr[j]);
return j;
}
// 對arr[l...r]部分進行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r) {
if (l >= r)
return;
int p = __partition(arr, l, r);
__quickSort(arr, l, p - 1);
__quickSort(arr, p + 1, r);
}
template<typename T>
void quickSort(T arr[], int n) {
__quickSort(arr, 0, n - 1);
}
好了鹃愤，按照慣例我們將同時調(diào)用快速排序和歸并排序進行測試，看看哪種算法的運行效率更高完域，其結(jié)果如下（隨機數(shù)據(jù)）：
Quick Sort : 0.029 s
Merge Sort : 0.03 s
我們從結(jié)果中發(fā)現(xiàn)快速排序算法的運行效率與優(yōu)化后的歸并排序算法的效率不相上下软吐。不知大家有沒有發(fā)現(xiàn)歸并排序算法前“優(yōu)化后”這三個字加粗顯示，這么做其實是為了想告訴大家吟税，我們的快速排序算法還有優(yōu)化的空間凹耙，而歸并排序算法已是目前最優(yōu)的結(jié)果。
那么肠仪，我們將怎么樣優(yōu)化快速排序呢肖抱？我們先回想一下對歸并排序的優(yōu)化操作，在歸并排序算法中异旧，我們針對數(shù)據(jù)較少時采用插入排序意述，類似的，我們也可以進行這樣的操作。
有一個重要的問題荤崇，我們始終忽略了拌屏。這就是我們沒有測試在近乎有序的隨機數(shù)據(jù)情況下，兩種排序算法的運行效率术荤。大家若學習過數(shù)據(jù)結(jié)構(gòu)這門課程就會知道倚喂，快速排序有個致命的缺陷——在處理近乎有序的隨機數(shù)據(jù)時，其時間復(fù)雜度會變?yōu)镺(n2)瓣戚。
為什么會成這種結(jié)果呢端圈？這是因為我們在對待排序表進行劃分時，不像歸并排序算法一樣一分為二子库，而是先找到一個元素pivot作為基準舱权，使得待排序列表在基準之前的元素均小于它，在基準后面的元素均大于它刚照。當快速排序算法處理近乎有序的隨機數(shù)據(jù)時刑巧，這種劃分操作就會類似于冒泡排序算法的處理操作，所以在這種情況下時間復(fù)雜度就變?yōu)镺(n2)无畔。
為了解決這種問題啊楚，我們就不再采用選用待排序表第一個元素作為基準（請大家不要被嚴奶奶版的數(shù)據(jù)結(jié)構(gòu)中快速排序算法的講解所束縛，推薦在學習數(shù)據(jù)結(jié)構(gòu)時翻閱“黑皮書”對數(shù)據(jù)結(jié)構(gòu)做進一步了解）浑彰，而選用待排序列表中盡可能中間的元素作為基準恭理，即隨機選擇一個數(shù)。（注：這里不過多敘述其原因郭变，具體請參考算法導(dǎo)論或“黑皮”版數(shù)據(jù)結(jié)構(gòu)與算法分析颜价。）
改進后的快速排序算法基本代碼如下：
// 對arr[l...r]部分進行partition操作
// 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template<typename T>
int __partition(T arr[], int l, int r) {
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
// arr[l+1...j] < v; arr[j+1...i) > v
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
swap(arr[j + 1], arr[i]);
j++;
}
}
swap(arr[l], arr[j]);
return j;
}
// 對arr[l...r]部分進行快速排序
template<typename T>
void __quickSort(T arr[], int l, int r) {
if (l >= r)
return;
int p = __partition(arr, l, r);
__quickSort(arr, l, p - 1);
__quickSort(arr, p + 1, r);
}
template<typename T>
void quickSort(T arr[], int n) {
srand(time(NULL));
__quickSort(arr, 0, n - 1);
}
讓我們看看運行的結(jié)果吧（近乎有序的隨機數(shù)據(jù)）诉濒。
Quick Sort : 0.035 s
Merge Sort : 0.005 s
我們發(fā)現(xiàn)快速排序算法的運行效率雖比上歸并排序周伦，但其性能已經(jīng)遠遠好于優(yōu)化前的性能。
除此之外未荒，我們的快速排序還可進行優(yōu)化专挪。例如在含有大量重復(fù)數(shù)據(jù)的情況下，我們的快速排序算法的運行效率依舊不高片排。這里我們向大家展示一下快速排序算法的龜速寨腔！
首先，我們按如下代碼修改main()中的代碼：
int main() {
int n = 100000;
int *arr_1 = SortTestHelper::generateRandomArray(n, 0, 10);
int *arr_2 = SortTestHelper::copyIntArray(arr_1, n);
SortTestHelper::testSort("Quick Sort", quickSort, arr_1, n);
SortTestHelper::testSort("Merge Sort", mergeSort, arr_2, n);
delete[] arr_1;
delete[] arr_2;
return 0;
}
然后我們運行程序率寡，看看其運行結(jié)果：
Quick Sort : 1.459 s
Merge Sort : 0.017 s
在處理含有大量重復(fù)數(shù)據(jù)時，快速排序算法的運行效率可稱為龜速耙惫病每界！這是因為我們在對待排序表進行劃分操作時，由于數(shù)據(jù)中含有大量的重復(fù)數(shù)據(jù)幻捏，會有很大概率上將待排序表劃分得極度不平衡，從而導(dǎo)致快速排序算法退化為時間復(fù)雜度為O(n2)篡九。
那么對于這種情況，我們優(yōu)化思路的算法演示為：
實際上榛臼，圖中兩側(cè)的數(shù)據(jù)應(yīng)該是如下圖所示：
優(yōu)化的基本代碼如下：
// 對arr[l...r]部分進行partition操作
// 返回p，使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template<typename T>
int __partition2(T arr[], int l, int r) {
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
// arr[l+1...i) <= v; arr(j...r] >= v
int i = l + 1, j = r;
while (true) {
while (i <= r && arr[i] < v) i++;
while (j >= l + 1 && arr[j] > v) j--;
if (i > j) break;
swap(arr[i], arr[j]);
i++;
j--;
}
swap(arr[l], arr[j]);
return j;
}
// 對arr[l...r]部分進行快速排序
template<typename T>
void __quickSort2(T arr[], int l, int r) {
if (l >= r)
return;
int p = __partition2(arr, l, r);
__quickSort2(arr, l, p - 1);
__quickSort2(arr, p + 1, r);
}
template<typename T>
void quickSort2(T arr[], int n) {
// 設(shè)置當前的時間值為種子,那么種子總是變化的航揉，所以以該種子產(chǎn)生的隨機數(shù)總是變化的
srand(time(NULL));
__quickSort2(arr, 0, n - 1);
}
那我們來看看這次優(yōu)化后的結(jié)果吧。
Quick Sort : 1.487 s
Merge Sort : 0.018 s
Quick Sort 2 : 0.016 s
通過這次優(yōu)化金刁，我們的快速排序算法的運行效率有了顯著地提升。實際上尤蛮，我們將這種方式的快速排序算法稱之為雙路快速排序算法。除此之外产捞，在處理含有大量重復(fù)數(shù)據(jù)的數(shù)據(jù)時醇锚，我們還有一個更為經(jīng)典的快速排序算法，通常我們將其稱為三路快速排序算法坯临。
其實這個排序算法的思路很簡單焊唬，其算法演示如下圖所示：
三路快速排序算法的基本代碼如下：
// 三路快速排序
// 將arr[l...r]分為 < v; == v; > v 三部分
// 之后遞歸對 < v; > v 兩部分進行三路快速排序
template<typename T>
void __quickSort3(T arr[], int l, int r) {
if (l >= r)
return;
// partition操作
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
// arr[l+1...lt] < v
int lt = l;
// arr[gt...r] > v
int gt = r + 1;
// arr[lt+1...i) == v
int i = l + 1;
while (i < gt) {
if (arr[i] < v) {
swap(arr[i], arr[lt + 1]);
lt++;
i++;
} else if (arr[i] > v) {
swap(arr[i], arr[gt - 1]);
gt--;
} else {
// arr[i] == v
i++;
}
}
swap(arr[l], arr[lt]);
__quickSort3(arr, l, lt - 1);
__quickSort3(arr, gt, r);
}
template<typename T>
void quickSort3(T arr[], int n) {
// 設(shè)置當前的時間值為種子,那么種子總是變化的，所以以該種子產(chǎn)生的隨機數(shù)總是變化的
srand(time(NULL));
__quickSort3(arr, 0, n - 1);
}
好了看靠，我們調(diào)用一些三路快速排序算法并運行程序赶促，其結(jié)果如下：
Quick Sort : 1.393 s
Merge Sort : 0.018 s
Quick Sort 2 : 0.015 s
Quick Sort 3 : 0.006 s
