常見排序算法比較
參考資料：各種排序算法比較
參考資料：快速排序算法
必須知道的八大種排序算法【java實現(xiàn)】（一） 冒泡排序挑随、快速排序?（這篇文章中存在部分錯誤折联，但是代碼示例較為完備肋坚，可以當(dāng)著示例來看）
算法復(fù)雜度和算法穩(wěn)定性的理解
時間復(fù)雜度：元素進(jìn)行比較和移動的次數(shù)宋列；
空間復(fù)雜度：算法執(zhí)行過程中，需要的輔助內(nèi)存情況惭嚣；
算法穩(wěn)定性：對于同值元素位置的改變情況決定姑廉，如果不改變缺亮，則屬于穩(wěn)定性好的算法，否則為不穩(wěn)定的算法桥言。
對冒泡排序算法最好情況下時間復(fù)雜度為O(n)的理解萌踱，及時間復(fù)雜度的具體算法：冒泡排序最佳情況的時間復(fù)雜度，為什么是O(n)
下面是冒泡排序算法的示例：
示例代碼
參考git倉庫：
關(guān)鍵點
各種排序算法在：時間算法復(fù)雜度限书、空間復(fù)雜度虫蝶、算法穩(wěn)定性、算法難易度上各有所長倦西，需要根據(jù)場景來定能真；比如對大部分有序的場景，采用插入排序/冒泡排序算法扰柠；對于數(shù)據(jù)量大時粉铐，對時間敏感的情況下，使用歸并排序/快排算法合適卤档；對于對內(nèi)存敏感的場景蝙泼，則不宜選用歸并排序/快排算法，可采用shell排序劝枣。
歸并排序算法時間復(fù)雜度上穩(wěn)定汤踏，為O（nlog2n）织鲸，但是空間復(fù)雜度較高，通常為O(n)溪胶；如果希望降低空間復(fù)雜度可以搂擦，采用原地歸并算法，可以將空間復(fù)雜度降低至O(nlogn),但是會損壞時間復(fù)雜度哗脖，所以需要在時間復(fù)雜度和空間復(fù)雜度上進(jìn)行折中瀑踢，根據(jù)具體應(yīng)用場景選擇；
快排算法才避，不穩(wěn)定橱夭，平均時間復(fù)雜度為O（nlog2n），空間復(fù)雜度為O(log2n) ~ O(n)桑逝，當(dāng)數(shù)據(jù)量大時優(yōu)勢明顯棘劣；當(dāng)數(shù)據(jù)量小時，通常采用插入排序算法肢娘。
jdk中的ArrayList.sort（）方法
jdk1.6及其以前呈础，使用歸并排序算法；
jdk1.7橱健、1.8 默認(rèn)情況下使用TimSort，除非用戶顯式指定使用老式的歸并排序算法LegacyMergeSort時沙廉。
TimSort 綜合使用二分查找插入算法和歸并排序算法拘荡，以求性能上達(dá)到最佳。代碼分析參考：TimSort in Java 7
jdk中的sort方法體現(xiàn)了如下思路：
1撬陵、依據(jù)待排序數(shù)組的情況珊皿，選擇不同的排序算法；比如：當(dāng)待排序數(shù)組的大小小于設(shè)定值32時巨税，則直接使用二分查找插入算法蟋定，否則使用真正的TimSort排序。
2草添、TimSort排序的高明之處在于：特殊處理已排序的數(shù)組內(nèi)容驶兜，減小算法復(fù)雜度；分塊處理待排序數(shù)組远寸，確保每個元素最多移動的次數(shù)抄淑，不至于因為數(shù)組大小N增大，算法復(fù)雜度越來越大驰后；對塊進(jìn)行歸并處理肆资。
jdk中的Arrays.sort（）方法
采用DualPivotQuicksort 雙軸快速排序算法。算法步驟：
1.對于很小的數(shù)組（長度小于27）灶芝，會使用插入排序郑原。
2.選擇兩個點P1,P2作為軸心唉韭，比如我們可以使用第一個元素和最后一個元素。
3.P1必須比P2要小犯犁，否則將這兩個元素交換属愤，現(xiàn)在將整個數(shù)組分為四部分：
（1）第一部分：比P1小的元素。
（2）第二部分：比P1大但是比P2小的元素栖秕。
（3）第三部分：比P2大的元素春塌。
（4）第四部分：尚未比較的部分。
在開始比較前簇捍，除了軸點只壳，其余元素幾乎都在第四部分，直到比較完之后第四部分沒有元素暑塑。
4.從第四部分選出一個元素a[K]吼句，與兩個軸心比較，然后放到第一二三部分中的一個事格。
5.移動L惕艳，K，G指向驹愚。
6.重復(fù) 4 5 步远搪，直到第四部分沒有元素。
7.將P1與第一部分的最后一個元素交換逢捺。將P2與第三部分的第一個元素交換谁鳍。
8.遞歸的將第一二三部分排序。
