各种排序算法的性能特点
Jihongchang（讨论 | 贡献）2022年11月11日 (五) 06:12的版本 （建立内容为“来自《算法第4版本》 {| class="wikitable" ! rowspan="2" |算法 ! rowspan="2" |是否稳定 ! rowspan="2" |是否为原地排序 ! colspan="2" |将N个元…”的新页面）
来自《算法第4版本》
| 算法 | 是否稳定 | 是否为原地排序 | 将N个元素排序的复杂度 | 备注 | |
|---|---|---|---|---|---|
| 时间复杂度 | 空间复杂度 | ||||
| 选择排序 | 否 | 是 | N2 | 1 | |
| 插入排序 | 是 | 是 | 介于N和N2之间 | 1 | 取决于输入元素的排列情况 |
| 希尔排序 | 否 | 是 | NlogN?
N6/5 |
1 | |
| 快速排序 | 否 | 是 | NlogN | lgN | 运行效率由概率提供保证 |
| 三向快速排序 | 否 | 是 | 介于N和NlogN之间 | lgN | 运行效率由概率保证，同时也取决于输入元素的分布情况 |
| 归并排序 | 是 | 否 | NlogN | N | |
| 堆排序 | 否 | 是 | NlogN | 1 | |
快速排序是最快的通用排序算法。