请问简化版Dijkstra三路划分排序算法的时间复杂度是多少？

先从这个算法的核心逻辑说起：Dijkstra三路划分的本质是一次线性遍历就把区间[left, right]的元素分成三个部分——小于基准、等于基准、大于基准，每一个元素只会被处理一次，不会重复扫描。基于这个核心，我们分三种情况来拆解时间复杂度：

1. 最好情况：O(n) #

当处理的区间里所有元素都和基准值相等时，遍历一遍就能把整个区间标记为「等于基准」的部分，不需要递归处理左右子区间。这时候整个算法的时间复杂度就是线性的O(n)，n是当前处理的元素总数。
这种场景下，三路划分的优势比普通快排大太多——普通快排遇到全重复元素会直接退化到O(n²)，而三路划分能完美处理。

2. 最坏情况：O(n²) #

如果每次选择的基准都是当前区间的最小值或最大值（比如你的代码里固定选list.get(left)，如果数组本身是有序/逆序的，就会触发这种情况），而且区间里几乎没有重复元素，这时候三路划分就退化成了普通的单路快排：每次划分只能把基准放到正确的位置，左右子区间的大小分别是n-1和0，递归深度会达到O(n)，每层处理O(n)的元素，最终时间复杂度就是O(n²)。

3. 平均情况：O(n log n) #

在大多数随机分布的场景下，基准值能把区间分成大小相对均衡的左右子区间（哪怕有部分重复元素）。每次划分的线性遍历是O(n)，递归深度是O(log n)——因为每次划分都会把问题规模缩小至少一部分（中间的等于基准的元素不需要再递归处理）。所以平均时间复杂度是O(n log n)，而且因为减少了重复元素的递归处理，实际运行效率会比普通快排更高。

另外补充一点：你的代码里固定选左端点作为基准，这会让有序数组的情况直接触发最坏复杂度。如果想优化，可以改成随机选基准或者三数取中选基准，能大幅降低最坏情况出现的概率。

内容的提问来源于stack exchange，提问作者A is for Ambition