当待排序的关键字均不相同时，排序结果时唯一的，否则排序结果不唯一。若具有相同关键字的稳定性时针对所有输入的实例而言的，即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该算法就是不稳定的。 稳定的排序入下表所示。
| 稳定的排序 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 气泡排序 | 最差/平均都是O(n^2)，最好时O(n) | 1 |
| 鸡尾酒排序 | 最差/平均都是O(n^2)，最好时O(n) | 1 |
| 插入排序 | 最差/平均都是O(n^2)，最好时O(n) | 1 |
| 归并排序 | 最差/平均/最好都是O(nlogn) | O(n) |
| 桶排序 | O(n) | O(k) |
| 基数排序 | O(dn) | O(n) |
| 二叉树排序 | O(n log n) | O(n) |
| 图书排序 | O(n log n) | (1+kc)n |
不稳定的排序如下表所示：
| 不稳定的排序 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 选择排序 | 最差平均都是O(n^2) | 1 |
| 希尔排序 | O(n log n) | 1 |
| 堆排序 | 最差/平均/最好都是O(n log n) | 1 |
| 快速排序 | 平均时O(n log n),最坏是O(n^2) | O(log n) |
（1）按是否设计数据的内、外存交换分 在排序过程中，若整个文件都放在内存中处理，排序时不涉及数据的内、外存交换，称之内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。 注意：
内排序适用于记录个数不是很多的小文件；外排序则适用于记录个数太多，不能一次将其全部记录放入内存的大文件；（2）按照策略划分内部排序方法。 可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
（1）平方阶：直接插入排序、直接选择排序和冒泡排序。 （2）线性对数阶：快速、堆和归并排序。 （3）O(n^1+kc)：希尔排序 （4）线性阶排序：桶排序、箱排序和基数排序。
简单排序中直接插入最好，快读排序最快，当文件为正序时，直接插入排序和冒泡排序均最佳。
快速排序时目前基于比较的内部排序中被认为时最好的犯法噶，宕待排序的关键字时随机分布时，快速排序的平均时间最短。
堆排序所需要的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
新闻热点
疑难解答
