时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
💡
原文中文，约8100字，阅读约需20分钟。
📝
内容提要
归并排序和快速排序是两种常用的分治算法，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)，快速排序是原地排序，时间复杂度也为O(nlogn)，空间复杂度为O(n)。归并排序的优化策略包括减少额外空间的使用、跳过合并步骤、对小规模子数组使用插入排序，快速排序的优化策略包括切换到插入排序、优化基准数的选择、三向切分。
🎯
关键要点
- 归并排序和快速排序是常用的分治算法。
- 归并排序时间复杂度为O(nlogn)，空间复杂度为O(n)。
- 快速排序是原地排序，时间复杂度为O(nlogn)，空间复杂度为O(n)。
- 归并排序的步骤包括划分和合并。
- 归并排序的主要缺点是需要额外的O(n)空间。
- 归并排序的优化策略包括减少额外空间、跳过合并步骤和对小规模子数组使用插入排序。
- 快速排序的步骤包括哨兵划分和排序子数组。
- 快速排序的平均时间复杂度为O(nlogn)，最差时间复杂度为O(n2)。
- 快速排序的优化策略包括切换到插入排序、基准数优化和三向切分。
- 归并排序由于是非原地排序，使用额外空间，应用不如快速排序广泛。
- 快速排序在哨兵划分不平衡时效率低下。
➡️
