经典排序算法
2021-06-05 本文已影响0人
小杨同学97
序
虽然在各种编程语言中都提供了快速排序的函数或方法，而且刷算法题
时很少需要自己手写排序算法。排序算法都不是很难理解，但是有时候就特别尴尬，想要手写排序算法却写不出来。
所以我做了一个郑重的决定，手写n(1)遍经典排序算法。
十大经典排序算法比较
| 排序算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(1) | 不稳定 |
| 插入排序 | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlog n) | O(1) | 不稳定 |
| 归并排序 | O(nlog n) | O(n) | 稳定 |
| 快速排序 | O(nlog n) | O(log n) | 不稳定 |
| 堆排序 | O(nlog n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | 稳定 |
| 基数排序 | O(n x k) | O(n + k) | 稳定 |
关于时间复杂度
平方阶 (O(n^2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog^2n)) 排序 快速排序、堆排序和归并排序；
O(n1+k)) 排序，k 是介于 0 和 1 之间的常数。 希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
