【笔记】各种内排序方法的性能——总表

时间复杂度

以下是各个排序方法复杂度总表

如果下面表中有错误的,还请评论留言以下

排序方式 时间复杂度 空间复杂度 稳定性
平均情况 最坏情况 最好情况
直接插入排序 O(n^2) O(n^2) O(n) O(1) 稳定
折半插入排序 O(n^2) O(n^2) O(n) O(nlog_2n) 稳定
希尔排序 O(n^1.3) 不稳定
冒泡排序 O(n^2) O(n^2) O(n) O(1) 稳定
快速排序 O(nlog_2n) O(n^2) O(nlog_2n) O(log_2n) 不稳定
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定
堆排序 O(nlog_2n) O(nlog_2n) O(nlog_2n) O(1) 不稳定
归并排序 O(nlog_2n) O(nlog_2n) O(nlog_2n) O(n) 稳定
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 稳定

发表评论 / Comment

用心评论~

金玉良言 / Appraise
haohuotui.comLV 1
2019-12-02 15:13
一看到涉及到程序的问题,我就感觉很复杂!感觉高深莫测啊!
龙奇网LV 2
2019-11-24 19:54
嗯,感觉好深奥