排序算法的性质
文章目录
| 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 每趟是否能确定一个元素的位置 | 适用于 | 比较次数与初始序列是否有关 | |
|---|---|---|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳 | no | 顺序和链式 | no |
| 折半插入排序 | O(n^2) | O(1) | 稳 | no | 仅顺序 | no | ||
| 希尔排序(缩小增量排序) | O(n^1.3) | O(1) | 不稳 | no | 仅顺序 | 与增量序列有关 | ||
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳 | yes | 仅顺序 | yes |
| 快速排序(平均性能最优) | O(nlog2n) | O(nlog2n) | O(n^2) | O(log2n) | 不稳 | yes | 仅顺序 | yes,取决于划分操作 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳 | yes | 顺序和链式 | no |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳 | yes | 仅顺序 | no |
| 2路归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳 | no | 仅顺序 | |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 基你太稳 | no | 通常采用链式 | no |
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论