java sort原理,Collections.sort() 的实现原理

r囧r小猫 2023-01-15 08:25 67阅读 0赞

package com.java.collections.demo;

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

public class Ctest01 \{

public static void main(String\[\] args) \{

List list = Arrays.asList("6", "1", "3", "1","2");

Collections.sort(list);//

System.out.println(list.toString());

执行main方法之后，输出结果如下

\[1, 1, 2, 3, 6\]

注：Arrays.asList() 返回的是ArrayList的实例对象

package java.util;

public class Arrays \{

@SafeVarargs

@SuppressWarnings("varargs")

public static List asList(T... a) \{

return new ArrayList<>(a);

package java.util;

public class Collections \{

@SuppressWarnings("unchecked")

public static > void sort(List list) \{

list.sort(null);//

package java.util;

public class ArrayList \{

@Override

@SuppressWarnings("unchecked")

public void sort(Comparator super E> c) \{

final int expectedModCount = modCount;

Arrays.sort((E\[\]) elementData, 0, size, c);//

if (modCount != expectedModCount) \{

throw new ConcurrentModificationException();

modCount++;

package java.util;

public class Arrays \{

public static void sort(T\[\] a, int fromIndex, int toIndex, Comparator super T> c) \{

if (c == null) \{

sort(a, fromIndex, toIndex); //

\} else \{

rangeCheck(a.length, fromIndex, toIndex);

if (LegacyMergeSort.userRequested)

legacyMergeSort(a, fromIndex, toIndex, c);

else

TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);

public static void sort(Object\[\] a, int fromIndex, int toIndex) \{

// 检查参数的合理性

rangeCheck(a.length, fromIndex, toIndex);

// LegacyMergeSort.userRequested 默认为false

if (LegacyMergeSort.userRequested) \{

// 使用一种老的归并排序

legacyMergeSort(a, fromIndex, toIndex);

\} else \{

ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0); //

package java.util;

class ComparableTimSort \{

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; // 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);

binarySort(a, lo, hi, lo + initRunLen);

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.

\*/

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;

package com.java.collections.demo;

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.List;

public class Ctest01 \{

public static void main(String\[\] args) \{

List list = Arrays.asList("6", "1", "3", "1","2");

Collections.sort(list, new Comparator() \{

@Override

public int compare(String o1, String o2) \{

// TODO Auto-generated method stub

return Integer.valueOf(o1) - Integer.valueOf(o2);

\});//

System.out.println(list.toString());

package java.util;

public class Collections \{

@SuppressWarnings(\{"unchecked", "rawtypes"\})

public static void sort(List list, Comparator super T> c) \{

list.sort(c);//

package java.util;

public class ArrayList \{

@Override

@SuppressWarnings("unchecked")

public void sort(Comparator super E> c) \{

final int expectedModCount = modCount;

Arrays.sort((E\[\]) elementData, 0, size, c);//

if (modCount != expectedModCount) \{

throw new ConcurrentModificationException();

modCount++;

package java.util;

public class Arrays \{

public static void sort(T\[\] a, int fromIndex, int toIndex, Comparator super T> c) \{

if (c == null) \{

sort(a, fromIndex, toIndex);

\} else \{

rangeCheck(a.length, fromIndex, toIndex);

if (LegacyMergeSort.userRequested)

legacyMergeSort(a, fromIndex, toIndex, c);

else

TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); //

package java.util;

class TimSort \{

static 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 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;

java sort原理,Collections.sort() 的实现原理

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 java sort原理,Collections.sort() 的实现原理

相关详解 Elasticsearch Index Sorting 原理

相关 MySQL Sort原理

相关 JAVA Arrays.sort()和Collectons.sort() 原理分析

相关浅谈 JavaScript array.sort(compare()) 实现原理.

相关 Java注解的实现原理

相关 Collections,sort()实现原理

相关 [Java] Volatile的实现原理

相关 [Java] Synchronized的实现原理

相关线性排序原理及其实现 counting sort