Java Arrays.sort和Collections.sort排序实现原理解析
作者:一年e度的夏天 发布时间:2022-11-01 01:53:57
1、使用
排序
2、原理
事实上Collections.sort方法底层就是调用的array.sort方法,而且不论是Collections.sort或者是Arrays.sort方法,
跟踪下源代码吧,首先我们写个demo
public static void main(String[] args) {
List<String> strings = Arrays.asList("6", "1", "3", "1","2");
Collections.sort(strings);//sort方法在这里
for (String string : strings) {
System.out.println(string);
}
}
简单得不能再简单的方法了,让我们一步步跟踪
OK,往下面看,发现collections.sort方法调用的list.sort
然后跟踪一下,list里面有个sort方法,但是list是一个接口,肯定是调用子类里面的实现,这里我们demo使用的是一个Arrays.asList方法,所以事实上我们的子类就是arraylist了。OK,看arraylist里面sort实现,选择第一个,为什么不选择第二个呢?(可以看二楼评论,解答得很正确,简单说就是用Arrays.sort创建的ArrayList对象)
OK,发现里面调用的Arrays.sort(a, c); a是list,c是一个比较器,我们来看一下这个方法
我们没有写比较器,所以用的第二项,LegacyMergeSort.userRequested这个bool值是什么呢?
跟踪这个值,我们发现有这样的一段定义:
> Old merge sort implementation can be selected (for
> compatibility with broken comparators) using a system property.
> Cannot be a static boolean in the enclosing class due to
> circular dependencies. To be removed in a future release.反正是一种老的归并排序,不用管了现在默认是关的
OK,我们走的是sort(a)这个方法,接着进入这个
接着看我们重要的sort方法
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // array的大小为0或者1就不用排了
// 当数组大小小于MIN_MERGE(32)的时候,就用一个"mini-TimSort"的方法排序,jdk1.7新加
if (nRemaining < MIN_MERGE) {
//这个方法比较有意思,其实就是将我们最长的递减序列,找出来,然后倒过来
int initRunLen = countRunAndMakeAscending(a, lo, hi);
//长度小于32的时候,是使用binarySort的
binarySort(a, lo, hi, lo + initRunLen);
return;
}
//先扫描一次array,找到已经排好的序列,然后再用刚才的mini-TimSort,然后合并,这就是TimSort的核心思想
ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
回到5,我们可以看到当我们写了比较器的时候就调用了TimSort.sort方法
,源码如下
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
和上面的sort方法是一样的,其实也就是TimSort的源代码
3、总结
不论是Collections.sort方法或者是Arrays.sort方法,底层实现都是TimSort实现的,这是jdk1.7新增的,以前是归并排序。TimSort算法就是找到已经排好序数据的子序列,然后对剩余部分排序,然后合并起来
来源:https://blog.csdn.net/u011410529/article/details/56668545
猜你喜欢
- 本文实例讲述了Java文件上传与文件下载实现方法。分享给大家供大家参考,具体如下:Java文件上传数据上传是客户端向服务器端上传数据,客户端
- 一、安装MongoDB4.0.3(××)1.1、官方安装文档https://docs.mongodb.com/manual/tutorial
- 一直使用Eclipse环境开发Android,也尝鲜使用过Android Studio去开发,各种IDE配合Android SDK及SDK原
- 主要技术实现:spring、 springmvc、 redis、 springboot、 mybatis 、sessi
- Gson是Google的一个开源项目,可以将Java对象转换成JSON,也可能将JSON转换成Java对象。Gson里最重要的对象有2个Gs
- DateTime.Now.ToString("dddd",new System.Globalization.Cultur
- 本文以一个实例简单实现了类的创建与初始化,实现代码如下所示:using System;using System.Collections.Ge
- 本文实例讲述了java获取中文拼音首字母工具类定义与用法。分享给大家供大家参考,具体如下:package com.sw.documentar
- 本文实例讲述了Java类加载器和类加载机制。分享给大家供大家参考,具体如下:一 点睛1 类加载器负责将.class文件(可能在磁盘上,也可能
- 一.hutool工具摘抄一段hutool工具的简介:Hutool是一个小而全的Java工具类库,通过静态方法封装,降低相关API的学习成本,
- 最近有由于需要,我开始接触阿里云的云市场的印刷文字识别-营业执照识别这里我加上了官网的申请说明,只要你有阿里云账号就可以用,前500次是免费
- PowerPoint幻灯片中可插入公式,用于在幻灯片放映时演示相关内容的论证、推算的依据,能有效地为演讲者提供论述的数据支撑。通过后端程序代
- 前言最近在逛博客的时候看到了有关Redis方面的面试题,其中提到了Redis在内存达到最大限制的时候会使用LRU等淘汰机制,然后找了这方面的
- 图1如图1,我们工作过程中,无论平台网站还是企业官网,总少不了新闻展示。如某天产品经理跟我们说,推广人员想要抓取百度新闻中热点要闻版块提高站
- 我们经常需要对我们的开发的软件做各种测试, 软件对系统资源的使用情况更是不可少, 目前有多个监控工具, 相比JProfiler对系统资源尤其
- 1. 概述在这篇文章中,我们将使用Spring Boot实现一个基本的邮箱注册账户以及验证的过程。我们的目标是添加一个完整的注册过程,允许用
- 本文实例为大家分享了Java实现简单学生管理系统的具体代码,供大家参考,具体内容如下名为StudentManageTest的Java测试类i
- 目录Set接口概述HashSet实现类1、HashSet 具有以下特点:2、HashSet 集合判断两个元素相等的标准3、向HashSet中
- 本文介绍了详解Maven * Nexus的安装与使用,分享给大家,具体如下:1.安装1.1 安装docker并加速yum update &am
- 说到Java的本地存储,肯定使用IO流进行操作。首先,我们需要一个创建文件的函数createNewFile:public static bo