常见排序算法的时间复杂度、空间复杂度、稳定性

时间:2022-01-10 16:53:12

排序算法 最佳时间复杂度 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性
冒泡排序 O(n) O(n²) O(n²)
O(1) 稳定
选择排序 O(n²)
O(n²)
O(n²)
O(1)
不稳定
插入排序 O(n)
O(n²)
O(n²)
O(1) 稳定
shell排序 O(n)
O(n^1.3) O(n²)
O(1)
不稳定
快速排序 O(nlog2n) O(nlog2n)
O(n²)

佳:O(log2n)

差:O(n)

不稳定
堆排序 O(nlog2n)
O(nlog2n)
O(nlog2n)
O(1)
不稳定
合并 O(nlog2n)
O(nlog2n)
O(nlog2n)
O(n) 稳定
基数排序 O(kn) O(kn)
O(n²)
O(n+r) 稳定

桶排序    O(n+c)      

       O(n+c)

        O(n²)         O(m+n) 不确定
注:n表示规模,k表示“数位”中的个数,c=n*(logn-Logm),m表示桶的数量。