一、基本排序算法
二、高级排序算法
三、各排序算法的比较
各排序算法总结
| 排序算法 | 平均时间复杂度 | 最好情况时间复杂度 | 最坏情况时间复杂度 | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|---|---|
| 插入排序 | O($n^2$) | O(n)，当序列已经有序时 | O($n^2$)，序列逆序时。 | O(1) | 是 | 数组大部分有序 |
| 选择排序 | O($n^2$) | O($n^2$) | O($n^2$) | O(1) | 否 | 数据量较小的情况 |
| 冒泡排序 | O($n^2$) | O($n^2$) | O($n^2$) | O(1) | 是 | 数据量较小的情况 |
| 希尔排序 | O(n^(1.3~2)) | O(n^(1.3~2)) | O(n^(1.3~2)) | O(1) | 否 | 增量序列的选取会影响排序时间，希尔排序没有快速排序算法快，中等大小规模表现良好，对规模非常大的数据排序不是最优选择，但是比O($n^2$)复杂度的算法快。 |
| 快速排序 | O(nlogn) | O(nlogn) | 哨兵选择为边界值时，O($n^2$) | O(nlogn) | 否 | 不适合元素较小的数组排序 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 否 | 需要大量的移动操作，且要额外的空间保存已排序数组 |
| 计数排序 | O(n) | O(n) | O(n) | O(n*2) | 否 | 假设数组元素都在0-k的范围内，并且需要两个辅助数组，如果数据分布不均匀，出现一个特别大的数据会导致额外的空间增加。 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 是 | 合并时需要额外的内存空间 |
| 基数排序 | O (nlog(r)m)，其中r为所采取的基数，而m为堆数 | O (nlog(r)m) | O (nlog(r)m) | O(r*m) | 是 | 需要额外的m个队列的辅助空间 |
