先来个表格总结直观展示下：
| 算法种类 | 时间复杂度 | 空间复 杂度 | 稳定性 | |||
| 最好情况 | 平均情况 | 最坏情况 | ||||
| 插入排序 | 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 折半插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | |
| 希尔排序 | O(n^1.3) | O(nlogn) | O(n^2) | O(1) | 不稳定 | |
| 交换排序 | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 | |
| 选择排序 | 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | |
| 归并排序 | 二路归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 | |
下面详细说明一下：
1.时间复杂度：（不包括基数排序）
平均情况下，快速排序、希尔排序（和增量有关，n在特定范围内为O(n^1.3)）、归并排序、堆排序时间复杂度为O(nlogn)，其他均为O(n^2)；
最坏情况下，快速排序、希尔排序为O(n^2)，其他均和平均情况下相同；
最好情况下，直接插入排序、折半插入排序、冒泡排序时间复杂度为O(n)（初始序列有序）。
2.空间复杂度：
快速排序O(logn)，2路归并排序O(n)，基数排序O(r)，其他都是O(1)。
3.稳定性：
希尔排序、快速排序、简单选择排序、堆排序不稳定，其他都是稳定的。
4.其他：
经过一趟排序，能保证一个元素到达最终位置：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）。
5.例题：
若输入数据存储在带头结点的双向循环链表中，下面排序算法是否仍然适用？
- 快速排序：适用。因为可以快速定位到第一个元素和最后一个元素结点，然后通过1个指针从头部向后移动，另外一个指针从尾部向前移动，逐一与基准元素进行比较，并能够通过修改指针完成结点交换操作。
- 直接插入排序：适用。因为可以方便地找到前驱后继和通过修改指针完成结点交换操作。
- 简单选择排序：适用。因为只需要移动指针遍历链表并通过修改指针完成结点交换。
- 堆排序：不适用。因为双向循环链表无法很方便地找到完全二叉树的双亲与孩子结点。
京公网安备 11010502036488号