這個標題是帶有歧義的，每一種排序都有自己的名字，有的是發明者+排序（Shell排序），有的是用的步驟名稱+排序（插入排序）... 而快速排序是以它的屬性+排序為名（這不是廢話嗎）。那麼我再換個意義明確的標題：
對大小為n的輸入，其位置關系有n！種可能。排序算法的工作就是在所有n！種可能中找出輸入究竟是哪一種。
而基於比較的排序算法手頭的工具就只有 比較 操作，通過不斷地比較一對對元素來排除不可能的排列（或者說留下可能的排列）。
而比較的結果只能是>和<（不考慮=)這兩種，所以每一次比較操作總有機會使得一半的可能留下來。所以基於比較的排序算法的下界為Ω(lgn!) =Ω(nlgn)。
也許你可能會問那為什麼插入排序在數據本來有序的情況下只需花費O（n）呢。
花費O（n）是沒錯，但這畢竟是決策樹中最短的一支啊，下界是針對最壞情況下至少得做多少次比較。
所以快速排序快的原因就是：其分區過程在很大程度上獲得的信息量很大，可以快速地排除掉不可能的排列可能。
比如拿最好的情況來說——主元為中位數（也就是均勻地把區間分為兩半），那麼得到有n/2個元素比主元小，n/2個元素比主元大。
這樣剩下來的排列可能為：(n/2)！ * (n/2)！ = n！/ 2^(n/2) 種，而這一過程只花費了O（n）。
當於在O（1）的比較下就只剩根號2分之1的可能，也是呈幾何下降。
當然快也是相對而言的：就拿插入排序來講，它為什麼那麼慢，就是因為每一次插入元素所獲得的信息很少，排除的排列可能也很少。
比如對第n/2元素進行插入操作，花費了O(n/2)，剩下來的排列可能為 n！/ (n/2)！ 而插入之前的排列可能為 n！ / (n/2 - 1)！ 種，相當於在O（1）的比較下 只排除了2/n的可能，這一效率是遠遠沒法跟快速排序比的！
/***************************************************************
函數：隨機選取主元的霍爾分區算法
參數：對[low, high)范圍內的數據分區，range為區間的元素個數
***************************************************************/
int* hoarePartition(int* low, int* high, int range)
{
///隨機選取主元
int pivot = ((int)(((double)rand() / RAND_MAX) * range) + low);
low--;
while(true)
{
while(*(++low) < pivot); ///掃描左區間
while(*(--high) > pivot); ///掃描右區間
///當兩邊都掃描到不屬於自己區間的元素時
if(low < high)
{
///當兩區間還沒有交集說明有兩個元素分別落在錯誤的區間，交換即可
int tmp = *low;
*low = *high;
*high = tmp;
}
///當區間相交時，Hoare分區只保證[0....pivot)中的元素 <= [pivot....n)中的元素
///並沒有確定主元的位置，所以只得到兩個確定大小關系的區間，中間沒有主元相隔
else return low;
}
}
這裡特別要注意的是Hoare分區算法並沒有讓主元隔在中間，只是得到兩個確定大小關系的區間。 所以在快速排序遞歸函數中對區間范圍的選擇會有所區別。
int cnt = 0; ///比較次數
int* hoarePartition(int* low, int* high, int range)
{
int pivot = *((int)(((double)rand() / RAND_MAX) * range) + low);
low--;
while(true)
{
while(*(++low) < pivot)
cnt++; ///發生比較
cnt++; ///測試失敗也是一次比較
while(*(--high) > pivot)
cnt++; ///發生比較
cnt++; ///測試失敗也是一次比較
if(low < high)
{
int tmp = *low;
*low = *high;
*high = tmp;
}
else return low;
}
}
/***************************************
函數：快速排序函數
參數：對[low, high)范圍內的數據排序
平均時間復雜度：O(nlgn)
***************************************/
void quickSort(int* low, int* high)
{
int range = high - low; ///區間元素個數
///當區間有不止1個元素時才進行分區
if(range > 1)
{
int* pivot = hoarePartition(low, high, range); ///返回主元地址
quickSort(low, pivot); ///對左區間進行快速排序
quickSort(pivot, high);
}
}
/***********************************
函數：測試比較次數
***********************************/
void testQuickSort(int* a, int n)
{
cnt = 0; ///初始化次數
quickSort(a, a + n);
cout << endl << cnt << endl;
}
這裡得到的期望的常數和算法導論上是不一樣的，因為這是針對Hoare分區的期望分析，不過分析方法和算法導論是一樣的。 首先得假設下返回的主元就是用來劃分的主元。不然太難分析。 這裡用算法導論上面的推導方法：任意一對相距gap的元素（i，j），在排序過程中會比較k次的概率為1 / (gap + 1)^(k - 1) * 2 / (gap + 1)， 而相距gap遠的元素對有(n - gap)對，所以得到下面的級數： 
/***************************************************************
函數：三數取中的霍爾分區算法
參數：對[low, high)范圍內的數據分區，range為區間的元素個數
***************************************************************/
int* hoarePartition(int* low, int* high, int range)
{
///三數取中
int a = *((int)(((double)rand() / RAND_MAX) * range) + low);
int b = *((int)(((double)rand() / RAND_MAX) * range) + low);
int c = *((int)(((double)rand() / RAND_MAX) * range) + low);
int pivot = a > b ? (b > c ? b : (a > c ? c : a)) : (a > c ? a : (b > c ? c : b));
low--;
while(true)
{
while(*(++low) < pivot); ///掃描左區間
while(*(--high) > pivot); ///掃描右區間
///當兩邊都掃描到不屬於自己區間的元素時
if(low < high)
{
///當兩區間還沒有交集說明有兩個元素分別落在錯誤的區間，交換即可
int tmp = *low;
*low = *high;
*high = tmp;
}
///當區間相交時，Hoare分區只保證[0....pivot)中的元素 <= [pivot....n)中的元素
///並沒有確定主元的位置，所以只得到兩個確定大小關系的區間，中間沒有主元相隔
else return low;
}
}
下面是具體的概率分布： 因為第k大的元素被選為主元的概率為(6(k - 1)(n - k) + 3n - 2) / n^3，對n取極限無窮得到概率分布函數 y = 6x(1 - x)：
/***************************************
函數：尾遞歸優化版快速排序
功能：對[low, high)范圍內的數據排序
期望運行時間：O(2nlgn)
***************************************/
void quickSortRoutine(int* low, int* high)
{
int range; ///區間元素個數
///當區間有不止1個元素時才進行分區
while((range = high - low) > 1) ///改為循環語句這樣父節點就可以在下一次運算中充當孩子節點
{
int* pivot = hoarePartition(low, high, range); ///返回主元地址
quickSortRoutine(low, pivot); ///對左區間進行快速排序
low = pivot; ///注意區間范圍
}
}
可以通過選擇替代“較大”的孩子遞歸使得遞歸樹的深度控制在lgn之內，不過快速排序本來就是靠概率吃飯的，這樣會增加比較開銷，我就不寫了。 這裡還有一點點優化的空間，那就是維護一個保存區間信息的數組，裡面保存的數據為待分區的區間，這樣就完全不用遞歸了。不過會額外增加空間上的消耗。
#define FACTOR 37 ///葉子的寬度
/***************************************************************
函數：三數取中的霍爾分區算法
參數：對[low, high)范圍內的數據分區，range為區間的元素個數
***************************************************************/
int* hoarePartition(int* low, int* high, int range)
{
///三數取中
int a = *((int)(((double)rand() / RAND_MAX) * range) + low);
int b = *((int)(((double)rand() / RAND_MAX) * range) + low);
int c = *((int)(((double)rand() / RAND_MAX) * range) + low);
int pivot = a > b ? (b > c ? b : (a > c ? c : a)) : (a > c ? a : (b > c ? c : b));
low--;
while(true)
{
while(*(++low) < pivot); ///掃描左區間
while(*(--high) > pivot); ///掃描右區間
///當兩邊都掃描到不屬於自己區間的元素時
if(low < high)
{
///當兩區間還沒有交集說明有兩個元素分別落在錯誤的區間，交換即可
int tmp = *low;
*low = *high;
*high = tmp;
}
///當區間相交時，Hoare分區只保證[0....pivot)中的元素 <= [pivot....n)中的元素
///並沒有確定主元的位置，所以只得到兩個確定大小關系的區間，中間沒有主元相隔
else return low;
}
}
/***************************************
函數：尾遞歸優化版快速排序
功能：對[low, high)范圍內的數據排序
期望運行時間：O(nlgn)
***************************************/
void quickSortRoutine(int* low, int* high)
{
int range; ///區間元素個數
///當區間有不止1個元素時才進行分區
while((range = high - low) > FACTOR) ///改為循環語句這樣父節點就可以在下一次運算中充當孩子節點
{
int* pivot = hoarePartition(low, high, range); ///返回主元地址
quickSortRoutine(low, pivot); ///對左區間進行快速排序
low = pivot; ///注意區間范圍
}
}
/********************************************************************
函數：優化一點點的插入排序
功能：對[low, high)內的數據進行排序
********************************************************************/
void improvedInsertionSort(int* low, int* high)
{
///因為最小值在第一位，所以直接從第三個元素開始插入
++low;
while(++low < high)
{
int tmp = *low; ///把待插入元素保存到臨時變量中
int* destPos = low; ///計算插入位子
///把第一次測試單獨提出來
if(*(--destPos) > tmp)
{
do
{
*(destPos + 1) = *destPos;
}while(*(--destPos) > tmp); ///測試上一個是否是目標位置
*(destPos + 1) = tmp; ///最後一次測試失敗使得destPos比實際小1
}
}
}
/**********************************
函數：完整版快速排序
**********************************/
void quickSort(int* low, int* high)
{
///設置隨機數種子
srand(time(nullptr));
///進行快速排序，葉子寬度為FACTOR
quickSortRoutine(low, high);
///找出最小值放到最開始作為插入排序的哨兵節點
int* minPos = low; ///最小值的位置
int* lastPos = low + FACTOR;
for(int* i = low + 1; i < lastPos; i++)
if(*i < *minPos) minPos = i;
int tmp = *low;
*low = *minPos;
*minPos = tmp;
///最後進行插入排序
improvedInsertionSort(low, high);
}
那麼葉子的寬度該如何去選擇呢。一般來說是8到20都不錯，不過這裡用了三數取中所以常數比普通隨機選取主元的快速排序大，所以這裡是個兩位數就可以了。 上面那個37也是我主觀選的，就像生活大爆炸裡sheldon說：73是最美妙的數字，因為73是第21個素數，反過來37正好又是第12個素數，並且21正好又等於7和3的積， 另外把73轉換為二進制後可以得到1001001，正讀倒讀都一樣。感覺這樣一寫就很高端啊。
