常见排序算法的对比
哪些公司问过
答案要点
- 快排:平均 O(n log n)、最坏 O(n²)、原地、不稳定;实践中最快(缓存友好、常数小)
- 归并:O(n log n)(含最坏)、稳定、需要 O(n) 额外空间;适合链表和外部排序
- 堆排:O(n log n)、原地、不稳定,缓存不友好
- 插入排序:O(n²),小规模或基本有序时最快;希尔排序是它的优化
- 稳定:冒泡、插入、归并;不稳定:选择、快排、堆排、希尔
易错点
- 说快排最坏也是 O(n log n)
- 把堆排序说成稳定
- 只背复杂度表,说不出各自的适用场景
- 忘了归并排序的额外空间
面试官常见追问
- 什么是排序的稳定性,有什么用?
- 数据基本有序时选什么?
- 标准库的 sort 用的是什么算法?
- 十亿个整数怎么排序?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场