博客园 - 乂墨EMO
·
为什么java默认的排序算法采用归并排序Timsort - 乂墨EMO
💡
原文中文，约500字，阅读约需2分钟。
📝
内容提要
双轴快速排序是对普通快速排序的优化，通过选择两个分区点将数组分为三部分，以提高性能。Timsort算法是对归并排序的优化，适用于有序性好的情况，具有稳定性，最坏情况下空间复杂度为n/2。
🎯
关键要点
- 双轴快速排序是对普通快速排序的优化，通过选择两个分区点将数组分为三部分。
- 普通快速排序是单轴的，只选择一个分区点进行划分。
- 双轴快速排序主要解决选择分区点为最大（小）值时性能急剧下降的问题。
- Timsort算法是对归并排序的一系列优化，适用于有序性好的情况。
- 当排序数量大于286且连续性好时，采用Timsort算法。
- 在连续性好的情况下，快排的时间复杂度可能退化为O(n²)，因此要避免使用快排。
- Timsort是稳定的算法，当前排序的数组中已经有排序好的数时，其时间复杂度小于O(nlogn)。
- Timsort算法在最坏情况下需要的临时空间为n/2，最好情况下只需很小的临时存储空间。
➡️
