基本情况
Java中sort方法主要有Collections.sort,Arrays.sort方法。并且Collections.sort底层调用的Arrays.sort方法。Arrays.sort底层一共使用了3中排序方法:插入排序、快速排序、优化的递归排序(TimSort)。TimSort的主要思想:找出有序的最长序列,排序其他数据,最后整合排序。
原因
- 快速排序:针对基本类型(int、short、long等)不稳定;不要求稳定性
- 归并排序:引用类型,稳定;要求稳定性
- 稳定性:比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。引用类型对象相等判断可能只判断关键属性,最好保持其他属性顺序与排列前一致;且归并相对快速排序,排序比较次数较少,移动次数较多,比较比移动耗时。
总结
1、数据量小于60,插入排序
2、大于60
- 基本类型:快速排序
- 引用类型:归并排序
参考
关于java中Arrays.sort()的几种用法
Arrays.sort和Collections.sort实现原理解析
网友评论