Listのソート実現原理
33322 ワード
ListのソートはComparatorを使用する.sortソート
結果:
[16, 18, 18, 19, 24, 38, 58, 58, 77, 92][14, 32, 36, 44, 52, 61, 69, 80, 84, 97]
------------------
[18, 24, 38, 19, 16, 92, 18, 58, 77, 58][32, 44, 52, 14, 61, 36, 97, 69, 80, 84]
Process finished with exit code 0
ソートのソースコードを見てください.これはソート機能のメインエントリです.
一、入り口
まず何がめちゃくちゃなのかを明らかにする.
タイプTはComparableのサブクラスであり、このインタフェースのタイプはTまたはTの親である必要があります.
二、Collections.sortメソッド
次にtoArrayメソッドを実行し、このlistを配列に変換した後、Arrayのsortメソッドを呼び出して配列をソートし、ソートが完了したらそのリストオブジェクトのlist反復器に配列の値を書き込みます.これにより、リストオブジェクトにソートが完了した結果が表示されます.
ここで重点的に分析しますsortメソッド
三、Array.sortメソッド
このステップを実行すると2つのブランチが返されます.
まずcが空か否かを判断し,空であればsortメソッドを直接実行する.
そうでないと判断するuserRequestedのブール値.この値がTrueの場合はlegacyMergeSortソートアルゴリズムを実行し、そうでない場合はTimSortソートアルゴリズムを実行します.
まず最初にuserRequestedって何ですか???ソースを開けてみましょう
実際にはコードに内部クラスが定義されています.この中にはuserResuestという属性があります.この属性の値はsecurityパッケージのdoPrivilegedメソッドによって生成されます.この方法はnativeメソッドです.実はシステムの属性に基づいて古い集計ソート実装か新しいtimソート実装かを選択します.
次に、sortメソッド、legacyMergeSort()メソッド、およびTimSort.sort()法によるソースレベルの探究
3.1 sortメソッド
このsortと上記の違いは,2つのソートを呼び出すパラメータが異なり,実際にはこの2つのソートを呼び出すリロード方法である.
3.2 legacyMergeSort(Object[] a)
auxはaのオブジェクトコピーであり,aは実は前のlistが回転した配列である.mergeSortメソッドは,実は集計ソートアルゴリズムである()
最後のプログラムは、実は2つの値をループで1つのマージします.
例えば5 7 6 9 2 8 7 5 6 0というリストです.
最初のセグメント:5 7 6 9 2|8 7 5 6 0
2 5 6 7 9|0 5 6 7 8
次に各セグメントが7未満であるか否かを判断して最後のループを実行する
このステップはtrueに戻り、0を1位にします.
1回の類推でソート後のデータ再編成を行います.
これが集計ソートアルゴリズムです
3.3 ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
TimSortアルゴリズムは,並べ替えと挿入並べ替えに起源するハイブリッド並べ替えアルゴリズムであり,実際の世界の様々なデータにおいてより良い性能を得るために設計された.
TimSortアルゴリズムは,昇順部分の遡及と降順部分の性能後退を低減するために,その昇順と降順の特徴に従って入力をパーティション化した.ソートの入力単位は、個々の数値ではなく、個々のブロック-パーティションです.各パーティションはrunと呼ばれます.これらのrunシーケンスに対して,runを1つずつ取り出してルールに従ってマージする.マージのたびに2つのrunが1つのrunにマージされます.マージの結果はスタックに保存されます.すべてのrunが消費されるまでマージし、スタック上の残りのrunを1つしか残っていないまでマージします.このとき,この残りのrunは順序付けの結果である.
ここでは、このソートに特化した例を共有します.
出典:https://blog.csdn.net/bruce_6/article/details/38299199
例
*注意*:プレゼンテーションの便宜上、TimSortのminRunを直接2に設定します.そうしないと、小さな配列でプレゼンテーションできません.の同時にMIN_MERGEも2(デフォルトは32)に変更され、binary sortへの直接のアクセスを回避します.
初期配列は[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14]=>連続的な降順または昇順シーケンス(2.2.1)を探すとともに,
=>インスタック(2.2.3)現在のスタックブロックは[3]
=>mergeループに入る(2.2.4)do not mergeスタックサイズが1のみのため
=>連続降順または昇順シーケンス(2.2.1)[1,5,7][2,6,8,10,12][4,3,9,11,13,15,16,14]を探す
=>インスタック(2.2.3)現在のスタックブロックは[3,5]
=>mergeサイクルに入る(2.2.4)merge runLen[0]<=runLen[11]gallopRight:run 1の最初の要素がrun 0のどの位置に挿入されるべきかを探します("2"が"1"を挿入すべきかを探した後)、その後、以前のrun 0の要素(いずれもrun 1の最初の要素より小さい)2)gallopLeftを無視することができます:run 0の最後の要素がrun 1のどの位置に挿入されるべきかを探します("7"は"8"の前に挿入すべきであり、その後run 1の要素(いずれもrun 0の最後の要素より大きい)を無視することができ、このようにソートする必要がある要素は[5,7][2,6]しか残っておらず、mergeLowが完了した後の結果:[1,2,5,6,7,8,12][4,3,9,11,13,15,16,14]
=>スタックに入る(2.2.3)現在のスタックブロックは[8]現在のmergeループを終了するスタック内のブロックは1のみであるため
=>連続する降順または昇順シーケンス(2.2.1)[1,2,5,6,7,8,10,12][3,4][9,11,13,15,16,14]=>インスタック(2.2.3)現在のスタックブロックサイズは[8,2]
=>mergeループに入る(2.2.4)do not merge runLen[0]>runLen[1]
=>連続降順または昇順シーケンス(2.2.1)[1,2,5,6,7,8,10,12][3,4][9,11,13,15,16]を探す[14]
=>インスタック(2.2.3)現在のスタックブロックは[8,2,5]
=>do not merege run 1とrun 2はrunLen[0]<=runLen[1]+runLen[2 merge run 2とrun 3を満たさないためrunLen[1]<=runLen[21]gallopRight:run 1とrun 2が順序付けされて完了したことを発見した結果:[1,2,5,6,7,8,10,12][3,4,9,11,13,15,16][14]
=>スタックイン(2.2.3)現在のスタックインのブロックサイズは[8,7]runLen[0]>runLen[1]のためmergeループを終了する
=>連続的な降順または昇順シーケンスを探す(2.2.1)最後には[14]という要素しか残っていない:[1,2,5,6,7,8,10,12][3,4,9,11,13,15,16][14]
=>インスタック(2.2.3)現在のインスタックのブロックサイズは[8,7,1]
=>mergeサイクルに入る(2.2.4)merge runLen[0]<=runLen[1]+runLen[2]runLen[2]>runLen[2]のため、run 1とrun 2を先にマージする.(そうでなければrun 0とrun 1を先にマージする)1)gallopRight&2)gallopLeftのようにソートする必要がある要素は[13,15][14]残り、mergeHighが完了した後の結果:[1,2,5,6,7,8,10,12][3,4,9,11,13,14,15,16]現在スタックに入っているブロックは[8,8]
=>継続merge runLen[0]<=runLen[11)gallopRight&2)gallopLeftのソートが必要な要素は[5,6,7,8,10,12][3,4,9,11]残っているため、mergeHighが完了した後の結果:[1,2,3,4,5,6,7,8,10,11,12,13,14,15,16]現在のスタックのブロックサイズは[16]
=>final mergeは不要です.現在のスタックサイズは1です.
=>終了
public static void main(String[] args) {
List<Integer> ljh1 = new ArrayList<Integer>();
List<Integer> ljh2 = new LinkedList<Integer>();
for(int i=0;i<10;i++){
ljh1.add((int)(Math.random()*90+10));
ljh2.add((int)(Math.random()*90+10));
}
Collections.sort(ljh1);
Collections.sort(ljh2);
System.out.println(ljh1.toString());
System.out.println(ljh2.toString());
System.out.println("------------------");
Collections.shuffle(ljh1);
Collections.shuffle(ljh2);
System.out.println(ljh1.toString());
System.out.println(ljh2.toString());
}結果:
[16, 18, 18, 19, 24, 38, 58, 58, 77, 92][14, 32, 36, 44, 52, 61, 69, 80, 84, 97]
------------------
[18, 24, 38, 19, 16, 92, 18, 58, 77, 58][32, 44, 52, 14, 61, 36, 97, 69, 80, 84]
Process finished with exit code 0
ソートのソースコードを見てください.これはソート機能のメインエントリです.
一、入り口
public static <T extends Comparable super T>> void sort(List<T> list) {
list.sort(null);
}まず何がめちゃくちゃなのかを明らかにする.
タイプTはComparableのサブクラスであり、このインタフェースのタイプはTまたはTの親である必要があります.
二、Collections.sortメソッド
default void sort(Comparator super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}次にtoArrayメソッドを実行し、このlistを配列に変換した後、Arrayのsortメソッドを呼び出して配列をソートし、ソートが完了したらそのリストオブジェクトのlist反復器に配列の値を書き込みます.これにより、リストオブジェクトにソートが完了した結果が表示されます.
ここで重点的に分析しますsortメソッド
三、Array.sortメソッド
public static <T> void sort(T[] a, Comparator super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}このステップを実行すると2つのブランチが返されます.
まずcが空か否かを判断し,空であればsortメソッドを直接実行する.
そうでないと判断するuserRequestedのブール値.この値がTrueの場合はlegacyMergeSortソートアルゴリズムを実行し、そうでない場合はTimSortソートアルゴリズムを実行します.
まず最初にuserRequestedって何ですか???ソースを開けてみましょう
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}実際にはコードに内部クラスが定義されています.この中にはuserResuestという属性があります.この属性の値はsecurityパッケージのdoPrivilegedメソッドによって生成されます.この方法はnativeメソッドです.実はシステムの属性に基づいて古い集計ソート実装か新しいtimソート実装かを選択します.
次に、sortメソッド、legacyMergeSort()メソッド、およびTimSort.sort()法によるソースレベルの探究
3.1 sortメソッド
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}このsortと上記の違いは,2つのソートを呼び出すパラメータが異なり,実際にはこの2つのソートを呼び出すリロード方法である.
3.2 legacyMergeSort(Object[] a)
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}auxはaのオブジェクトコピーであり,aは実は前のlistが回転した配列である.mergeSortメソッドは,実は集計ソートアルゴリズムである()
private static void mergeSort(Object[] src, //
Object[] dest,//
int low, // 0
int high, // list
int off) { // ， ， off 。
int length = high - low;
// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) { // 7
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src // 7
int destLow = low;
int destHigh = high;
low += off; //off = 0 ;low = 0
high += off; //off = 0 ;high = list
int mid = (low + high) >>> 1; //list ， 8 4 7 3. ，
mergeSort(dest, src, low, mid, -off); // ， 7 ，
mergeSort(dest, src, mid, high, -off); // ，
// ， SRC DEST。 ， 。
// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { //
System.arraycopy(src, low, dest, destLow, length);
return;
}
// src dest，
// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) { //
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) //mid high low mid low mid
dest[i] = src[p++]; // src src mid ， dest src
else
dest[i] = src[q++]; // src src mid ， dest src
}
}最後のプログラムは、実は2つの値をループで1つのマージします.
例えば5 7 6 9 2 8 7 5 6 0というリストです.
最初のセグメント:5 7 6 9 2|8 7 5 6 0
2 5 6 7 9|0 5 6 7 8
次に各セグメントが7未満であるか否かを判断して最後のループを実行する
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)このステップはtrueに戻り、0を1位にします.
1回の類推でソート後のデータ再編成を行います.
これが集計ソートアルゴリズムです
3.3 ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
TimSortアルゴリズムは,並べ替えと挿入並べ替えに起源するハイブリッド並べ替えアルゴリズムであり,実際の世界の様々なデータにおいてより良い性能を得るために設計された.
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) // Remaining
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) { // 32, binarySort( )
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); // minRun , /2， minRun
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi); // ， ，
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) { // 32
int force = nRemaining <= minRun ? nRemaining : minRun; //
binarySort(a, lo, lo + force, lo + runLen);
runLen = force;
}
// merge，merge （ X，Y，Z ）：
//a) merge
//b) 2，If X<=Y， X Y merge
//b) >=3，If X<=Y+Z， X Y merge， X>Y+Z Y>Z
// 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;
}TimSortアルゴリズムは,昇順部分の遡及と降順部分の性能後退を低減するために,その昇順と降順の特徴に従って入力をパーティション化した.ソートの入力単位は、個々の数値ではなく、個々のブロック-パーティションです.各パーティションはrunと呼ばれます.これらのrunシーケンスに対して,runを1つずつ取り出してルールに従ってマージする.マージのたびに2つのrunが1つのrunにマージされます.マージの結果はスタックに保存されます.すべてのrunが消費されるまでマージし、スタック上の残りのrunを1つしか残っていないまでマージします.このとき,この残りのrunは順序付けの結果である.
ここでは、このソートに特化した例を共有します.
出典:https://blog.csdn.net/bruce_6/article/details/38299199
例
*注意*:プレゼンテーションの便宜上、TimSortのminRunを直接2に設定します.そうしないと、小さな配列でプレゼンテーションできません.の同時にMIN_MERGEも2(デフォルトは32)に変更され、binary sortへの直接のアクセスを回避します.
初期配列は[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14]=>連続的な降順または昇順シーケンス(2.2.1)を探すとともに,
countRunAndMakeAscending関数は昇順であることを保証する[1,5,7][2,6,8,10,12,4,3,9,11,13,15,16,14]=>インスタック(2.2.3)現在のスタックブロックは[3]
=>mergeループに入る(2.2.4)do not mergeスタックサイズが1のみのため
=>連続降順または昇順シーケンス(2.2.1)[1,5,7][2,6,8,10,12][4,3,9,11,13,15,16,14]を探す
=>インスタック(2.2.3)現在のスタックブロックは[3,5]
=>mergeサイクルに入る(2.2.4)merge runLen[0]<=runLen[11]gallopRight:run 1の最初の要素がrun 0のどの位置に挿入されるべきかを探します("2"が"1"を挿入すべきかを探した後)、その後、以前のrun 0の要素(いずれもrun 1の最初の要素より小さい)2)gallopLeftを無視することができます:run 0の最後の要素がrun 1のどの位置に挿入されるべきかを探します("7"は"8"の前に挿入すべきであり、その後run 1の要素(いずれもrun 0の最後の要素より大きい)を無視することができ、このようにソートする必要がある要素は[5,7][2,6]しか残っておらず、mergeLowが完了した後の結果:[1,2,5,6,7,8,12][4,3,9,11,13,15,16,14]
=>スタックに入る(2.2.3)現在のスタックブロックは[8]現在のmergeループを終了するスタック内のブロックは1のみであるため
=>連続する降順または昇順シーケンス(2.2.1)[1,2,5,6,7,8,10,12][3,4][9,11,13,15,16,14]=>インスタック(2.2.3)現在のスタックブロックサイズは[8,2]
=>mergeループに入る(2.2.4)do not merge runLen[0]>runLen[1]
=>連続降順または昇順シーケンス(2.2.1)[1,2,5,6,7,8,10,12][3,4][9,11,13,15,16]を探す[14]
=>インスタック(2.2.3)現在のスタックブロックは[8,2,5]
=>do not merege run 1とrun 2はrunLen[0]<=runLen[1]+runLen[2 merge run 2とrun 3を満たさないためrunLen[1]<=runLen[21]gallopRight:run 1とrun 2が順序付けされて完了したことを発見した結果:[1,2,5,6,7,8,10,12][3,4,9,11,13,15,16][14]
=>スタックイン(2.2.3)現在のスタックインのブロックサイズは[8,7]runLen[0]>runLen[1]のためmergeループを終了する
=>連続的な降順または昇順シーケンスを探す(2.2.1)最後には[14]という要素しか残っていない:[1,2,5,6,7,8,10,12][3,4,9,11,13,15,16][14]
=>インスタック(2.2.3)現在のインスタックのブロックサイズは[8,7,1]
=>mergeサイクルに入る(2.2.4)merge runLen[0]<=runLen[1]+runLen[2]runLen[2]>runLen[2]のため、run 1とrun 2を先にマージする.(そうでなければrun 0とrun 1を先にマージする)1)gallopRight&2)gallopLeftのようにソートする必要がある要素は[13,15][14]残り、mergeHighが完了した後の結果:[1,2,5,6,7,8,10,12][3,4,9,11,13,14,15,16]現在スタックに入っているブロックは[8,8]
=>継続merge runLen[0]<=runLen[11)gallopRight&2)gallopLeftのソートが必要な要素は[5,6,7,8,10,12][3,4,9,11]残っているため、mergeHighが完了した後の結果:[1,2,3,4,5,6,7,8,10,11,12,13,14,15,16]現在のスタックのブロックサイズは[16]
=>final mergeは不要です.現在のスタックサイズは1です.
=>終了