排序类型
平均情况
最好情况
最坏情况
辅助空间
稳定性
冒泡排序
O(n²)
O(n)
O(n²)
O(1)
稳定
选择排序
O(n²)
O(n²)
O(n²)
O(1)
不稳定
直接插入排序
O(n²)
O(n)
O(n²)
O(1)
稳定
折半插入排序
O(n²)
O(n)
O(n²)
O(1)
稳定
希尔排序
O(n^1.3)
O(nlogn)
O(n²)
O(1)
不稳定
归并排序
O(nlog₂n)
O(nlog₂n)
O(nlog₂n)
O(n)
稳定
快速排序
O(nlog₂n)
O(nlog₂n)
O(n²)
O(nlog₂n)
不稳定
堆排序
O(nlog₂n)
O(nlog₂n)
O(nlog₂n)
O(1)
不稳定
计数排序
O(n+k)
O(n+k)
O(n+k)
O(k)
稳定
桶排序
O(n+k)
O(n+k)
O(n²)
O(n+k)
(不)稳定
基数排序
O(d(n+k))
O(d(n+k))
O(d(n+kd))
O(n+kd)
稳定
注: 桶排序的稳定性取决于桶内排序的稳定性, 因此其稳定性不确定. 基数排序中, k代表关键字的基数, d代表长度, n代表关键字的个数.
愿以此文怀念下我那远去的算法课程.
未完待续…
感谢 提供图片支持. 特别感谢 不是小羊的肖恩 在简书上发布的 JS家的排序算法 提供的讲解.
您可能感兴趣的文章: