数据结构中快速排序算法的不足以及改进？

Question

如题所述

Answer 1

一般快速排序算法都是以最左元素作为划分的基准值，这样当数据元素本身已经完全有序（不管正序或者逆序）时，每一趟划分只能将一个元素分割出来，其效率很低：时间复杂度O(n^2)，空间复杂度为O(n)
所以改进方法就是找寻合适的基准值，保证不至于在关键字有序或者接近有序时发生这个情况，一般可以使用三者取中（就是待划分序列的头元素、尾元素、中间元素三者的中间值）、或者随机选择等方法，这样即使关键字完全有序，也可以保证时间复杂度O(nlogn)，空间复杂度O(logn)本回答被网友采纳

Answer 2

chiconysun说的很好，做一点小小的补充：

在数据量较大时，递归调用本身的消耗对算法的时间效率也会产生一定影响，采用非递归实现，或者在待排序区间小于某值（有实验数据表明15左右较合适）时，采用其它非递归的排序方法代替快速排序，可以达到更高的时间效率。
相对于关键值的选取，这一优化带来的提升有限（亲测结果，提升10%左右，选择了插入排序做替代）。