一、 分类描述1. 插入排序 直接插入排序：算法简单，稳定，适用于数据量小的情...
一、 分类描述
1. 插入排序
直接插入排序：算法简单，稳定，适用于数据量小的情况
希尔排序：直接插入排序的改进版，不稳定，对于待排序序列的不同情况效率相近
2. 交换排序
冒泡排序：算法简单，稳定，在数据基本有序的情况下效率较高
快速排序：算法效率高，不稳定，需要额外的辅助空间
3. 选择排序
直接选择排序：任何情况时间复杂度均为O(n^2)，不稳定，其优势在于交换次数少
堆排序：不稳定，对序列的原始顺序不敏感，适用于数据量大的情况
4. 归并排序
分治策略，稳定，适用于待排序列整体无序、部分有序的情况，需要额外的辅助空间
5. 基数排序
稳定；适用范围有限；当数据位数较小时，时间复杂度近似为O(n)，效率高于其它的稳定性排序算法
二、总结比较表
类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
最好 | 最坏 | 平均 | |||||
插入排序 | 直接插入 | O(n) | O(n^2) | O(n^2) | O(1) | O | 简单 |
希尔排序 | O(n^1.3) | O(n^2) | O(n^1.x) | O(1) | X | 较复杂 | |
交换排序 | 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | O | 简单 |
快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | X | 较复杂 | |
选择排序 | 直接选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | X | 简单 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | X | 较复杂 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | O | 较复杂 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | O | 较复杂 |
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
