排序的‘公平性’：稳定性是什么？以插入排序为例

排序的“稳定性”指排序后相等元素的相对顺序是否保持不变，保持则为稳定排序。插入排序通过独特的插入逻辑实现稳定性。 插入排序核心是将无序元素逐个插入有序部分。当插入相等元素时，不交换，直接插在相等元素之后。例如数组[3,1,3,2]，处理第二个3时，因与有序部分末尾的3相等，直接插入其后方，最终排序结果[1,2,3,3]，原两个3的相对顺序未变。 稳定性的关键在于保留相等元素的原始顺序。这在实际场景中至关重要，如成绩排名、订单处理等需按原始顺序公平排序的情况。插入排序因“相等不交换，后插”的逻辑，天然保证了稳定性，让重复元素始终按原始顺序排列，体现“公平性”。