排序
从简单的排序开始吧
| 种类 | 平均复杂度 | 最坏复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 快速排序 | O(nlogn) | O(n^2) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(n) | 稳定 |
| 基数排序 | O(k*n) | O(n^2) | 稳定 |
快排
每次选一个pivot，把小于这个数的数放在数组左边，大于的数放在数组右边，然后分治来做
归并
对每一段从上到下递归，然后对每段的左右两部分进行大小判定，并存入额外数组，最后向上并，每段进行合并
计数
就是个哈希，没啥好说的
希尔排序
根据间隔进行分段，每段进行插入排序
桶排序
计数排序升级版
创建多个桶，使用某种映射函数把原数组元素和对应的桶对应，桶内进行排序，然后再合并
基数排序
对每一位进行排序，用于整数排序