原创文章，转载请注明出处。
本文是排序算法系列文章的第五篇，主要讲述 “快速排序” 算法。
一、原理：
快速排序的基本思想是任取待排序序列中的某个数据元素（通常选择序列的第一个数据元素）作为基准，按照该基准的关键字大小，将整个序列划分为左右两个子序列。其中左侧子序列中所有的数据元素都小于或等于基准元素，右侧子序列中所有数据元素都大于基准元素，基准元素则排在这两个子序列中间，这也是该元素最终应当安放的位置。然后分别对这两个子序列递归执行上述快速排序算法，直到所有数据元素都排在相应位置上（即有序）为止。
一趟排序的过程为：取序列第一个元素为基准元素 key，指针 low 指向序列第一个元素下标，指针 high 指向序列最后一个元素下标。从 high 指向的元素开始，向前遍历（每向前一次 high 指针要减 1，表明某数已遍历过，且该数大于 key，放在右侧是正确的），直至找到第一个小于基准 key 的元素，将其放到 low 指向的位置，并且 low 指针加上 1。然后从 low 指向的元素开始向后遍历（每向后一次 low 指针要加 1，表明某数已遍历过，且该数小于 key，放在左侧是正确的），直至找到第一个大于基准 key 的元素，将其放到 high 指向的位置，并且 high 指针减去 1。重复上述的 high、low 交替过程，直至 low == high，将基准元素放在 low（high）指向的位置，这样便完成了一趟快速排序过程。
二、代码及注释：
int switch_QSort(int *arr, int low, int high)
{
int i, j;
int key = arr[low]; //基准（关键字）初始化默认为序列的第一个元素
while (low < high)
{
for (i = high; low < high && i >= low; i--) //从序列的最右（high）开始，往前找到第一个小于基准的元素
{
if (arr[i] <= key) //找到小于基准的元素，应该放到基准位置的左侧
{
arr[low] = arr[i]; //将该元素放在未分序列的第一个位置（low）
low++; //指向下一个low位置
break; //找到一个后跳出循环，因为high跟low的查找是交替进行的
}
else //若每次往前未找到小于基准的元素
{
high--; //说明该对应位置本就应该在基准位置右侧，因而需指向下一个high位置
}
}
for (i = low; low < high && i <= high; i++) //从序列的最左（low）开始，往后找到第一个大于基准的元素
{
if (arr[i] >= key) //找到大于基准的元素，应该放到基准位置的右侧
{
arr[high] = arr[i]; //将该元素放在未分序列的最后一个位置（high）
high--; //指向下一个high位置
break; //找到一个后跳出循环，因为high跟low的查找是交替进行的
}
else //若每次往后未找到大于基准的元素
{
low++; //说明该对应位置本就应该在基准位置左侧，因而需指向下一个low位置
}
}
}
arr[low] = key; //左右序列分完后，也即循环结束后，low==high，基准位置找到了，将基准元素放到该位置
return low; //返回一次排序后的基准位置，为下一次左右序列的划分做准备
}
void quickSort(int *arr, int low, int high)
{
//指针low指向序列的第一个位置，指针high指向序列的最后一个位置
if (low < high) //当low != high时
{
int key = switch_QSort(arr, low, high); //基准（关键字）的最终位置，也即一次排序后low==high时的位置，将序列分为左右两个子序列
quickSort(arr, low, key - 1); //左序列递归调用快速排序
quickSort(arr, key + 1, high); //右序列递归调用快速排序
}
}
三、算法性能分析：
当输入规模为 n = 10000、20000、30000、40000、50000 时，执行程序，可以得到在不同输入规模下，20 组随机样本数据执行快速排序的单组执行时间及平均执行时间为：
理论上来说，快速排序的时间复杂度同归并排序一样，均为 O(nlogn)。同时，由上图可以看出，当 n = 10000 时，20 组样本排序的平均执行为 0.702315 ms。以输入规模为 10000 的数据运行时间为基准点，则设理论上的平均执行时间为：t = O(nlogn)，当 n 扩大两倍时，t’ = O(2nlog2n) =O(2n(logn + log2)) = O(2nlogn + 2nlog2) ≈ O(2nlogn)；同理 n 扩大 3 倍、4 倍、5 倍时，t’ ≈ O(3nlogn)、O(4nlogn)、O(5nlogn)，相应地，实测耗时为：t’ = 2t、3t、4t、5t，代入t = 0.702315 ms，可以计算出快速排序的理论耗时及实测耗时。
所以，在相应输入规模下，快速排序的理论执行时间为：
根据上表，可以作出快速排序理论效率曲线和实测效率曲线如下：
如上图表，是快速排序的理论效率曲线和实测效率曲线，其中位于上方的数据标签是实测效率曲线的标注，位于下方的数据标签是理论效率曲线的标注。由图表我们可以看出，在同一问题规模下，理论消耗时间和实际消耗时间相近，两条曲线基本重叠。
在快速排序过程中，通过一趟排序，先确定一个元素为基准元素（通常取序列的第一个元素），将要排序的数据分割成独立的左右两个子序列，其中左侧子序列的所有数据都比基准元素要小或相等，右侧子序列的所有数据都比基准元素要大，也就是说基准元素排在这两个子序列中间。而后再按此步骤对左右两个子序列分别进行快速排序，上述步骤通过递归实现，如此下去，直至序列完全有序。
在最坏情况下，待排序列已经正序排序，则快速排列的递归树成为单支树，每次划分只能得到一个比上一次少一个记录的子序列，必须经过 (n - 1) 趟才能把所有记录定位，而且第 i 趟需要经过 (n - i) 次关键字比较才能找到第 i 个记录的安放位置，总的关键字的比较次数达到 (n2/2)，时间复杂度达 O(n2)，但是这种情况在随机化生成序列中出现的概率近乎为 0。
对于快速排序来说，最好的情况是每次划分都可以得到元素相等的两个子序列，这样递归树左右子树的高度相等，为 logn，而在每一层上的记录定位操作所需时间为 O(n)，时间复杂度为 O(nlogn)。
通常情况下，随机化生成的序列进行快排是可以生成近乎平衡的递归树的，因此，总的时间复杂度为 O(nlogn)，其曲线应当近乎符合线性关系，从上面的折线图也可以比较直观地看出，不管是理论效率曲线还是实测效率曲线，都基本符合线性关系。在相同的输入规模下，理论消耗时间与实际消耗时间十分相近，二者吻合得很好，只有细微差距，原因可能是随机生成序列数据的偶然性造成的，也可能跟程序运行时电脑的状态有一定关系。