上一篇介紹了最基本的資料儲存結構 -- 陣列，既然提到陣列就難免要說一下排序了，由於排序是一個比較重要的部分，在一些面試中問到演算法基礎也經常會問到，而且本篇會介紹8種常見的排序演算法，篇幅較大，所以將排序單獨分離出來作為一篇文章。

交換陣列元素

在介紹排序演算法前，先寫一個交換陣列中任意兩個元素的方法，供下面各排序演算法進行呼叫

還有一個便於我們檢視結果的列印方法，雖然沒有什麼技術含量，不過還是順便寫出來吧：

下面正式開始介紹排序演算法：

8種常見排序演算法：1. 簡單選擇排序

每一趟從待排序的資料元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完，它需要經過n-1趟比較。程式碼實現如下：

2. 氣泡排序

依次比較兩個相鄰的元素，將值大的元素交換至右端。程式碼實現如下：

3. 直接插入排序

將待排序的資料元素按其關鍵字值的大小插入到前面的有序序列中。程式碼如下：

3.2. 折半插入排序

又叫二分插入排序, 即尋找插入位置時，用二分法尋找

4. 歸併排序該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。將兩個有序表合併成一個有序表，稱為二路歸併。優點：效率較高,時間複雜度為O(NlogN), 而冒泡,插入,選擇的時間複雜度都是O(NN)缺點：需要在儲存器中有一個大小等於被排序陣列的中介陣列,就是用空間換時間核心：歸併兩個有序陣列

程式碼實現如下：

5. 希爾排序:又叫最小增量排序，基於插入排序，時間複雜度O(N*(logN)2)，效率不算太高,適於中等大小陣列，但是非常容易實現，程式碼既簡單又短。原理：透過加大插入排序中元素之間的間隔，並在這些有間隔的元素中進行插入排序，從而使資料項大跨度地移動，當這些資料項排過一趟序之後，希爾排序演算法減小資料項的間隔再進行排序，依次進行下去，進行這些排序時的資料項之間的間隔被稱為增量，習慣上用字母h來表示這個增量。Shell排序是不穩定的，它的空間開銷是O(1)，時間開銷估計在O(N3/2)~O(N7/6)之間Shell原稿中建議初始間距為N/2,但這被證明不是最好的數列,會使時間複雜度降低到O(N*N)後又衍生出N/2.2的最佳化，其中的關鍵點在於間隔數列元素的互質性,這使得每一趟排序更有可能保持前一趟排序已排好的效果

程式碼實現如下：

6. 快速排序:劃分：快速排序的根本機制, 把資料分為兩組,使所有關鍵字大於特定值的資料項在一組,小於的在另一組, 如全班學生的考試成績以及格線60劃分。時間複雜度: O(N*logN)原理：把一個數組分為兩個子陣列(劃分), 然後遞迴的呼叫自身,為每個子陣列進行快速排序。效率: 影響效率的關鍵點在於樞紐的選擇(即上面劃分中的關鍵字,例子中的60分)，應儘量保證兩個子陣列的大小接近通常來說關鍵字可以選擇任意一項資料,一般選擇頭尾arr[0]或arr[arr.length-1]，但是這樣做演算法的效能是不穩定的，因為待排序的陣列可能是有序的，會使時間複雜度降到O(N*N)理想中的樞紐應為待排序陣列的中值資料項, 但是選取中間值比較麻煩,所以一個折中的辦法就是'三項資料取中'劃分,即陣列頭,尾,中,三個資料項的中值作為樞紐, 這樣既簡單又可以避免選擇到最大或最小值作為樞紐的情況。

1. 常規實現：以起始(或結尾)索引為分界點

2. 三項資料取中實現快速排序

7. 基數排序基數:一個數字系統的基,10是十進位制系統的基數，2是二進位制系統的基數把數值拆分2位數字位,對每一位進行排序缺點:以空間換時間

程式碼如下：

8. 堆排序

程式碼如下：

其中VectorHeap是一個自己寫到堆的實現類，關於堆到後面介紹到堆時再詳細介紹，下面先給出其具體實現類的程式碼

其中的Node節點類實現如下：