1、使用
成都創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比廉江網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式廉江網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋廉江地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。
排序
2、原理
事實(shí)上Collections.sort方法底層就是調(diào)用的array.sort方法，而且不論是Collections.sort或者是Arrays.sort方法，
跟蹤下源代碼吧，首先我們寫個(gè)demo
重慶分公司
重慶分公司
public static void main(String[] args) {
List strings = Arrays.asList("6", "1", "3", "1","2");
Collections.sort(strings);//sort方法在這里
for (String string : strings) {
System.out.println(string);
}
} 簡(jiǎn)單得不能再簡(jiǎn)單的方法了，讓我們一步步跟蹤
OK，往下面看，發(fā)現(xiàn)collections.sort方法調(diào)用的list.sort
然后跟蹤一下，list里面有個(gè)sort方法，但是list是一個(gè)接口，肯定是調(diào)用子類里面的實(shí)現(xiàn)，這里我們demo使用的是一個(gè)Arrays.asList方法，所以事實(shí)上我們的子類就是arraylist了。OK，看arraylist里面sort實(shí)現(xiàn)，選擇第一個(gè)，為什么不選擇第二個(gè)呢？（可以看二樓評(píng)論，解答得很正確，簡(jiǎn)單說就是用Arrays.sort創(chuàng)建的ArrayList對(duì)象）
OK，發(fā)現(xiàn)里面調(diào)用的Arrays.sort(a, c); a是list,c是一個(gè)比較器，我們來看一下這個(gè)方法
我們沒有寫比較器，所以用的第二項(xiàng)，LegacyMergeSort.userRequested這個(gè)bool值是什么呢？
跟蹤這個(gè)值，我們發(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)在默認(rèn)是關(guān)的
OK，我們走的是sort(a)這個(gè)方法，接著進(jìn)入這個(gè)
接著看我們重要的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就不用排了
// 當(dāng)數(shù)組大小小于MIN_MERGE(32)的時(shí)候，就用一個(gè)"mini-TimSort"的方法排序，jdk1.7新加
if (nRemaining < MIN_MERGE) {
//這個(gè)方法比較有意思，其實(shí)就是將我們最長(zhǎng)的遞減序列，找出來，然后倒過來
int initRunLen = countRunAndMakeAscending(a, lo, hi);
//長(zhǎng)度小于32的時(shí)候，是使用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，我們可以看到當(dāng)我們寫了比較器的時(shí)候就調(diào)用了TimSort.sort方法，源碼如下
staticvoid 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; }
和上面的sort方法是一樣的，其實(shí)也就是TimSort的源代碼
3、總結(jié)
不論是Collections.sort方法或者是Arrays.sort方法，底層實(shí)現(xiàn)都是TimSort實(shí)現(xiàn)的，這是jdk1.7新增的，以前是歸并排序。TimSort算法就是找到已經(jīng)排好序數(shù)據(jù)的子序列，然后對(duì)剩余部分排序，然后合并起來
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
