logo头像

不忘初心,奋力前行

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

本文于435天之前发表,文中内容可能已经过时,如有问题,请联系我。

排序算法

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

冒泡排序

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)

稳定

堆选归集与初始序列无关

支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!