排序算法的稳定性
哪些公司问过
答案要点
- 稳定:相等元素排序后保持原有的相对顺序
- 稳定:冒泡、插入、归并、计数、基数、TimSort;不稳定:快排、堆排、选择、希尔
- 快排不稳定:划分时的交换会让相等元素跨过彼此
- 稳定性意义:多关键字排序时,后一次排序不会打乱前一次的结果
- 复杂度:快排平均 O(n log n)、最坏 O(n²);堆排 O(n log n);归并 O(n log n)、额外空间 O(n)
易错点
- 说快速排序是稳定的
- 把稳定性和时间复杂度混为一谈
- 说不出稳定性在什么场景有用
- 忽略快排最坏 O(n²) 的情况
面试官常见追问
- 快速排序的最坏情况是什么,怎么避免?
- std::sort 和 std::stable_sort 有什么区别?
- 手写冒泡排序和插入排序,复杂度是多少?
- 快排和堆排在实际中怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场
- 取值范围有限的海量数据排序,如考生分数5 场