前面J桑讲了快排的思想（感兴趣的朋友可以去看看~）
戳我戳我戳我~~~
今天我们来讲快排的优化。
快速排序性能的关键点分析
决定快排性能的关键点是每次单趟排序后，key 对数组的分割。如果每次选 key 基本二分居中，那么快排的递归树就是一棵均匀的满二叉树，性能最佳。然而，实践中虽然不可能每次都是二分居中，但性能依然可控。
但如果出现每次选到最小值或最大值，划分为 0 个和 N-1 的子问题时，时间复杂度为 O(N²)。在数组序列有序时，就会出现这样的问题。
仍需解决的场景
-
数组中有多个与 key 相等的值：
- 例如：
- 例如：
-
数组中全是相同的值：
- 例如：
这些场景会影响快排的性能，可能导致最坏情况的出现。
在快速排序中，基准元素的选择至关重要。相比将最左边元素作为基准，随机选择基准有几个明显优势：
-
避免最坏情况：
- 如果数组有序或近乎有序，选择最左边元素作为基准会导致每次分割的子数组大小不均匀，造成递归深度达到最大，从而使时间复杂度退化到 O(n²)。
-
提升分割效果：
- 随机选择的基准元素更有可能让数组均匀分割，这样递归深度会更小，效率更高。
-
更强的适应性：
- 在处理重复元素较多的情况下，最左边的基准可能导致很多冗余操作。随机选择可以更灵活地处理这些情况，减少不必要的比较。
总的来说，使用随机数作为基准选择能让快速排序在各种情况下更稳定、更高效。
它的实现是：（随机选到key与最左边元素交换，还是让key = 最左边元素）
三值取中与随机选择基准
概念
-
三值取中：
- 三值取中是一种优化快速排序基准选择的方法。它通过选取数组中的第一个元素、最后一个元素和中间元素，计算这三个数的中位数作为基准。这种方法能够有效减少极端情况的发生，从而提高排序性能。
-
随机选择基准：
- 随机选择基准是另一种优化策略，它通过在数组中随机选取一个元素作为基准。这样可以打破数组的有序性规律，降低最坏情况的概率，保持良好的平均时间复杂度。
总结
三值取中和随机选择基准各有优劣。三值取中通过选择中位数能够提高稳定性，特别是在处理特定情况时表现出色；而随机选择基准则在实现上更为灵活，适合于更广泛的数据集。在实际应用中，可以根据数据特征和具体需求选择合适的方法，以获得最佳的快速排序效果。
三值取中的代码实现是：
前面两个方式是解决如何找key的问题，三路划分主要是用于处理有大量与Key值相同的元素时的情况。
为什么要用三路划分？
三路划分的基本思想
三路划分的核心思想可以简单地总结为将数组分为三段：
- 小于基准值（key）的部分
- 等于基准值（key）的部分
- 大于基准值（key）的部分
这种划分方法结合了两种常见的划分策略：Hoare 的左右指针法和 Lomuto 的前后指针法。通过使用三个指针来管理这三个区域，使得算法在处理重复元素时能够高效进行。
算法步骤
-
选择基准：
- 默认情况下，选择最左边的元素作为基准（key）。
-
初始化指针：
- 指针指向数组的开始位置。
- 指针指向数组的结束位置。
- 指针从 开始，遍历整个数组。
-
遍历和划分：
-
当 指针遇到：
- 小于基准值的元素：与 指针指向的元素交换，同时 和 都向右移动一位。
- 大于基准值的元素：与 指针指向的元素交换，并将 向左移动一位（此时， 不动，因为交换后，当前指向的元素还需要判断）。
- 等于基准值的元素：直接移动 向右。
-
继续这个过程，直到 超过 。
-
-
三路划分算法通过将数组分为小于、等于和大于基准的三部分，有效地解决了快速排序在处理重复元素时的性能问题。它的核心在于利用三个指针来高效管理这三部分，从而提高了算法的效率和稳定性。在面对大量相同元素时，三路划分算法可以显著减少不必要的比较和交换操作，使得排序过程更加高效。
三路划分具体实现代码是：
综合上述三值取中及三路划分，我们就得到了一个近乎完美的排序方法，它可以解决99%排序问题~
这里给大家一个测试代码，大家下去可以测试快排的效率
introsort的快排，introsort是introspective sort采⽤了缩写，他的名字其实表达了他的实现思路，他的思路就是进行自我侦测和反省，快排递归深度太深（sgi stl中使⽤的是深度为2倍排序元素数量的对数值）那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进⾏快排分割递归了，改换为堆排序进⾏排序。
自省排序说白了就是数据小时用直接插入排序，数据多时用快排，深度大时改为堆排序，将我们前面学到的排序都结合起来了，我们直接来看代码~
到这里我们快排的优化就讲完了，当然往后还有其他的优秀排序，但是我们这里的快排已经能打败90%的排序了，是一个近乎完美的排序，大家要和J桑一起多看多练哦~