在快速排序过程中，通常取待排序序列中的第1个记录的关键字作为枢轴

Question

在快速排序过程中，通常取待排序序列中的第1个记录的关键字作为枢轴，以它为“分界线”重排其余记录。试讨论当初始记录序列按关键字有序或基本有序时该算法的执行时间效率，写出算法的时间复杂度，如果要改进，应如何选取枢轴记录？

Answer 1

有序或者基本有序时，每次划分只能完成1个（左右），时间复杂度为O(n^2)
如果要改进，选择枢轴可以使用方法：
方法1、三者取中：序列第一个、中间位置、最后位置三个值的中间值
方法2、随机选取：不再是第一个记录，而是在序列中随机选取