1.快速排序
快速排序每趟選擇一個基準元素延欠，用基準元素將序列劃分成兩部分陌兑，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面由捎，這一趟過程稱為分區(qū)（partition）操作兔综。每一趟分區(qū)操作的目的就是把這趟的基準元素擺到最終位置。
遞歸地對基準元素左邊的序列和右邊的序列分別調(diào)用分區(qū)操作，則當序列的大小是零或者一時整個序列排序完成软驰，采用的是“分治”的策略涧窒。
思路總結：
（1）先從序列中取出一個數(shù)作為基準數(shù)。
（2）分區(qū)過程：將比基準數(shù)大的數(shù)全部放到它的右邊锭亏，小于或等于它的數(shù)全部放到它的左邊纠吴。
（3）對左右序列重復步驟（2），直到各序列數(shù)只有一個或零個
為了便于大家理解“分區(qū)”操作慧瘤，將快排寫成兩個函數(shù)戴已，大家也可以合成一個函數(shù)寫，參考代碼如下：
//分區(qū)操作
public int partition(int a[],int left,int right){
int l = left,r = right,key = a[left];
if(left<right){
while(l<r){//結束條件為左指針與右指針匯合
while(l<r&&key<=a[r]){//從右向左遍歷數(shù)組锅减，找到第一個小于key的值
r--;
}
if(l<r){//右邊小于key的值與key的位置互換
a[l++] = a[r];
}
//左右方向互換
while(l<r&&key>a[l]){//從左向右遍歷糖儡，找到第一個大于key的值
l++;
}
if(l<r){//左邊大于key的值與key互換
a[r--] = a[l];
}
}
a[l] = key;//key放到數(shù)組最終位置
}
return l;
}
上面的分區(qū)操作的代碼可以簡單概括為“挖坑填數(shù)”，即每次partiton將序列最左邊的數(shù)選為基準元素key怔匣，將key挖出握联，從右向左開始遍歷，讓序列中的數(shù)與基準元素key值進行比較每瞒，若右邊有比基準值小的數(shù)金闽，則將該數(shù)“挖”出來，“填”入坑中独泞，被挖的數(shù)成為新的坑呐矾，每“挖、填”一次數(shù)懦砂，改變一次序列的遍歷方向蜒犯，直到序列遍歷完成為止，將key（基準元素）填入最終結束的位置荞膘，也就確定了基準元素最終在序列中的位置罚随。
//遞歸調(diào)用
public void quickSort(int a[],int left,int right){
if(left<right){
int t = partition(a, left, right);
quickSort(a, left, t-1);//左邊的數(shù)組快排
quickSort(a, t+1, right);//右邊的數(shù)組快排
}
}
排序過程如下所示：
初始狀態(tài)： a[0] a[1] a[2] a[3] a[4] a[5]
初始值： ５ ∮鹱省６ √云小４ ３ ⊥郎１ 〕备摹２
第一趟排序過程：key = 5 a[0]為初始坑所在位置（用[ ]標識坑的位置）
［５］ 「古６ 』阍凇４ ３ ≡啻稹１ ２ (右->左糕殉，l=0,r=5亩鬼，a[r]小于key)
２ ６ “⒌４ ■ǚ妗３ １ ∠劢唷［２］ (交換玷过，a[5]值填坑，a[5]變新坑)
》倮取２ ６ ∫逼ァ４ ３ ∨匚痢１ 〗腊［２］ (左->右，l=1,r=5袒餐，a[l]大于key)
》捎肌２ ［６］ 【难邸４ ∥蚤堋３ １ ６ (交換焰宣，a[1]值填坑霉囚，a[1]變新坑)
２ ∝盎［６］ ∮蕖４ ３ １ ∩了簟６ (右->左盅粪，l=1,r=4，a[r]小于key)
∏睦佟２ ∑惫恕１ ４ 》鳌３ 〉旖尽［１］ ６ (交換番刊，a[4]值填坑含鳞，a[4]變新坑)
２ ∧焓唷１ ４ ∶裆埂３ ［１］ 〕荨６ (左->右潜必，l=2,r=4)
２ ∥值１ 〈殴觥４ ３ ［１］ ∠怼６ (左->右垂攘，l=3,r=4)
２ ∮偃小１ ∩顾４ ３ ∫菁帧［５］ ≡山觥６ (l=r=4,key填a[l])
２ ÷燎帧１ ∽粕恕４ ３ ５ ∵湎省６ (找到５的最終位置)
第二趟： 『摹１ ２ ４ ∨北３ 5 6∮敝丁（找到２的最終位置）
第三趟： １ ÷「摇２ 》⒚蟆３ ４ 5 6 （找到４的最終位置）
２.歸并排序
歸并排序先遞歸分解序列拂蝎，一分為二進行分組穴墅，直到分解到分組只有一個元素為止，認為其有序温自，再將有序分組兩兩合并玄货，最后使整個序列有序。（歸并可以簡單理解為：遞歸分解+兩兩合并）
將兩個有序序列合并的思路：
（1）比較兩個序列中第一個數(shù)悼泌，取出較小者松捉，對應取數(shù)序列取數(shù)位置后移一位，即下一個數(shù)變?yōu)榈谝粋€數(shù)馆里。
（2）重復步驟（3）隘世，如果有序列值全部取完可柿，那直接將另一個序列的數(shù)據(jù)依次取出即可
（3）取出的數(shù)依次存入一個新的序列，這個新的序列即為這兩個有序序列合并而成的新的有序序列
分解的實現(xiàn)比較簡單丙者，通過改變傳入數(shù)組下標复斥，直接遞歸調(diào)用即可，為了便于大家理解歸并排序中遞歸與合并的概念械媒，將歸并寫成兩個函數(shù)目锭，參考代碼如下：
//遞歸分解操作
public void mergeSort(int a[],int begin,int end){//傳入的begin、end均為待排序數(shù)組的下標值
if(begin<end){
int mid = (begin+end)/2;
mergeSort(a, begin, mid);
mergeSort(a, mid+1, end);
merge(a, begin, end);
}
}
對于數(shù)組進行分解纷捞，例如若某個數(shù)組長度為8痢虹，下標為0~7，則mid = (0+7)/2=3主儡，可將數(shù)組分成兩個子數(shù)組：下標為[03]的數(shù)組和下標為[47]的數(shù)組奖唯。而對于下標[03]的數(shù)組，其mid=(0+3)/2=1缀辩，又可將其分為下標為[01]的數(shù)組和下標為[2~3]的數(shù)組臭埋。依此類推，直到分解成的數(shù)組只有一個元素為止臀玄，認為其有序瓢阴。
//合并操作
public void merge(int a[],int begin,int end){
int mid = (begin + end)/2;//將傳進來原數(shù)組對應下標的子數(shù)組根據(jù)mid分解
int i = begin, j = mid + 1; //分解成兩個數(shù)組:[begin~mid]、[mid+1~end]
int k = 0;
int temp[] = new int[end+1];//申請額外空間來暫存排序后的新的有序數(shù)組
while (i <= mid && j <= end) //依次比較分解后兩個數(shù)組內(nèi)的數(shù)健无，直至其中一個數(shù)組到末尾
{
if (a[i] <= a[j]) //將較小值放入臨時數(shù)組的前面
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= mid) //若數(shù)組[begin~mid]中還有數(shù)沒取完荣恐，則將未取完的數(shù)全部追加到臨時數(shù)組后面
temp[k++] = a[i++];
while (j <= end) //若數(shù)組[mid+1~end]中還有數(shù)沒取完，則將未取完的數(shù)全部追加到臨時數(shù)組后面
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[begin+i] = temp[i]; //將合并后有序的臨時數(shù)組中的數(shù)依次賦值到原來待合并的數(shù)組累贤，完成該次合并
}
排序過程如下所示：
初始狀態(tài)：a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
初始值：〉隆６ ５ 【矢唷３ ∨鸨弧１ ８ ∩酢７ ∪铝颉２ ４
６ ５ ∈加恪３ ∽械А１ ８ ∫角濉７ ∑鹉骸２ ４（0~1合并）
』崂印５ 「号场６ ３ １ ⊥厕唷８ ７ ≈嚼鳌２ ”好４（2~3合并）
５ ６ １ ３ ８ 〔须纭７ ２ ∑兜肌４（0~3合并）
∨酌ā１ ３ 『⒌啤５ 」虢稹６ ８ ７ ２ 》宓怠４（4~5合并）
“芷ァ１ ３ 〖パ病５ ∠颇丁６ ７ 』肚辍８ ２ ４（6~7合并）
〔酃鳌１ ３ √俊５ ×镀摺６ ７ ８ ２ ４（4~7合并）
１ ３ ５ ６ ２ ４ ７ ８（0~7合并）
１ 〔汲帧２ ⊥阕尽３ ４ √馀５ “锤怠６ ７ ≤轿８（排序結果）
