首页 > 代码库 > Java Arrays 排序
Java Arrays 排序
Java SDK中的排序分为两种情况:
1、对基础类型数组的排序,使用DualPivotQuicksort类
a、如果是对char、short数组的排序,因为byte、char、short分别为8bit、16bit、16bit,能表示的最大数比较小(2^16):
所以,对它们的排序策略为数组长度小于32的时候使用直接插入排序、数组长度小于(128、32768)的时候使用快速排序、其他使用计数排序(时间长,需要128或者32768长度的数组辅助)
b、对于其他几种基础类型的数组排序,因为长度大,不适用计数排序,故策略为:如果数组长度小于32,使用直接插入排序,否则使用快速排序
2、对于非基础类型的排序,使用ComparableTimSort类
采用的排序算法为二分插入排序,特点是每次向有序区域插入一个值时,不是逐个向前比较,而是采用二分查找的思路,和中间那个值比较。
这个能减少查找的次数从N^2到nlogn,但是交换的次数仍然为N^2, 因为它是数组,而不是链表,无法直接插入到那个位置,还是需要找到index之后的元素逐个后移,不过这里可以使用System.arrayCoy的方法,提高性能
Java Arrays 排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。