代码

时间复杂度 O(nlogn)

最坏时间复杂度 O(N^2)

加一行什么代码能避免?

在 partition 逻辑开始前，加一个随机打乱或者随机选基准的操作

更适合自己体质的代码……

之前大一备战ACM竞赛的时候背过快排的模版 觉得很好记 还是统一用这个吧

Hoare 分区法 + 中点基准

最好记的写法是取中间元素作为基准，i 和 j 从两头向中间走，逻辑完全镜像

不用特意去处理 Pivot 的交换，也不用纠结最后 Pivot 落在哪

这个代码还消除了因“重复元素”导致的O(N^2)

但是还是不能解决人为构造的对抗数据

要想几乎解决最坏时间复杂度O(N^2) 还是要随机选一个数作为pivot最好

const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
const pivot = nums[randomIndex];

当然运气不好没办法……(当然概率极低) 遇到没招(笑哭……)