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

r囧r小猫 2023-01-15 08:25 122阅读 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() 的实现原理

发表评论取消回复

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

相关阅读

相关 Arrays.sort和Collections.sort实现原理解析_软件开发

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

相关详解 Elasticsearch Index Sorting 原理

相关 MySQL Sort原理

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

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

相关 Collections,sort()实现原理

相关 [Java] Volatile的实现原理

相关 [Java] Synchronized的实现原理

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