在 Java常見排序基礎 - 上 中主要介紹了冒泡排序、選擇排序、插入排序三種基礎排序，本篇文章主要介紹的是 快速排序、歸并排序。
快速排序：
首先看下什麼是快速排序，快速排序（Quicksort）是對冒泡排序的一種改進。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以
遞歸進行，以此達到整個資料變成有序序列。以上概念來自百度百科。
對于 “
通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小”，簡單的了解可以這樣的：在數組中找一個支點 ( 支點可以是數組中的任意位置，但是這個支點一般是數組的中心位置 )，經過一趟排序後，支點左邊的數都要比支點小，支點右邊的數都要比支點大。
假設現在有這樣一個數組：int arr[ ] = { 1,4,5,62,2,7,8,6,9,14 };
經過一趟排序之後，如果我選擇數組中間的數作為支點：7(任意的)，那麼第一趟排序後的結果是這樣的：{1,4,5,6,2,7,8,62,9,14}，那麼，1,4,5,6,2,7 則是第一趟排序的左邊，7,8,62,9,14則是第一趟排序的右邊。既然現在确定好了第一趟排序的結果，那麼現在隻需要對第一趟排序的左邊在尋找一個支點，繼續對這裡進行邏輯判斷排序、以此類推，這樣就最終實作了
支點左邊的數比支點小，支點右邊的數比支點大前面說到，快速排序整個排序過程都可以
進行，但是構成遞歸需必須具備兩個條件：首先，子問題須與原始問題為同樣的事，且更為簡單（這裡的意思就是找支點 、對支點左右側進行邏輯判斷）；其次不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
那麼下面我們就一步步的完成快速排序：
首先，我們定義一個數組，假設它的支點是數組的中間，那麼計算數組的中間值隻需要知道數組最後一個索引即可（因為第一個索引是0），于是，我們就有了以下代碼：
快速排序 - 1
既然我們知道了數組的支點，就可以對其進行判斷了，判斷的步驟簡單點了解 就是 arr[支點]與arr[索引]的具體大小判斷，由于這裡局部變量定義的left與right，分别是數組的最小索引以及數組的最大索引，也就是arr[0]和arr[ arrLength - 1]。是以，為了讓快速排序進行判斷的話 隻需要數組最小索引不斷累加、最大索引不斷累減、依次判斷。隻要 累加之後的最小索引和累減之後的最大索引 次數不一緻即可一直讓其在内部判斷。那麼什麼時候讓最小索引不斷累加，什麼時候讓最大索引不斷累減？理論上來說就是支點左邊的數值比支點小，即可讓其自增；支點右側的數值比支點大，則讓其自減。是以，最後可以這樣寫：
快速排序
值得注意的是，快速排序是一種不穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時産生變動。關于快速排序的内容就介紹到這裡。
歸并排序：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；
即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序過程如下：比較 a [ i ] 和 b [ j ] 的大小，若 a [ i ] ≤ b [ j ]，則将第一個有序表中的元素 a [ i ] 複制到 r [ k ] 中，并令 i 和 k 分别加上1；否則将第二個有序表中的元素 b [ j ] 複制到r [ k ]中，并令j和k分别加上1，如此循環下去，直到其中一個有序表取完，然後再将另一個有序表中剩餘的元素複制到r中從下标k到下标t的單元。歸并排序的算法我們通常用遞歸實作，先把待排序區間 [ s,t ] 以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸并操作合并成有序的區間[ s,t ]。
歸并操作的工作原理如下：第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列
第二步：設定兩個指針，最初位置分别為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重複步驟3直到某一指針超出序列尾
将另一序列剩下的所有元素直接複制到合并序列尾
歸并排序的演算過程：假設現在有兩個已排好順序的數組：
int [ ] arr1 = {2, 7, 8} 、int [ ] arr2 = {1, 4, 9}還有一個大數組來裝載它們
int [ ] arr = new int [6] ；步驟一：
那麼，首先将兩個數組的值進行比較，
誰的值比較小，誰就放入大數組！比較步驟：拿出arr1[0]和arr2[0]進行比較，顯然是arr2[0]比較小，是以将arr2[0]放入大數組中，
同時arr2指針往後一格（也就是 +1，累加） ，是以，現在目前為止arr = {1}
步驟二：
接着，拿arr1 [0] 和arr2 [1] 進行比較，arr1[0]較小，将arr1[0]放入大數組中，
同時arr1指針往後一格是以，現在目前為止arr = {1,2}
步驟三：
然後，拿arr1[1] 和arr2[1] 進行比較，顯然是arr2[1] 比較小，将arr2[1] 放入大數組中，
同時arr2指針往後一格是以，目前arr = {1,2,4}
…以此類推…
到最後，我們會将兩個已排好序的數組變成一個已排好序的數組，也就是 arr = {1,2,4,7,8,9}；至此，整個演算過程結束。
可能你會說，既然歸并排序的前提是需要兩個已經排好順序的數組，但是一般沒有兩個已經排好順序的數組給我們，因為排序的本質就是解決錯綜複雜的大小關系，那這個算法是不是有點本末倒置的剛？
其實不是，下面我們繼續分析。假設現在有這樣一個數組：
int [ ] arr = {2, 7, 8, 1, 4, 9} ;如果要對此數組做歸并排序，首先就可以用arr [3]，也就是元素為1的那個地方分開。然後用一個指針L指向arr[0]，一個指針M指向arr[3]，用一個指針R指向arr[5](數組最後一位)。有了指針的幫助，我們就可以将這個數組切割成是兩個有序的數組了（操作的方式就可以和上面一樣了）。但實際開發中中，數組一般是順序錯亂的，類似這樣一個數組：int [ ] arrays = { 9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8 } ；如果遇到這種情況我們該如何用歸并排序去思考問題？
我們可以這樣想，首先将 int[ ] arr = {2, 7, 8, 1, 4, 9} 這個數組根據索引分隔成每一份，arr[0]它是一個有序的"數組",arr[1]它也是一個有序的"數組"，接着利用指針(L,M,R)又可以像操作兩個數組一樣進行排序。最終合成{2,7}…….再不斷拆分合并，是以最後又回到了我們的arr = {1,2,4,7,8,9}。是以，歸并排序可以排序雜亂無章的數組。
将一個大問題分成很多個小問題進行解決，最後重新組合起來，這種思想一般稱為：分治法，很明顯，歸并排序也可以借鑒使用這種思想去操作。
* 合并數組
* @param arrays
* @param L 指向數組第一個元素
* @param M 指向數組分隔的元素
* @param R 指向數組最後的元素
public static void merge(int[] arrays, int L, int M, int R) {
//左邊的數組的大小 == 也就是中間的索引減去最小索引
int [ ] leftArray = new int[M - L];
//右邊的數組大小 == 數組最大索引減去中間的索引 還要+1
int [ ] rightArray = new int[R - M + 1];
//往這兩個數組填充資料
for (int i = L; i < M; i++) {
leftArray[i - L] = arrays[i];
}
for (int i = M; i <= R; i++) {
rightArray[i - M] = arrays[i];
int i = 0, j = 0;
// arrays數組的第一個元素
int k = L;
//比較這兩個數組的值，哪個小，就往數組上放
while (i < leftArray.length && j < rightArray.length) {
//誰比較小，誰将元素放入大數組中,移動指針，繼續比較下一個
if (leftArray[i] < rightArray[j]) {
arrays[k] = leftArray[i];
i++;
k++;
} else {
arrays[k] = rightArray[j];
j++;
}
}
//如果左邊的數組還沒比較完，右邊的數都已經完了，那麼将左邊的數抄到大數組中(剩下的都是大數字)
while (i < leftArray.length) {
arrays[k] = leftArray[i];
i++;
k++;
//如果右邊的數組還沒比較完，左邊的數都已經完了，那麼将右邊的數抄到大數組中(剩下的都是大數字)
while ( j < rightArray.length ) {
arrays[k] = rightArray[j]；
j++;
}
以上代碼是合并的代碼，下面是歸并排序的參考代碼：
歸并排序
最後是測試代碼：
測試代碼
另外：歸并排序是一種穩定的算法。
如果這篇文章對你有幫助，希望各位看官留下寶貴的star，謝謝。
Ps:著作權歸作者所有,轉載請注明作者, 商業轉載請聯系作者獲得授權，非商業轉載請注明出處(開頭或結尾請添加轉載出處，添加原文url位址),文章請勿濫用,也希望大家尊重筆者的勞動成果。