Collection和Collections區別
java.util.Collection 是一個集合介面，它提供了對集合物件進行基本操作的通用介面方法， java.util.Collections 是針對集合類的一個幫助類，他提供一系列靜態方法實作對各種集合的搜索、排序、執行緒安全等操作， 然后還有混排（shuffle）、反轉（reverse）、替換所有的元素（fill）、拷貝（copy）、回傳Collection中最小元素（min）、回傳Collection中最大元素（max）、回傳指定源串列中最后一次出現指定目標串列的起始位置（ lastIndexOfSubList ）、回傳指定源串列中第一次出現指定目標串列的起始位置（ IndexOfSubList ）、根據指定的距離回圈移動指定串列中的元素（rotate）; 事實上Collections.sort方法底層就是呼叫的Arrays.sort方法Collections 中的sort() 方法如下：
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
其中呼叫的list.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);
}
}
其中呼叫的Arrays.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);
}
}
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
legacyMergeSort (a,c)：歸并排序
TimSort.sort() ： Timsort 排序，結合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序演算法
Timsort的核心程序:
TimSort 演算法為了減少對升序部分的回溯和對降序部分的性能倒退，將輸入按其升序和降序特點進行了磁區，排序的輸入的單位不是一個個單獨的數字，而是一個個的塊-磁區，其中每一個磁區叫一個run，針對這些 run 序列，每次拿一個 run 出來按規則進行合并，每次合并會將兩個 run合并成一個 run，合并的結果保存到堆疊中，合并直到消耗掉所有的 run，這時將堆疊上剩余的 run合并到只剩一個 run 為止，這時這個僅剩的run 便是排好序的結果，
綜上述程序，Timsort演算法的程序包括 :
1、如何陣列長度小于某個值，直接用二分插入排序演算法
2、找到各個run，并入堆疊
3、按規則合并run
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/147227.html
標籤：Java
上一篇：Android反編譯apk修改版本號重新打包簽名詳細教程（超詳細）
下一篇：Cloneable 介面實作原理