表格对比
| O(n2)的排序算法 | 思路要点 | 为什么稳定或者不稳定 | |
|---|---|---|---|
| 冒泡排序 | 每次冒泡把最大的数未排序数组的最后 |
unsorted+sorted(max) | 都是相邻交换,没有跨越式交换,发现相等时可以不移动 |
| 插入排序 | 反向遍历前面的排序部分,腾出位置,插入第一个未排序元素 | sorted+unsorted | 插入时可以插入相同元素的后面 |
| 选择排序 | 选择未排序区间最小的元素,交换到已排序区间的末尾 |
sorted+unsorted | 交换时可能跨过和自己相等的数,破坏稳定性 |
- 一个小总结
可以看出,冒泡排序和选择排序，都是把数组分为未排序和排序的两部分，然后从未排序部分找出最值放入到已排序部分。
- 思考 特定算法是依赖特定的数据结构的。这三个排序是基于数组实现的，如果基于链表来实现，还能work吗，复杂度又咋样?