Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析
1、使用
排序
2、原理
事實上Collections.sort方法底層就是調(diào)用的array.sort方法,而且不論是Collections.sort或者是Arrays.sort方法,
跟蹤下源代碼吧,首先我們寫個demo
public static void main(String[] args) { List<String> strings = Arrays.asList("6", "1", "3", "1","2"); Collections.sort(strings);//sort方法在這里 for (String string : strings) { System.out.println(string); } }
簡單得不能再簡單的方法了,讓我們一步步跟蹤
OK,往下面看,發(fā)現(xiàn)collections.sort方法調(diào)用的list.sort
然后跟蹤一下,list里面有個sort方法,但是list是一個接口,肯定是調(diào)用子類里面的實現(xiàn),這里我們demo使用的是一個Arrays.asList方法,所以事實上我們的子類就是arraylist了。OK,看arraylist里面sort實現(xiàn),選擇第一個,為什么不選擇第二個呢?(可以看二樓評論,解答得很正確,簡單說就是用Arrays.sort創(chuàng)建的ArrayList對象)
OK,發(fā)現(xiàn)里面調(diào)用的Arrays.sort(a, c); a是list,c是一個比較器,我們來看一下這個方法
我們沒有寫比較器,所以用的第二項,LegacyMergeSort.userRequested這個bool值是什么呢?
跟蹤這個值,我們發(fā)現(xiàn)有這樣的一段定義:
> Old merge sort implementation can be selected (for
> compatibility with broken comparators) using a system property.
> Cannot be a static boolean in the enclosing class due to
> circular dependencies. To be removed in a future release.反正是一種老的歸并排序,不用管了現(xiàn)在默認是關的
OK,我們走的是sort(a)這個方法,接著進入這個
接著看我們重要的sort方法
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; // array的大小為0或者1就不用排了 // 當數(shù)組大小小于MIN_MERGE(32)的時候,就用一個"mini-TimSort"的方法排序,jdk1.7新加 if (nRemaining < MIN_MERGE) { //這個方法比較有意思,其實就是將我們最長的遞減序列,找出來,然后倒過來 int initRunLen = countRunAndMakeAscending(a, lo, hi); //長度小于32的時候,是使用binarySort的 binarySort(a, lo, hi, lo + initRunLen); return; } //先掃描一次array,找到已經(jīng)排好的序列,然后再用剛才的mini-TimSort,然后合并,這就是TimSort的核心思想 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; }
回到5,我們可以看到當我們寫了比較器的時候就調(diào)用了TimSort.sort方法
,源碼如下
static <T> 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<T> 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; }
和上面的sort方法是一樣的,其實也就是TimSort的源代碼
3、總結
不論是Collections.sort方法或者是Arrays.sort方法,底層實現(xiàn)都是TimSort實現(xiàn)的,這是jdk1.7新增的,以前是歸并排序。TimSort算法就是找到已經(jīng)排好序數(shù)據(jù)的子序列,然后對剩余部分排序,然后合并起來
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
Spring Security使用多種加密方式進行密碼校驗的代碼示例
在Web應用中,密碼的安全存儲和驗證是至關重要的,本文將通過一個具體的代碼示例,介紹和總結如何在Spring Security中使用多種加密方式進行密碼校驗,文中通過代碼講解得非常詳細,需要的朋友可以參考下2024-06-06SpringBoot集成SFTP客戶端實現(xiàn)文件上傳下載實例
這篇文章主要為大家介紹了SpringBoot集成SFTP客戶端實現(xiàn)文件上傳下載實例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-08-08SpringCloud zookeeper作為注冊中心使用介紹
ZooKeeper由雅虎研究院開發(fā),是Google Chubby的開源實現(xiàn),后來托管到Apache,于2010年11月正式成為Apache的頂級項目。ZooKeeper是一個經(jīng)典的分布式數(shù)據(jù)一致性解決方案,致力于為分布式應用提供一個高性能、高可用,且具有嚴格順序訪問控制能力的分布式協(xié)調(diào)服務2022-11-11SpringBoot使用Nacos動態(tài)配置數(shù)據(jù)源的方法
這篇文章主要介紹了SpringBoot使用Nacos動態(tài)配置數(shù)據(jù)源的方法,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-03-03IDEA報錯"Cannot?resolve?symbol"問題的解決辦法
早上來了,打開idea發(fā)現(xiàn)注解等都變紅報錯can’t resolvesymbol,由于這個錯之前也報過,所以記錄一下,這篇文章主要給大家介紹了關于IDEA報錯"Cannot?resolve?symbol"問題的解決辦法,需要的朋友可以參考下2023-11-11SpringBoot2實現(xiàn)MessageQueue消息隊列
本文主要介紹了 SpringBoot2實現(xiàn)MessageQueue消息隊列,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-04-04