首页技术文章正文

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

更新时间:2019-04-17 来源:黑马程序员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+超强师资团队,多为总监、架构师出身,除了专业技能,还为你规划适合你的职业发展路线。

分享到:
在线咨询 我要报名
和我们在线交谈!