全国咨询/投诉热线:400-618-4000

java培训:Arrays.sort()的内部排序机制

更新时间:2019年04月17日16时30分 来源:传智播客java培训 浏览次数:

  数组的操作可以使用java提供的工具类Arrays,其中Arrays.sort()方法用于数组的排序。
  基本数据类型数组的操作,使用经过优化的快速排序算法
  当数组的规模较小时,直接插入排序的比较次数并不会比快排或者归并多多少,其效率反而不如简单排序算法,所以在数组规模小于7时,使用直接插入排序,
  当数组规模较大时,合理的选择快排的枢轴元素,如在规模小于40时,在数组的首,中,尾三个位置上的数,取中间大小的数做枢轴;在数组规模大于40时,从数组中取位置均匀分布的9个数,然后每三个数一组取中间数,最后三个中间数再取中间数。确定枢轴后,与数组的第一个元素交换,之后的快排与普通快排一样。
  当数组中有大量重复元素时,选择重复元素作为枢轴,然后两个端各设置两个工作指针low、high,left、right用于始终指向要交换的元素位置,如5,2,5,6,4,3,5,1,5,7
  从high开始判断,low <= high,若high位置的元素 >= 基准元素high–,同时若high位置的元素 == 基准元素,high位置的元素与right位置的元素交换,同时right–,继续直到high位置的元素 < 基准元素。
  从low开始判断,low <= high,若low位置的元素 <= 基准元素low++,同时若low位置的元素 = 基准元素,low位置的元素与left位置的元素交换,同时left++,继续直到low位置的元素 > 基准元素。
  low、high位置的元素交换,同时low++、high–,然后再从high开始继续上面的过程,最后将重复的元素至于序列的两端,中间的序列分成了两部分,左面的为小于基准元素的,右面的为大于基准元素的,如5,5,2,1,4,3,7,6,5,5,此时low在7位置,high在3位置。
  将两端重复的元素都交换到中间后,对两端不等的元素使用快排,左侧外循环从下标0开始判断,若等于枢轴进入内循环,内循环从下标low - 1开始向前找不等于枢轴的,找到交换,直到外循环遇到不等于枢轴的退出;右侧外循环从下标n - 1开始判断,若等于枢轴进入内循环,内循环从下标high + 1开始向后找不等于枢轴的,找到交换,直到外循环遇到不等于枢轴的退出。
  引用数据类型数组的排序,使用经过优化的归并排序算法。
  当数组规模j较小时,使用直接插入排序。
  当属组规模较大时,使用归并排序,且当合并的两个有序序列中,低子序列的最高元素小于高子序列的最低元素时,无序执行合并算法,这个可以在merge算法里判断。
java培训

  传智Java培训拥有6大课程优势:

  ①独有的一站式IT职业教育体系,让学员通过6个月的线下学习实现高起点就业, 12个月的线上在职进阶课实现升职加薪,大幅提升学员的职场晋升速度。

  ②60+套技术解决方案,覆盖职场常见开发问题,让学员就业后快速上手开发难题,轻松成为核心员工。

  ③超大项目库,覆盖7大就业主流热门行业,让学员边学习边积累项目开发经验。

  ④超千人投入的3大课程研发库,每年耗资千万打造领先行业的优质课程。

  ⑤传智&华为课程共建,持续为课程输出前沿技术。

  ⑥120+超强师资团队,多为总监、架构师出身,除了专业技能,还为你规划适合你的职业发展路线。

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校区

    14天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    8天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    0天免费试学

    基础班入门课程限时免费

    申请试学名额

    12天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    10天免费试学

    基础班入门课程限时免费

    申请试学名额