快速排序， 是最經典的排序算法之一。快速排序擁有良好的時間複雜度，平均為 O(nlog2n) ，最差為 O(n2) 。在這裡，我們不妨略略深入讨論一下快速排序：
時間複雜度分析
首先說平均時間複雜度。以比較常用的從兩頭進行掃描的算法為例，算法主要分兩步：
1. 是快排的核心：“分趟”。就是“每一趟”下來，找到某一個元素應該待的位置，這個元素一般被稱為pivot；
2.再分别對pivot前後兩部分進行遞歸排序。
#include <iostream>
using namespace std;
int partition(int *a, int left, int right)
{
int key = a[left];
while(left < right){
while(left < right && a[right] >= key) right--; //從右找到第一個比key小的
a[left] = a[right];
while(left < right && a[left] <= key) left++; //從左找到第一個比key大的
a[right] = a[left];
}
a[left] = key; //基準歸位
return left;
}
void Qsort(int *a, int left, int right)
{
if(left < right){ //元素長度>1時
int pos = partition(a, left, right);
Qsort(a, left, pos - ); //pos本身不需要再動了
Qsort(a, pos + , right);
}
}
int main()
{
int a[] = {, , , , , , , , };
Qsort(a, , sizeof(a) / sizeof(a[]) - );
for(int i = ; i < sizeof(a) / sizeof(a[]); i++)
{
cout << a[i] << " ";
}
return ;
}
顯然，一趟下來，pivot被固定的位置越趨于中間，前後兩部分子序列的遞歸調用就越均衡，這時候時間複雜度是最小的。
T(n) <= n + 2T(n/)
<= 2n + 4T(n/)
<= 3n + 8T(n/)
...
<= (log n)n + nT() = O(nlog n)
是以，為 O(nlog2n) 。
最差的情況下，也就是pivot被固定後的位置總是在最前面或最後面，導緻前後兩部分子序列實際隻是一個子序列。這也就意味着，原代排序列本身就是有序的，要麼從小到大，要麼從大到小。比如從小到大：此時，第一趟經過n-1次比較，将第一個元素固定在首位；第二趟經過n-2次比較，将第二個元素固定在第二位，以此類推，n個元素總共要比較 1+2+3+...+(n−1)=n(n−1)/2 次，是以複雜度為 O(n2) 。當然，如果從簡單形象的角度去了解，一般的快排執行過程大概是二叉樹形結構，而最差情況則是退化成了連結清單。
優化
優化大緻有三種比較有效的方法。
使用插入排序
在子序列比較小的時候，其實插排是比較快的，因為對于有序的序列，插排可以達到 O(n) 的複雜度，如果序列比較小，則和大序列比起來會更加有序，這時候使用插排效率要比快排高。其實作方法也很簡單：快排是在子序列元素個數變成1是，才停止遞歸，我們可以設定一個門檻值n，假設為5，則大于5個元素，子序列繼續遞歸，否則選用插排。（其實在C++的STL中，歸并算法就是采用了這個思路，當子序列小到一定程度的時候，直接選用插排對子序列進行排序）
快排是在待排數列越趨近于有序時變得越慢，複雜度越高，調用插排可以很好的解決這個問題。
pivot選用中位數
對于一般的快排，我們直接簡單的就取最左或最右的資料作為pivot，這樣的話很可能遇到比較極端的pivot，使得劃分出來的左右子序列變得不均衡。如果選取最左、中間、最右這三個值的中位數的話，顯然會使得pivot更加“不偏激”，這樣劃分出來的左右子序列也會更加均衡。
選用中位數和調用插排一樣，都能避免數列比較有序時複雜度變高的問題。
三路劃分
快排是二路劃分的算法。如果待排序列中重複元素過多，也會大大影響排序的性能。這時候，如果采用三路劃分，則會很好的避免這個問題。
如果一個帶排序列重複元素過多，我們先随機選取一個pivot，設為T，那麼數列可以分為三部分：小于T，等于T，大于T：
等于T的部分就無需再參與後續的遞歸調用了，速度自然就大大提升了。
但是問題在于怎麼高效地将序列劃分為三部分！
如下圖，我們可以設定四個遊标，左端a、b，右端c、d。b、c的作用跟之前兩路劃分時候的左右遊标相同，就是從兩端向中間周遊序列，并将周遊到的元素與pivot比較，如果等于pivot，則移到兩端（b對應的元素移到左端，c對應的元素移到右端。移動的方式就是拿此元素和a或d對應的元素進行交換，是以a和d的作用就是記錄等于pivot的元素移動過後的邊界），反之，如果大于或小于pivot，還按照之前兩路劃分的方式進行移動。這樣一來，中間部分就和兩路劃分相同，兩頭是等于pivot的部分，我們隻需要将這兩部分移動到中間即可。
參考算法如下，摘自http://blog.csdn.net/jlqCloud/article/details/46939703：
private void quickSort(int[] a, int left, int right) {
if (right <= left)
return;
/*
* 工作指針
* p指向序列左邊等于pivot元素的位置
* q指向序列右邊等于Pivot元素的位置
* i指向從左向右掃面時的元素
* j指向從右向左掃描時的元素
*/
int p, q, i, j;
int pivot;// 錨點
i = p = left;
j = q = right - ;
/*
* 每次總是取序列最右邊的元素為錨點
*/
pivot = a[right];
while (true) {
/*
* 工作指針i從右向左不斷掃描，找小于或者等于錨點元素的元素
*/
while (i < right && a[i] <= pivot) {
/*
* 找到與錨點元素相等的元素将其交換到p所訓示的位置
*/
if (a[i] == pivot) {
swap(a, i, p);
p++;
}
i++;
}
/*
* 工作指針j從左向右不斷掃描，找大于或者等于錨點元素的元素
*/
while (left <= j && a[j] >= pivot) {
/*
* 找到與錨點元素相等的元素将其交換到q所訓示的位置
*/
if (a[j] == pivot) {
swap(a, j, q);
q--;
}
j--;
}
/*
* 如果兩個工作指針i j相遇則一趟周遊結束
*/
if (i >= j)
break;
/*
* 将左邊大于pivot的元素與右邊小于pivot元素進行交換
*/
swap(a, i, j);
i++;
j--;
}
/*
* 因為工作指針i指向的是目前需要處理元素的下一個元素
* 故而需要退回到目前元素的實際位置，然後将等于pivot元素交換到序列中間
*/
i--;
p--;
while (p >= left) {
swap(a, i, p);
i--;
p--;
}
/*
* 因為工作指針j指向的是目前需要處理元素的上一個元素
* 故而需要退回到目前元素的實際位置，然後将等于pivot元素交換到序列中間
*/
j++;
q++;
while (q <= right) {
swap(a, j, q);
j++;
q++;
}
/*
* 遞歸周遊左右子序列
*/
quickSort(a, left, i);
quickSort(a, j, right);
}
private void quick(int[] a) {
if (a.length > ) {
quickSort(a, , a.length - );
}
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
三路劃分可以避免很多重複元素再次參與遞歸，對于有大量重複元素的待排序列，效率提高了不少。
以上隻是理論上的總結，當然實踐起來代碼也不難寫。在這裡推薦一篇有碼有實驗資料的文章，看後也是更加直覺形象，受益匪淺。
快排的優化其實對于一個計算機科學與技術的入門者來講，是一個不錯的思維上的砥砺，這種類型的東西多多探索，計算機科學“素養”自然慢慢就上去了。