快速排序
快速排序（Quick Sort）是分治思想的典型应用。算法选取一个基准元素（pivot），将数组划分为小于和大于基准的两部分，再递归对两部分排序。
核心步骤：选择 pivot（通常取首、尾或三数取中）→ 分区（partition）→ 递归左右子数组。分区时使用双指针，左指针找大于 pivot 的元素，右指针找小于 pivot 的元素，交换后继续，直至相遇。
快排的平均时间复杂度为 O(n log n)，最坏为 O(n²)（如已排序数组且选首元素为 pivot）。空间复杂度 O(log n) 来自递归栈。快排是不稳定排序，因为交换可能改变相同元素的相对顺序。
归并排序
归并排序（Merge Sort）采用分治策略：将数组不断二分至单个元素，再两两合并为有序序列。
合并过程：维护两个有序子数组的指针，每次取较小者放入结果数组。当子数组长度为 n 时，合并需要 O(n) 时间和 O(n) 辅助空间。
归并排序的时间复杂度恒为 O(n log n)，与数据分布无关。空间复杂度 O(n) 用于临时数组。归并是稳定排序，合并时相等元素取左侧即可保持顺序。缺点是需要额外空间，不适合内存紧张场景。
时间复杂度对比
| 算法 | 平均 | 最坏 | 空间 | 稳定性 | |------|------|------|------|--------| | 快排 | O(n log n) | O(n²) | O(log n) | 否 | | 归并 | O(n log n) | O(n log n) | O(n) | 是 | | 堆排序 | O(n log n) | O(n log n) | O(1) | 否 |
选择算法时：需要稳定性选归并；内存受限选堆排序；一般场景快排常数因子小，实践中最快。