参考答案
内容深度:基础 · 无代码示例 · 来源:外部链接 · 已复核 · 28 天前更新
快排
- 选 pivot 分区,左小右大,递归;平均 O(n log n),最坏 O(n²)(已排序/极端 pivot),原地但不稳定。
- 适合内存排序/平均性能;随机 pivot/三数取中缓解最坏;小数组可切插入排序。
归并
- 分治合并两个有序子数组;稳定 O(n log n),需要 O(n) 额外空间;适合链表/外部排序/要求稳定。
- 递归/迭代自底向上;合并时比较取小,稳定性靠先取左。
选择
- 要稳定/最坏可控→归并;内存敏感/平均快→快排;工程中常混合(Timsort/内省排序)。