订单按库存降序且零库存置后的稳定排序
答案要点
- 规则:非零库存按库存降序,零库存放末尾,库存相同保持原相对顺序
- 先稳定分出零库存与非零两组,非零组按库存降序稳定排序后拼接零库存组
- 库存非负时直接按库存降序稳定排序即可,0 自然落到末尾
- 稳定排序可用 Java 对象数组排序、std::stable_sort、Python sorted 或手写归并
- 复杂度 O(n log n);库存范围小时可用计数排序达到 O(n+k)
易错点
- 用 std::sort 或快排,库存相同的订单顺序被打乱
- 比较器写成 b[1]-a[1],数值极端时可能溢出,用 Integer.compare 更稳妥
- 用交换法把零库存挪到末尾,会打乱零库存订单之间的原顺序
面试官常见追问
- 为什么不能用快速排序或 std::sort?
- 库存相同要按订单编号升序怎么办?
- 要求 O(1) 额外空间怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场