常用排序算法复杂度和稳定性情况总结

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
插入排序 O(n2) O(n) O(n2) O(1) 稳定
希尔排序 O(nlogn)~O(n2) O(n2) O(n2) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn)~O(n) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n+k) O(n+k) O(n+k) O(k) 稳定
桶排序 O(n+k) O(n+k) O(n2) O(n+k) 稳定
基数排序 O(n×k) O(n×k) O(n×k) O(n+k) 稳定

堆选归集与初始序列无关

发表评论

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