排序算法的稳定性及其汇总

什么是排序？

排序是将一组无序的数据按照一定规律顺次排列起来，即将无序序列排成一个有序序列（由小到大或由大到小）的操作。

排序方法的分类

按数据存储介质分类：

内部排序：数据量不大，数据在内存中进行，无需内外存交换数据。

外部排序：数据量较大，数据在外存（文件排序）中进行，排序过程相对复杂。

按比较器个数分类：

串行排序：单处理机，同一时刻只比较一对元素。

并行排序：多处理机，同一时刻比较多对元素。

按辅助空间分类：

原地排序：辅助空间用量为O(1)的排序方法。

非原地排序：辅助空间用量超过O(1)的排序方法。

按稳定性分类：

稳定排序：能够保持相同数值元素原有顺序的排序方法。

非稳定排序：不能保持相同数值元素原有顺序的排序方法。

以下是几种常见的排序方法及其特点：

1. 插入排序：基本思想是在有序序列中插入一个元素，保持序列有序，逐步增加有序长度。性能分析表明，元素数据越接近有序，排序速度越快。最坏情况下（输入的数据是逆序的），时间复杂度为O(n^2)。要提高查找速度，需要减少元素的比较和移动次数。折半插入排序平均性能优于直接插入排序，时间复杂度为O(n^2)，空间复杂度为O(1)，是一种稳定的排序方法。

2. 选择排序：基本思想是从待排序记录序列中选出最小（或最大）的元素，存放在序列的起始位置，然后再从剩余未排序元素中继续选择最小（或最大）元素，放到已排序的序列的末尾。时间复杂度为O(n^2)，空间复杂度为O(1)，是稳定排序方法。

3. 快速排序：基本思想是通过一次排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。其时间复杂度受划分元素选取的影响，输入数据越随机，性能越好。时间复杂度在最好、最坏和平均情况下有所不同，空间复杂度为O(logn)。快速排序是一种不稳定的排序方法。

4. 堆排序：通过建堆和筛选操作实现排序。时间复杂度为O(nlogn)，空间复杂度为O(1)。堆排序是一种不稳定的排序方法，适用于大量数据的排序。

5. 归并排序：将两个或两个以上的有序子序列合并为一个有序序列。时间效率为O(nlogn)，空间效率为O(n)。归并排序是稳定的排序方法。

6. 基数排序：分配+收集的方式，适用于数字数据的排序。时间效率与关键字个数和取值范围有关，空间效率与数据量和取值范围有关。基数排序是稳定的排序方法。