基本概念
排序的稳定性：
排序后大小相同的元素的相对位置不发生改变的排序为稳定排序，反之不稳定。
内排序与外排序：
根据在排序过程中待排序的记录是否全部放置在内存中
主要介绍内排序
内排序性能
- 时间性能
- 比较次数
- 移动次数
- 辅助空间
- 算法的复杂性
算法分类
总结
| 算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 选择 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔 | O(n log n)~O(n2) | O(1) | 不稳定 | ||
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快排 | O(n log n) | O(n log n) | O(n2) | O(log n)~O(n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | 取决于具体实现 | 不稳定 |
| 计数 | O(n + m) | O(n + m) | O(n + m) | O(n + m) | 稳定 |
| 桶排序 | O(n + m) | O(n + m) | O(n2) | O(n + m) | 稳定 |
| 基数排序 | O(n * d) | O(n * d) | O(n2) | O(n + k) | 稳定 |
桶排序最坏时间复杂度：所有元素在一个桶且用时间复杂度为O(n2)的算法
| 归并排序 | 容器 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 自上而下 | 数组 | O(n log n) | O(n + log n) |
| 链表 | O(n log n) | O(logn) | |
| 自下而上 | 数组 | O(n log n) | O(n) |
| 链表 | O(n log n) | O(1) |
若有收获，就点个赞吧
0 人点赞
