为什么叫快速排序
?
这个标题是带有歧义的，每一种排序都有自己的名字，有的是发明者+排序（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的可能，这一效率是远远没法跟快速排序比的！所以快速排序高效的原因就在于利用主元划分这一模型可以很快地确定元素之间的关系。
Hoare分区算法
Hoare分区算法的优点是：首先常数很低（对于本身就已经处于正确区间的元素是不会做多余移动的），并且会把和主元相等的元素均匀地分到两边。
/***************************************************************
函数：随机选取主元的霍尔分区算法
参数：对[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分区算法并没有让主元隔在中间，只是得到两个确定大小关系的区间。 所以在快速排序递归函数中对区间范围的选择会有所区别。
比较次数的期望
这里的比较次数是指整个排序算法运行中，所有扫描区间的动作的次数。即下面cnt的大小的期望：
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)对，所以得到下面的级数：
cnt的实际值应该会比上面的计算结果大，因为Hoare分区算法中选取的主元值也会和自己比较（上面的级数没有考虑这一点），所以还应该加上主元的个数， 这本来也是个概率问题（如果主元为最小值时可能使得区间不变），不过可以很快做出估计：O（n），因为这是一棵二叉树，每个内部节点都会选取一次主元，而内部节点 = 叶子节点 - 1。 所以期望次数最终为：2nln(n) + n 下面是我的测试数据（输入元素互异）：
三数取中的优势
从区间随机选取三个数（可以重复选取同一元素），直观上很快可以知道越是大小接近中间的数越是容易成为主元，也就在很大程度上使得划分更加均匀。
/***************************************************************
函数：三数取中的霍尔分区算法
参数：对[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)：?
如果像算法导论里面那样定义一个“好”的划分为主元排在[n/3, 2n/3]之中，那么通过积分我们可以知道这一概率为13/27（接近一半的概率），比不用三数取中的1/3大出不少。 完全不会分析这种概率分布不