排序算法总结
发布时间 2023-04-16 00:48:12作者: lidongdongdong~
基于比较的排序算法 <E extends Comparable<E>>
排序的稳定：排序前相等的两个元素，排序后相对位置不变（元素交换位置如果是跳跃交换，就有可能造成不稳定）
可以试着想想排序算法对 [0, 1, 1, 0] 是如何排序的
1、如果元素只有一个域，稳定性没有意义
2、不依赖排序算法的稳定性，通过定义明确比较方式也可是实现稳定的排序
| 序号 |
排序算法 |
时间复杂度 |
空间复杂度 |
特殊数据 |
其他 |
稳定性 |
| 1 |
选择排序 |
O(N^2) |
O(1) |
|
|
× |
| 2 |
插入排序 |
O(N^2) |
O(1) |
完全有序，时间 O(N) |
|
✓ |
| 3 |
冒泡排序 |
O(N^2) |
O(1) |
完全有序，时间 O(N) |
|
✓ |
| 4 |
归并排序 |
O(N * logN) |
O(N) |
完全有序，时间 O(N) |
O(N * logN) 求解数组逆序对个数 |
✓ |
| 5 |
快速排序 |
O(N * logN) |
O(1) |
含有相同元素数组，三路快排 O(N) |
O(N) 求解 SelectK、TopK 问题 |
× |
| 6 |
堆排序法 |
O(N * logN) |
O(1) |
|
堆、优先队列、O(N * logK) 求解 TopK |
× |
| 7 |
希尔排序 |
O(N * logN)~O(N^2) |
O(1) |
|
分组的思想 |
× |