排序算法稳定性
内容提要
排序稳定性指排序后相等元素的相对位置保持不变。稳定排序算法包括冒泡、插入、归并和基数排序；不稳定算法包括快速、堆、希尔和选择排序。选择排序和快速排序因交换操作破坏稳定性，归并排序在合并时优先取左侧元素而保持稳定，并附有Java代码验证。
延伸解读
稳定性在工程中的实际价值
文章指出，稳定性的好处在于：先按一个键排序，再按另一个键排序时，第一次排序的结果可以为第二次所用。这意味着在多条件排序场景中，若采用稳定排序，只需从次要键到主要键依次排序即可得到正确结果，无需额外处理。这一特性在数据库排序、表格多列排序等场景中非常实用，能简化实现逻辑并减少出错可能。
不稳定排序的破坏机制对比
文章通过具体例子说明不稳定排序如何破坏稳定性。选择排序在交换最小元素时，可能将靠后的相等元素换到前面，如序列5 8 5 2 9中第一个5与2交换，导致两个5的相对顺序改变。快速排序则在中枢元素与a[j]交换时打乱稳定性。堆排序在调整父节点时，可能交换后面的元素而遗漏前面的相等元素，从而破坏稳定性。这些机制表明，不稳定往往源于跨距离的交换操作。
归并排序为何能保持稳定
归并排序在合并两个有序短序列时，如果当前元素相等，会优先取左侧序列的元素放入结果序列。这一策略保证了相等元素的原始相对顺序不变，因此归并排序是稳定的。文章还提供了Java代码验证，通过插入排序和选择排序的对比，直观展示了稳定与不稳定的差异。这种稳定性使归并排序适合对稳定性有要求的场景。
基数排序的稳定性与适用条件
基数排序按低位先排序、收集，再按高位排序、收集，依次直到最高位。由于每一轮排序都是稳定的，最终次序能保证高优先级高的在前，高优先级相同的低优先级高的在前。文章指出基数排序用于整数，需要较多存储空间，且基于分别排序、分别收集。因此，它适合整数且对稳定性有要求的排序任务，但需考虑空间开销。
Q&A
什么是排序算法的稳定性？
排序算法的稳定性是指排序前后两个相等的数相对位置不变。也就是说，如果原序列中两个元素相等，排序后它们的先后顺序保持不变，则该排序算法是稳定的。
哪些排序算法是稳定的？
稳定的排序算法包括：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序。
为什么快速排序是不稳定的？
快速排序在分区过程中，中枢元素与a[j]交换时，可能把前面元素的稳定性打乱。例如序列5 3 3 4 3 8 9 10 11，中枢元素5和3交换就会破坏元素3的稳定性。
归并排序为什么是稳定的？
归并排序在合并两个有序序列时，如果两个当前元素相等，会优先取前面序列的元素放在结果序列的前面，从而保证相等元素的相对顺序不变。
选择排序为什么不稳定？
选择排序每趟选择最小元素并与当前位置交换，可能把相等元素中靠前的元素交换到后面，破坏相对顺序。例如序列5 8 5 2 9，第一遍选择时第一个5会和2交换，导致两个5的相对顺序改变。
排序稳定性有什么实际好处？
稳定性允许先按一个键排序，再按另一个键排序，第一次排序的结果可以为第二次排序所用，从而保持多次排序的累积效果。
