排序算法
简单实现了一下几种常见的内排序算法
- 希尔排序
- 归并排序
- 快速排序
- 堆排序
- 基数排序
- 桶排序
| 排序算法 | 平均执行效率 | 稳定性 | 备注 |
|---|---|---|---|
| 插入排序 | o(n^2) | 稳定 | 我觉得这个稳定性取决于实现的时候的停止条件 |
| 冒泡排序 | o(n^2) | 稳定 | |
| 选择排序 | o(n^2) | 非稳定 | 因为选择最小 or 最大元素交换的时候回改变原来的顺序 |
| 希尔排序 | o(nlogn) | 稳定 | 希尔排序是一个根据步长的来的插入排序 |
| 快排 | o(nlogn) | 非稳定 | 分治的方法，递归的处理子数组，每次寻找到一个数字的位置 |
| 堆排序 | o(nlogn) | 非稳定 | 用大顶堆 or 小顶堆实现，调整堆的有序性需要 logn 的时间 |
| 归并排序 | o(nlogn) | 稳定 | 使用分治，每次合并两个已经有序的数组 |