冒泡排序与快速排序的原理与区别
哪些公司问过
答案要点
- 冒泡:相邻比较交换,每轮把最大值移到末尾,可用标志位提前结束
- 冒泡最好 O(n),平均和最坏 O(n²),原地且稳定
- 快排:选基准分区后递归,平均 O(n log n),最坏 O(n²)
- 快排不稳定,递归栈平均 O(log n),用随机基准避免退化
- 更快的排序还有归并、堆排序,归并稳定但需 O(n) 额外空间
易错点
- 说快速排序是稳定排序
- 冒泡内层循环边界写错导致数组越界
- 忽略快排最坏情况,只说 O(n log n)
面试官常见追问
- 冒泡排序为什么是稳定的?
- 快排为什么不稳定?举个例子。
- 冒泡排序用 C 语言怎么写?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 取值范围有限的海量数据排序,如考生分数5 场