双向选择排序中是否需校验最值合理性？为何保留left==max判断？

这个语句绝对不能删除，它是保证双向选择排序逻辑正确的关键，和重复元素无关，核心是处理「最大值初始位置恰好等于当前left」的场景，具体原因如下：

问题场景示例 #

拿数组 [4, 1, 2, 3] 来测试：

1. 初始left=0，right=3，遍历后找到min=1（对应值1），max=0（对应值4）。
2. 执行swap(array, left, min)，交换索引0和1，数组变为[1, 4, 2, 3]。
3. 如果没有if (left == max)语句，接下来会执行swap(array, right, max)——也就是交换索引3和0，数组变成[3, 4, 2, 1]，明显排序错误：最大值4没有被放到当前区间的最右端，反而把最小值1换到了末尾。
4. 有了if (left == max)语句时，因为left==max（0==0），会把max更新为min（也就是1），接下来执行swap(array, right, max)，交换索引3和1，数组变为[1, 3, 2, 4]，最大值被正确放到右端，后续排序逻辑正常。

原理说明 #

双向选择排序的核心步骤是：

• 先把当前区间的最小值交换到left位置
• 再把当前区间的最大值交换到right位置

但如果最大值一开始就在left位置，第一次交换（left和min）会把原来的最大值从left移到min的位置。这时候如果不更新max的索引，后续交换最大值到right时，会错误地去操作原来的left位置（现在已经是最小值了），导致最大值丢失在区间中间，破坏排序逻辑。

你之前测试的[3,3,3,3]、[3,3,3,4]都是不会触发这个问题的场景，但存在大量类似[4,1,2,3]的场景，必须依赖这个语句修正索引才能保证排序正确。

内容的提问来源于stack exchange，提问作者LikeDreamwalker