插入排序中未交换元素后：继续比较还是处理下一元素？

问题场景：
待排序列表初始为[20.51, 18.59, 19.21, 17.33, 19.88, 20.09]，按插入排序逻辑推进到处理item[4]（值为19.88）阶段。此时当前列表为[17.33, 18.89, 19.21, 20.51, 19.88, 20.09]；先交换19.88和20.51得到[17.33, 18.89, 19.21, 19.88, 20.51, 20.09]，接着比较19.88与前一个元素19.21，发现无需交换。

结论 #

可以停止对19.88的比较，直接开始处理item[5]。

核心逻辑依据 #

插入排序的本质是维护一个已排序的前缀子序列，对于当前待插入元素，我们只需要从已排序子序列的末尾向前遍历：

1. 一旦找到第一个小于等于当前元素的位置，就说明当前元素已经处于正确的排序位置
2. 因为已排序子序列是升序的，前面的所有元素必然都小于等于这个"第一个符合条件的元素"，自然也小于当前元素，完全没必要继续往前比较

在这个场景里：

• 已排序前缀是[17.33, 18.89, 19.21]（交换后19.88的前三个元素）
• 19.88 > 19.21，说明前面的18.89、17.33肯定都比19.88小，所以19.88的位置已经正确，无需再比较。

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