1.快速排序

快速排序每趟選擇一個基準(zhǔn)元素，用基準(zhǔn)元素將序列劃分成兩部分，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面，這一趟過程稱為分區(qū)（partition）操作。每一趟分區(qū)操作的目的就是把這趟的基準(zhǔn)元素?cái)[到最終位置。　　遞歸地對基準(zhǔn)元素左邊的序列和右邊的序列分別調(diào)用分區(qū)操作，則當(dāng)序列的大小是零或者一時整個序列排序完成，采用的是“分治”的策略。

思路總結(jié)：

（1）先從序列中取出一個數(shù)作為基準(zhǔn)數(shù)。
（2）分區(qū)過程：將比基準(zhǔn)數(shù)大的數(shù)全部放到它的右邊，小于或等于它的數(shù)全部放到它的左邊。
（3）對左右序列重復(fù)步驟（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){//結(jié)束條件為左指針與右指針匯合
                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ù)選為基準(zhǔn)元素key，將key挖出，從右向左開始遍歷，讓序列中的數(shù)與基準(zhǔn)元素key值進(jìn)行比較，若右邊有比基準(zhǔn)值小的數(shù)，則將該數(shù)“挖”出來，“填”入坑中，被挖的數(shù)成為新的坑，每“挖、填”一次數(shù)，改變一次序列的遍歷方向，直到序列遍歷完成為止，將key（基準(zhǔn)元素）填入最終結(jié)束的位置，也就確定了基準(zhǔn)元素最終在序列中的位置。

//遞歸調(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]
初始值：　　?。怠　　。丁　　。础　　。场　　。薄　　。?br> 第一趟排序過程：key = 5 　a[0]為初始坑所在位置（用[ ]標(biāo)識坑的位置）
　　　　　　［５］　?。丁　　。础　　。场　　。薄　　。病　?右->左，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?。ㄕ业剑驳淖罱K位置）
第三趟：　　?。薄　　。病　　。场　　。础　　?5　　　6?。ㄕ业剑吹淖罱K位置）

２.歸并排序

歸并排序先遞歸分解序列，一分為二進(jìn)行分組，直到分解到分組只有一個元素為止，認(rèn)為其有序，再將有序分組兩兩合并，最后使整個序列有序。（歸并可以簡單理解為：遞歸分解+兩兩合并）

Paste_Image.png

將兩個有序序列合并的思路：

（1）比較兩個序列中第一個數(shù)，取出較小者，對應(yīng)取數(shù)序列取數(shù)位置后移一位，即下一個數(shù)變?yōu)榈谝粋€數(shù)。
（2）重復(fù)步驟（3），如果有序列值全部取完，那直接將另一個序列的數(shù)據(jù)依次取出即可
（3）取出的數(shù)依次存入一個新的序列，這個新的序列即為這兩個有序序列合并而成的新的有序序列

分解的實(shí)現(xiàn)比較簡單，通過改變傳入數(shù)組下標(biāo)，直接遞歸調(diào)用即可，為了便于大家理解歸并排序中遞歸與合并的概念，將歸并寫成兩個函數(shù)，參考代碼如下：

//遞歸分解操作
public void mergeSort(int a[],int begin,int end){//傳入的begin、end均為待排序數(shù)組的下標(biāo)值
        if(begin<end){
            int mid = (begin+end)/2;
            mergeSort(a, begin, mid);
            mergeSort(a, mid+1, end);
            merge(a, begin, end);
        }
    }

對于數(shù)組進(jìn)行分解，例如若某個數(shù)組長度為8，下標(biāo)為0~7，則mid = (0+7)/2=3，可將數(shù)組分成兩個子數(shù)組：下標(biāo)為[0_{3]的數(shù)組和下標(biāo)為[4}7]的數(shù)組。而對于下標(biāo)[0_{3]的數(shù)組，其mid=(0+3)/2=1，又可將其分為下標(biāo)為[0}1]的數(shù)組和下標(biāo)為[2~3]的數(shù)組。依此類推，直到分解成的數(shù)組只有一個元素為止，認(rèn)為其有序。

//合并操作
public void merge(int a[],int begin,int end){
        int mid = (begin + end)/2;//將傳進(jìn)來原數(shù)組對應(yīng)下標(biāo)的子數(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]
初始值：?。丁　　。怠　　。场　　。薄　　。浮　　。贰　。病　。?br> 　　　　?。丁　　。怠　　。场　　。薄　　。浮　　。贰　。病　。矗?~1合并）
　　　　?。怠　　。丁　　。场　　。薄　　。浮　　。贰　。病　。矗?~3合并）
　　　　?。怠　　。丁　　。薄　　。场　　。浮　　。贰　。病　。矗?~3合并）
　　　　?。薄　　。场　　。怠　　。丁　　。浮　　。贰　。病　。矗?~5合并）
　　　　?。薄　　。场　　。怠　　。丁　　。贰　　。浮　。病　。矗?~7合并）
　　　　?。薄　　。场　　。怠　　。丁　　。贰　　。浮　。病　。矗?~7合并）
　　　　?。薄　　。场　　。怠　　。丁　　。病　　。础　。贰　。福?~7合并）
　　　　　１　　?。病　　。场　　。础　　。怠　　。丁　。贰　。福ㄅ判蚪Y(jié)果）