排序算法的稳定性
稳定性概念
- 稳定排序：如果两个关键字相等，在排序前后的相对位置不发生变化，那么该排序算法是稳定的。例如，有两个记录R和S，它们的排序关键字相等，假设在排序前R在S的前面，如果使用稳定排序算法，排序后R仍然在S的前面。
- 不稳定排序：如果两个关键字相等，在排序后可能会交换它们的位置，那么该排序算法是不稳定的。例如，排序前R在S前，但排序后S可能在R前。
重要性
- 数据关联性：在有些应用场景中，记录包含多个关键字，并且这些关键字之间存在某种关联。例如，学生信息记录可能包含姓名和成绩，如果先按照姓名排序，再按照成绩排序，稳定性可以保证同成绩的学生按姓名排序的顺序不变。
- 外部排序：在外部排序中，数据量很大，需要分批处理，稳定性可以保证分批处理后的数据合并时不会打乱原有的顺序。
- 多阶段排序：在某些多阶段排序过程中，稳定性可以确保前一阶段排序的结果不会在后续阶段被破坏。
常见排序算法的稳定性
稳定排序算法：冒泡排序、插入排序、归并排序、基数排序。
- 冒泡排序：通过相邻元素的比较和交换来排序，相等的元素不会交换位置，因此是稳定的。
- 插入排序：在插入过程中，相等的元素保持原有顺序，因此是稳定的。
- 归并排序：合并过程中，相等的元素从两个子数组中按顺序取出，因此是稳定的。
- 基数排序：按位比较和分配，相等的元素在分配和收集过程中保持顺序，因此是稳定的。
不稳定排序算法：选择排序、快速排序、堆排序、希尔排序。
- 选择排序：选择最小（或最大）元素进行交换，可能会改变相等元素的相对顺序，因此是不稳定的。
- 快速排序：基准元素的选取和交换可能会改变相等元素的相对顺序，因此是不稳定的。
- 堆排序：堆调整过程可能会改变相等元素的相对顺序，因此是不稳定的。
- 希尔排序：跨多个位置的交换可能会改变相等元素的相对顺序，因此是不稳定的。