快速排序的复杂度是$O(n\cdot \log n)$，一般来说比归并、堆排序要快。然而快排本身最坏情况下退化为冒泡排序，不够稳定。
这种“最坏情况”源于轴点（pivot）的选取:考虑完全有序的序列{0, 1, 2, ….. n}, 如果选择最左侧的元素为轴点，每一次算法过程都会将区间分为长度为1和长度为n-1的子序列，因而复杂度是$O(n^2)$;而对于完全反序的序列{n, n-1, n-2, ….. 1, 0},如果选择最右侧的元素为轴点，区间的划分情况同样最坏。
一般情况下，对应于一组可能的输入，如果轴点选取为每一次都划分出长度为1的子序列的元素，将达到最坏情况。
一种常见的策略是随机选取轴点。鉴于大部分快排选择最左侧元素为轴点，在不破坏现有实现的基础上，在递归开始后首先随机选择一个元素和最左侧元素交换，其余过程不变，这样就等效为随机选了一个元素作为轴点。这种方法的期望比较次数是1.386nlogn。
第二种方法是选择待排序序列的最左、最右和中间三个元素中的中位数作为轴点。期望比较次数降为1.188nlogn，代价是3%左右的交换次数。这一步骤可以反复进行，比如，可以先将区间分为三段，每一段使用上述方法选取一个轴点，然后再比较这三个点，取其中位数，称之为ninther。
第二种方法的原理可以大致理解为，从首尾和中部选择三个元素的中位数，可以充分接近于原序列的中位数。我们知道，如果每一次轴点都在线性时间选择为中位数，那么快排是稳定的O(nlogn)算法。因此这种方法可以降低最坏情况发生的概率（输入序列随机的情况），且多次重复这个过程，可以进一步优化。
如果我们能在线性时间里找到原序列的中位数就好了！这就是一个$\frac{n}{2}$-选取问题。现有快排的普遍策略即quickselect，而采用五取样划分，可以在线性时间内找到一个序列第k大的数。
关于五取样划分，也就是linearselect的问题，这里不再赘述。因为这种优化方法在实际中几乎没有应用（常数过大，只有数据集极大时有效，在这种情况下，introsort更好）
