快速排序和归并排序有什么区别？

直接回答

两者都是 O(n log n) 级别的分治排序。核心区别：快排"先划分后递归"，靠 pivot 就位，原地排序但不稳定，最坏 O(n²)；归并"先递归后合并"，合并两个有序子数组，需要 O(n) 辅助空间，但稳定且任何情况都是 O(n log n)。

展开解析

对比维度：稳定性上归并稳定、快排不稳定；空间上快排只需 O(log n) 递归栈，归并数组版本要 O(n) 缓冲；最坏情况归并始终 O(n log n)，快排最坏 O(n²)（随机化后概率极低）。实际性能上快排通常更快，因为缓存局部性好、常数小；归并顺序访问，适合链表和外部排序（链表归并可做到 O(1) 额外空间）。应用场景：内存紧张、追求平均速度选快排（多数语言的内置排序基于快排思想或其混合）；要求稳定、数据在链表/磁盘上选归并。追问：Java 对象排序为何用 TimSort（归并+插入混合）、快排如何三路划分应对重复键。