时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队

原文约8100字，阅读约需20分钟。发表于：。

归并排序遵循：分解待排序的 n 个元素的序列成各具 n/2 个元素的两个子序列，将长数组的排序问题转换为短数组的排序问题，当待排序的序列长度为 1 时，递归划分结束：合并两个已排序的子序列得出已排序的最终结果归并排序最吸引人的性质是它能保证将长度为 n 的数组排序所需的时间和 nlogn 成正比；它的主要缺点是所需的额外空间和 n 成正比。：借助辅助数组实现合并，使用 O(n) 的额外空间；递归深度为 logn，使用 O(logn) 大小的栈帧空间。忽略低阶部分，所以空间复杂度为 O(n)

归并排序和快速排序是两种常用的分治算法，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，快速排序是原地排序，时间复杂度也为O(nlogn)，空间复杂度为O(n)。归并排序的优化策略包括减少额外空间的使用、跳过合并步骤、对小规模子数组使用插入排序，快速排序的优化策略包括切换到插入排序、优化基准数的选择、三向切分。