Collection和Collections區(qū)別
java.util.Collection 是一個(gè)集合接口。它提供了對集合對象進(jìn)行基本操作的通用接口方法。
java.util.Collections 是針對集合類的一個(gè)幫助類囚灼，他提供一系列靜態(tài)方法實(shí)現(xiàn)對各種集合的搜索坷澡、排序搞挣、線程安全等操作。 然后還有混排（shuffle）爬立、反轉(zhuǎn)（reverse）、替換所有的元素（fill）万哪、拷貝（copy）侠驯、返回Collection中最小元素（min）抡秆、返回Collection中最大元素（max）、返回指定源列表中最后一次出現(xiàn)指定目標(biāo)列表的起始位置（ lastIndexOfSubList ）吟策、返回指定源列表中第一次出現(xiàn)指定目標(biāo)列表的起始位置（ IndexOfSubList ）儒士、根據(jù)指定的距離循環(huán)移動指定列表中的元素（rotate）;
事實(shí)上Collections.sort方法底層就是調(diào)用的Arrays.sort方法
Collections 中的sort() 方法如下：
public static <T extends Comparable<? super T>> void sort(List<T> list) {
? ? ? list.sort(null);
}
其中調(diào)用的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);
? ? }
}
其中調(diào)用的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 排序，結(jié)合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法
Timsort的核心過程:
TimSort 算法為了減少對升序部分的回溯和對降序部分的性能倒退檩坚，將輸入按其升序和降序特點(diǎn)進(jìn)行了分區(qū)着撩。排序的輸入的單位不是一個(gè)個(gè)單獨(dú)的數(shù)字，而是一個(gè)個(gè)的塊-分區(qū)匾委。其中每一個(gè)分區(qū)叫一個(gè)run拖叙。針對這些 run 序列，每次拿一個(gè) run 出來按規(guī)則進(jìn)行合并赂乐。每次合并會將兩個(gè) run合并成一個(gè) run薯鳍。合并的結(jié)果保存到棧中。合并直到消耗掉所有的 run沪猴，這時(shí)將棧上剩余的 run合并到只剩一個(gè) run 為止辐啄。這時(shí)這個(gè)僅剩的run 便是排好序的結(jié)果。
深圳網(wǎng)站建設(shè)www.sz886.com
