快速排序也是一種複雜度為 O ( n l o g n ) O(nlogn) O(nlogn)的排序算法，但它的效率比同等複雜的排序算法還要高，是以在實踐中會經常使用。
原理
快速排序的思想是将數組分為兩個部分，一部分小于 v v v，另一部分大于 v v v，這個 v v v也稱為基準數，一般選取數組第一個數作為基準數。它的實作效果是這樣的，當分為兩個數組後，每個單獨的數組又可以使用該方法排序，直到隻有最後一個元素，那這裡又可以使用遞歸方法了。我們将數組分為兩部分的過程稱為partition。
partition的實作思路如下：假設第一個元素為基準點，并将其索引記為 l l l，此時已經有一部分資料進行了整理，得到了 < v <v <v，和 > v >v >v的部分，規定 a r r [ l + 1... j ] < v arr[l+1...j]<v arr[l+1...j]<v， a r r [ j + 1... i − 1 ] > v arr[j+1...i-1]>v arr[j+1...i−1]>v， i i i表示周遊中目前元素索引。
如果 e > v e>v e>v就很簡單了，直接将索引值向後移動一位即可
如果 e < v e<v e<v，稍微麻煩一點，将 > v >v >v部分的第一個資料與 e e e交換，同時 j + + , i + + j++,i++ j++,i++即可。
周遊完成後，将 v v v與 a r r [ j ] arr[j] arr[j]交換， v v v也就放在了正确的位置。
此時 a r r [ l . . . j − 1 ] < v arr[l...j-1]<v arr[l...j−1]<v， a r r [ j + 1... i ] > v arr[j+1...i]>v arr[j+1...i]>v, a r r [ j ] = v arr[j]=v arr[j]=v，接下來對兩部分數組分别排序即可。
梳理以上過程，可得快排的實作步驟：
1.partition将數組正确分為兩部分
2.對兩部分遞歸partition，直至遞歸結束。
實作
#include <iostream>
#include <algorithm>
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++){ //注意是<=r,而不是<r
if(arr[i]<v){
swap(arr[i],arr[j+1]);
j++;
}
}
swap(arr[j],arr[l]);
return j;
}
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);
}
優化
首先，對于小規模數組排序可以采用插入排序，提高小規模數組排序運作速度。具體代碼隻需要将遞歸結束的條件改為插入排序。
template <typename T>
void __quickSort(T arr[], int l, int r){
if(r-l<=15){
insertionSort(arr,l,r); //具體插入排序的代碼可以參考之前的文章
return;
}
int p = partition(arr, l ,r);
__quickSort(arr, l, p-1);
__quickSort(arr, p+1, r);
}
但這隻是一個小小的修改，此時的快速排序有一個緻命的弱點會使時間複雜度變為 O ( n 2 ) O(n^2) O(n2)。這個問題就出現在解決近乎有序數組上，如果一個有序數組，快速排序每次選擇第一個元素作為基準值，在partition操作後基準值的位置幾乎沒有移動，那就相當于 n n n個資料被分為1 和 n − 1 n-1 n−1個，那麼到最後就需要遞歸n次，同時partition的操作時間複雜度也是 O ( n ) O(n) O(n)，此時的複雜度就退化為 O ( n 2 ) O(n^2) O(n2)了。是以如果能夠盡量選擇中間的元素，那麼複雜度就能夠達到 O ( n l o g n ) O(nlogn) O(nlogn)。
為了解決這個問題，我們可以随機選擇一個數作為基準數，這樣就可以極大的減小每次partition後數組的不均衡性。此時在最差的情況下快排的時間複雜度仍然為 O ( n 2 ) O(n^2) O(n2),但是這種機率是非常低的，它的時間複雜度期望為 O ( n l o g n ) O(nlogn) O(nlogn)。
#include <iostream>
#include <algorithm>
#include <ctime>
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++){ //注意是<=r,而不是<r
if(arr[i]<v){
swap(arr[i],arr[j+1]);
j++;
}
}
swap(arr[j],arr[l]);
return j;
}
template <typename T>
void __quickSort(T arr[], int l, int r){
if(r-l<=15){
insertionSort(arr,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);
}
參考：https://coding.imooc.com/learn/list/71.html