快速排序、归并排序

1.快速排序

快速排序每趟选择一个基准元素，用基准元素将序列划分成两部分，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，这一趟过程称为分区（partition）操作。每一趟分区操作的目的就是把这趟的基准元素摆到最终位置。　　递归地对基准元素左边的序列和右边的序列分别调用分区操作，则当序列的大小是零或者一时整个序列排序完成，采用的是“分治”的策略。

快速排序-图片来自维基百科

思路总结：

（1）先从序列中取出一个数作为基准数。
（2）分区过程：将比基准数大的数全部放到它的右边，小于或等于它的数全部放到它的左边。
（3）对左右序列重复步骤（2），直到各序列数只有一个或零个

为了便于大家理解“分区”操作，将快排写成两个函数，大家也可以合成一个函数写，参考代码如下：

//分区操作
    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]){//从右向左遍历数组，找到第一个小于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放到数组最终位置        
        }
        return l;
    }

上面的分区操作的代码可以简单概括为“挖坑填数”，即每次partiton将序列最左边的数选为基准元素key，将key挖出，从右向左开始遍历，让序列中的数与基准元素key值进行比较，若右边有比基准值小的数，则将该数“挖”出来，“填”入坑中，被挖的数成为新的坑，每“挖、填”一次数，改变一次序列的遍历方向，直到序列遍历完成为止，将key（基准元素）填入最终结束的位置，也就确定了基准元素最终在序列中的位置。

//递归调用
public void quickSort(int a[],int left,int right){
        if(left<right){
            int t = partition(a, left, right);
            quickSort(a, left, t-1);//左边的数组快排
            quickSort(a, t+1, right);//右边的数组快排
        }
    }

排序过程如下所示：
初始状态：　　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　（找到４的最终位置）

２.归并排序

归并排序先递归分解序列，一分为二进行分组，直到分解到分组只有一个元素为止，认为其有序，再将有序分组两两合并，最后使整个序列有序。（归并可以简单理解为：递归分解+两两合并）

Paste_Image.png

将两个有序序列合并的思路：

（1）比较两个序列中第一个数，取出较小者，对应取数序列取数位置后移一位，即下一个数变为第一个数。
（2）重复步骤（3），如果有序列值全部取完，那直接将另一个序列的数据依次取出即可
（3）取出的数依次存入一个新的序列，这个新的序列即为这两个有序序列合并而成的新的有序序列

分解的实现比较简单，通过改变传入数组下标，直接递归调用即可，为了便于大家理解归并排序中递归与合并的概念，将归并写成两个函数，参考代码如下：

//递归分解操作
public void mergeSort(int a[],int begin,int end){//传入的begin、end均为待排序数组的下标值
        if(begin<end){
            int mid = (begin+end)/2;
            mergeSort(a, begin, mid);
            mergeSort(a, mid+1, end);
            merge(a, begin, end);
        }
    }

对于数组进行分解，例如若某个数组长度为8，下标为0~7，则mid = (0+7)/2=3，可将数组分成两个子数组：下标为[0_{3]的数组和下标为[4}7]的数组。而对于下标[0_{3]的数组，其mid=(0+3)/2=1，又可将其分为下标为[0}1]的数组和下标为[2~3]的数组。依此类推，直到分解成的数组只有一个元素为止，认为其有序。

//合并操作
public void merge(int a[],int begin,int end){
        int mid = (begin + end)/2;//将传进来原数组对应下标的子数组根据mid分解
        int i = begin, j = mid + 1;   //分解成两个数组:[begin~mid]、[mid+1~end]
        int k = 0;  
        int temp[] = new int[end+1];//申请额外空间来暂存排序后的新的有序数组
        while (i <= mid && j <= end)  //依次比较分解后两个数组内的数，直至其中一个数组到末尾
        {  
            if (a[i] <= a[j])  //将较小值放入临时数组的前面
                temp[k++] = a[i++];  
            else  
                temp[k++] = a[j++];  
        }            
        while (i <= mid)  //若数组[begin~mid]中还有数没取完，则将未取完的数全部追加到临时数组后面
            temp[k++] = a[i++];            
        while (j <= end)  //若数组[mid+1~end]中还有数没取完，则将未取完的数全部追加到临时数组后面
            temp[k++] = a[j++];            
        for (i = 0; i < k; i++)  
            a[begin+i] = temp[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合并）
　　　　　１　　　２　　　３　　　４　　　５　　　６　　７　　８（排序结果）