排序算法

平均时间复杂度

最好情况

最坏情况

空间复杂度

稳定性

冒泡排序

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)

稳定

堆选归集与初始序列无关