顾名思义，快速排序是实践中已知最快的排序算法，平均运行时间为 O(NlogN)，最坏情况运行时间为 O(N^2)。 算法的基本思想很简单，但是要编写一个高效的快速排序算法却没有那么简单。 基准的选择、要素的细分等都至关重要。 如果你不知道如何优化快速排序算法，你不应该错过这篇文章。
算法思维
快速排序使用分而治之的策略。 分而治之的基本思想就是将原问题划分为多个与原问题相似的子问题，解决这些子问题，并将子问题的解合并到原问题的解中。
那么如何利用分而治之的思想来对数据进行排序呢？ 假设有一组元素A：
可见算法思路比较简单，但是实际如何处理上述步骤呢？
如何选择基准
事实上，无论你如何选择基准，都不会影响排序结果，但不同的选择可能会影响整体的排序时间，因为基准的不同选择会导致两个划分集的大小不同。 如果分割之后，两个集合的大小几乎相等的话，那么我们整体分割的次数显然会减少，所以整体花费的时间也会相应减少。 让我们看一下替代策略。
选择第一个或最后一个
如果要排序的数字是随机的，那么选择第一个或最后一个作为基准是没有问题的。 这也是我们看到的最常见的选择。 但如果要排序的数据已经排序了，就会出现非常糟糕的分割。 几乎所有数据都被分成一个集合，而另一集合中没有数据。 这样的话，花费了时间，却没有做多少实际工作。 最坏情况下其时间复杂度为O(N^2)。 因此，绝对不推荐这种策略。
随机选择
随机选择基准是一种更安全的方法。 因为它并不总是产生较差的分割。
C语言实现参考：
ElementType randomPivot(ElementType A[],int start,int end)
{
srand(time(NULL))
int randIndex = rand()%(end -start)+start;
return A[randIndex];
}
选择三个数字的中位数
从前面的描述中我们知道，最好能够选择数据的中值，因为它几乎可以将集合分成相等的两部分。 但很多时候计算中值是很困难的，而且需要时间来计算。 因此，我们随机选择三个元素，并使用它们的中位数作为整个数据中位数的估计。 这里，我们选择最左、最右、中间位置三个元素的中位数作为基准。
如果您有以下数组：
1 9 10 3 8 7 6 2 4
左边元素为1，位置为0，右边元素为4，位置为8，那么中间位置为[0+8]/2=4，中间元素为8，那么三者的中位数数字为 4（1、4 和 8 的中位数）。
如何将元素移动到底座的两侧
选择底座后，如何将元素移动到底座两侧？ 通常的做法如下：
当我们使用三数均值法来选择基准时，由于基准是中值，所以实际上只需要保证左端、右端、中间值从小到大即可。 以前面提到的数组为例，我们找到这三个之后，我们将它们排序如下：
排序前
排序后
如果是这样的话，那么其实不需要将base元素与最后一个元素交换，而只需与倒数第二个元素交换即可，因为最后一个元素肯定比base元素大，这样可以减少交换次数。
如果前面的描述还不清楚，我们来看看实践中一个完整的流程是什么样子的。
第一步，以中间值为基准，对左端、右端和中间值进行排序：
第二步是将中值与倒数第二个数交换：
第三步，i向右移动，直到找到大于等于基线9的元素：
第四步，j向左移动，直到找到小于等于基线的元素2：
步骤5，交换i和j：
步骤6：重复上述步骤，将i向右移动，j向左移动：
第7步，交换i和j指向的值：
步骤8：重复上述步骤，i向右移动，j向左移动。 这时候i和j已经交错了：
第九步，i和j已经交错，所以最终将基元素与i指向的元素交换：
如何对子集进行排序 当我们走到这一步时，我们发现i的左边是小于i指向的元素，右边是所有大于i的元素。 最后，对子集执行相同的操作。
递归法
最常见的一种是递归方法。 递归的优点是代码简洁、易于理解，但不可忽视的是，当递归嵌套太深时，其效率问题和堆栈溢出的风险可能会迫使你选择非递归方法。 将整个集合一分为二后，递归调用剩下的两个集合，直到排序完成。 简单说明如下（不可运行代码）：
void Qsort(int A[],int left,int right)
{
/*分区操作*/
int i = partition(A,left,right);
/*对子集递归调用*/
Qsort(A,left,i-1);
Qsort(A,i+1,right);
}
递归时最需要注意的是递归结束调用，否则会出现无限递归，导致堆栈溢出。
