算法-排序-快速排序的优化

我们知道快速排序在最坏情况下的时间复杂度是O(n^2)，那有没有办法优化它呢？

最坏情况的影响因素

我们知道，快速排序的时间复杂度其实和分区点的位置有关的，如果每次分区点都在中间位置，那这个时候的时间复杂度是最低的，如果每次分区点都在两端，则时间复杂度是最坏的。

如何尽量避免最坏的情况出现呢

避免最坏情况的出现的主要方法就是让分区点两边尽量均匀。那如何让分区点两边尽量均匀呢？常见的有两种方法

1. 随机法
   随机法很简单，就是每次从待排序区间中随机挑选一个作为分区点。可能这个分区点不是最佳的分区点，但是从概率角度讲，它也不大可能是最坏的分区点，平均下来也就可以尽可能的避免最坏的情况出现
2. 取中法
   取中法也很简单，就是取一定的数据进行对比，选出中间值，然后以其作为区分点，比较常见的有三数取中、五数取中等