算法分类：
- 比较类排序:
通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序 - 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序
- 内部排序：待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列
- 外部排序：指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的
内部排序.png
复杂度，稳定性
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n1.3)|O(n2) | O(1) | 不稳定 |
| 选择排序 | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2(n)) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(nlog2(n)) | O(log2(n)) | 不稳定 |
| 归并排序 | O(nlog2(n)) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n+k) | 稳定 |
网友评论