排序算法的时间复杂度和空间复杂度
| 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 是否为稳定排序 | 是否为原地排序 | |
|---|---|---|---|---|---|---|
| 冒泡排序 | $O(n)$ 初始数组正序 | $O(n^2)$ 初始数组逆序 | $O(n^2)$ | $O(1)$ 原地使用数组，无额外内存开销 |
是 | 是 |
| 插入排序 | 是 | 是 | ||||
| 选择排序 | $O(n^2)$ [每一趟都选出最值,一趟为 $O(n)$,一共跑$n$趟] | 否 | 是 | |||
| 希尔排序 | $O(n)$ | $O(n^2)$ | $O(n^{1.3}$) | 否 | 是 | |
| 快速排序 | $O(nlogn)$ | $O(n^2)$每次都取到的是最大值 | $O(nlogn)$ | $O(logn)$ [递归栈的深度] | 否 | 是 |
| 堆排序 | $O(nlogn)$ 堆排序时间复杂度分析：堆调整的时间复杂度为$O(logn)$对n元素进行堆调整时间复杂度为 $O(nlogn)$] 堆调整时间复杂度分析：根节点和排在最后的序号为i的叶子结点交换,堆调整的操作次数=树的深度=$logn$ |
$O(1)$ 原地使用数组，无额外内存开销 | 否 | 是 | ||
| 归并排序 | 划分区间的时间复杂度：$O(logn)$ 归并$n$层的时间复杂度：$O(nlogn)$ 归并每层的时间复杂度：$O(n)$ 归并的层数：$logn$ 总时间复杂度：$O(nlogn)+ O(logn)=O(nlogn)$ |
$O(n+logn)$ [$logn$: 递归栈的深度] [$n$: 辅助储存结果数组的长度] | 是 | 否 | ||
| 计数排序 | $O(n+k)$ $k$为辅助桶的数据范围（数组最大值-最小值） 求最大最小值：$O(n)$ 遍历装入桶：$O(n)$ 循环输出元素：$O(k)$ |
$O(n+k)$ $n$：保存输出结果的数组 $k$：辅助桶数组 将输出结果直接覆盖到原数组，空间复杂度可将为$O(k)$ | 否 | 是 | ||
| 桶排序 | $O(n+k)$ | $O(k)$ | 是 | 否 | ||
| 基数排序 | $O(n*m)$ | 是 | 否 | |||
分类
