快排与归并排序对比

快排与归并排序对比

一、面试常考点

1. 快排特点

平均 O(n log n)，原地排序，最坏 O(n^2)。（深入阅读：1. 稳定性敏感）

2. 归并特点

稳定排序，时间稳定 O(n log n)，但需额外 O(n) 空间。（深入阅读：2. 内存敏感）

二、应用建议

1. 稳定性敏感

优先归并。

2. 内存敏感

优先原地快排（并注意随机化 pivot）。