排序算法是《数据结构与算法》中最基本的算法之一。
| 十大经典排序算法对比 | ||||||
|---|---|---|---|---|---|---|
| 排序算法 | 时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 | ||
| 平均 | 最好 | 最坏 | ||||
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 内部排序 | :heavy_check_mark: |
| 选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 内部排序 | :x: |
| 插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 内部排序 | :heavy_check_mark: |
| 希尔排序 | $O(n^{1.3})$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 内部排序 | :x: |
| 归并排序 | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n)$ | 外部排序 | :heavy_check_mark: |
| 快速排序 | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n^2)$ | $O(n\log_2n)$ | 内部排序 | :x: |
| 堆排序 | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(n\log_2n)$ | $O(1)$ | 内部排序 | :x: |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(k)$ | 外部排序 | :heavy_check_mark: |
| 桶排序 | $O(n+k)$ | $O(n+k)$ | $O(n^2)$ | $O(n + k)$ | 外部排序 | :heavy_check_mark: |
| 基数排序 | $O(n×k)$ | $O(n×k)$ | $O(n×k)$ | $O(n + k)$ | 外部排序 | :heavy_check_mark: |
详细说明及代码实现如下：