目前共学习了:冒泡排序、直接插入排序、选择排序、希尔排序、快速排序、归并排序几种排序算法,下面比较一下它们的性能
I. 时间复杂度比较:
II. 空间复杂度比较和稳定性比较
排序方法 | 辅助空间 | 稳定性 | 适合情况 |
---|---|---|---|
冒泡排序 | O(1) | 稳定 | 不太多(简单) |
直接插入排序 | O(1) | 稳定 | 大部分已排序时(简单) |
选择排序 | O(1) | 不稳定 | 不太多(简单) |
希尔排序 | O(1) | 不稳定 | 不太多(较复杂) |
快速排序 | O(𝒍𝒐𝒈𝟐𝒏) | 不稳定 | 较多,基本有序时反而不好(较复杂) |
归并排序 | O(𝒏) | 稳定 | 都可以,较多时比较好(较复杂) |