前端菜鸟

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

常用排序算法
类型 排序方法 时间复杂度 辅助空间 稳定性
平均时间 最好时间 最坏时间
插入排序 直插排序 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) 稳定
(0)

本文由 Calamus 作者:calamus 发表,转载请注明来源!

热评文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注