参考https://juejin.cn/post/6844904130813640711

快排优化小结

对快速排序的优化主要体现在基准值选取、数据集分割、递归子序列选取、其他排序算法混合等方面，换句话说就是让每次的分区尽量均匀且没有重复被处理的元素，这样才能保证每次递归都是高效简洁的。

影响快排性能的情况：

分区不均匀

  • 所选的基准值是序列的首元素且是序列中的最大值或最小值，导致其他元素都在基准值的一侧，另一侧没有；这种情况下每次划分子区间后只有一个指针在动，复杂度为O(n2)

  • 对于已经排序或者近乎有序的数据集合来说就可能出现这种极端情况。

  • 解决方法：保证每次分割子序列的时候都足够均匀，比如随机选取基准值，而不是每次都选取第一个或者最后一个

数据中有大量重复元素

  • 解决方法：三分区快排，小于区、等于区、大于区，每次从头到尾遍历一遍，维护小于区和大于区的边界，递归的时候递归小于区和大于区，中间的等于区不变

在实际过程中根据处理值与基准值的大小关系，进行相应分区合并和交换，再进行下标移动就可以了，实际中分三种情况，这也是写代码的依据：

  • 处理值e==p，将e合并到等于区，i++；
  • 处理值e<p，将e与(lt+1)位置的数据交换，扩展小于区lt++，等于区长度不变，相当于整体平移；
  • 处理值e>p，将e与(gt-1)位置的数据交换，扩展大于区gt--，此时i不变，交换后的值是之前待处理区的尾部数据；
    请在这里输入引用内容