排序算法的复杂度、稳定性比较

时间:2022-07-15 16:52:06
常用排序算法
类型 排序方法 时间复杂度 辅助空间 稳定性
平均时间 最好时间 最坏时间
插入排序 直插排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(n^1.5) O(n) O(n^1.5) O(1) 不稳定
选择排序 选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
交换排序 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
快速排序 O(nlog2n) O(nlog2n) O(n^2) O(nlog2n) 不稳定
归并排序 归并排序 O(nlogn) O(nlogn) O(nlogn) O(1) 稳定
基数排序 基数排序 O(d(r+n)) O(d(r+n)) O(d(r+n)) O(dr+n) 稳定