[TOC]  ## 冒泡排序 冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。  ## 選擇排序 選擇排序(Selection-sort)是一種簡單直觀的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。  ## 插入排序 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。  ## 快速排序 1. 從數列中挑出一個元素，稱為 “基準”（pivot）； 2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作； 3. 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。 ``` public class QuickSort { public static void quickSort(int[] arr,int low,int high){ int i,j,temp,t; if(low>high){ return; } i=low; j=high; //temp就是基準位 temp = arr[low]; while (i<j) { //先看右邊，依次往左遞減 while (temp<=arr[j]&&i<j) { j--; } //再看左邊，依次往右遞增 while (temp>=arr[i]&&i<j) { i++; } //如果滿足條件則交換 if (i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后將基準為與i和j相等位置的數字交換 arr[low] = arr[i]; arr[i] = temp; //遞歸調用左半數組 quickSort(arr, low, j-1); //遞歸調用右半數組 quickSort(arr, j+1, high); } public static void main(String[] args){ int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19}; quickSort(arr, 0, arr.length-1); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } } ``` ## 歸并排序 1. 把長度為n的輸入序列分成兩個長度為n/2的子序列； 2. 對這兩個子序列分別采用歸并排序； 3. 將兩個排序好的子序列合并成一個最終的排序序列。  ## 堆排序 1. 將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆 2. 將堆頂元素R\[1\]與最后一個元素R\[n\]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn) 3. 對當前無序區(R1,R2,……Rn-1)調整為新堆，然后再次將R\[1\]與無序區最后一個元素交換 4. 不斷重復此過程直到有序區的元素個數為n-1，則整個排序過程完成。   ## java API 排序算法 Arrays.sort -> DualPivotQuicksort TimSort算法和雙指針快速排序。 首先強調一下，這是個**穩定**的排序算法 看過代碼之后覺得這個算法沒有想象的那么難。邏輯很清晰，整個算法最大的特點就是充分利用數組中已經存在順序。在歸并的過程中有一個 Galloping Mode(翻譯過來可以叫 飛奔模式)，這是整個排序算法中最不尋常的地方。簡單的理解就是，歸并過程中有兩個數列，比較的時候，有個數列連續有{MIN\_GALLOP}個元素都比另一個數列的第一個元素小，那就應該數一下后面到底還有多少個元素比另一個數列的第一個元素小。數完之后一次copy過去，減少copy的次數。MIN\_GALLOP還是一個可以動態調整的值，這應該是統計優化的結果。 ## 參考資料 [讀 Java TimSort算法 源碼 筆記](https://www.jianshu.com/p/10aa41b780f2) [DualPivotQuickSort 雙軸快速排序 源碼 筆記](https://www.jianshu.com/p/6d26d525bb96) [十大經典排序算法最強總結](https://blog.csdn.net/hellozhxy/article/details/79911867) [排序六 堆排序](https://www.cnblogs.com/jingmoxukong/p/4303826.html)