Java 集合中的排序算法浅析
💡
原文中文，约11400字，阅读约需28分钟。
📝
内容提要
TimSort是一种自适应、混合、稳定的排序算法，时间复杂度为O(nlogn)，空间复杂度为O(n)，minrun的取值建议在32~64之间，它会对待排序序列进行划分，找出连续有序的子序列，并且利用栈结构进行合并，还有一种gallop(飞奔)模式可以减少参与归并的数据长度。Java1.8中的TimSort类位于java.util.TimSort，DivalQuickSort算法也是一种快速排序，它会选取两个数作为pivot，划分出三个区间，每次递归迭代时遍历待处理的区域数据，然后比较它应该放的位置，并进行交换操作。
🎯
关键要点
- TimSort是一种自适应、混合、稳定的排序算法，时间复杂度为O(nlogn)，空间复杂度为O(n)。
- TimSort通过划分待排序序列，找出连续有序的子序列，并利用栈结构进行合并。
- 建议minrun的取值在32~64之间，以提高排序效率。
- Java1.8中的TimSort类位于java.util.TimSort。
- DivalQuickSort算法是一种快速排序，选取两个数作为pivot，划分出三个区间进行排序。
- Java的排序API提供了通用、高效、实用的排序功能，使用频繁且具有独特之处。
- Collections.sort方法实现了稳定且默认升序排序的功能。
- TimSort的核心思想是利用部分有序的数据来减少排序时间，run表示连续有序的最长子序列。
- 合并过程是实时的，利用栈结构和特定条件进行合并，以提高效率。
- gallop模式可以减少参与归并的数据长度，避免不必要的比较。
- DivalQuickSort在特定条件下使用其他排序算法，如归并和插入排序，以提高性能。
- 在相同环境下，双轴快排DivalQuickSort表现优异，适合处理大规模数据集。
- 工业用排序算法通常是多种算法的混合，适应特定条件以提高性能。
➡️
