《算法设计与分析》--快速排序随笔

快速排序:快排是一种基于分治策略的一个排序算法，其基本的思想是对于输入的子数组a[p:r]可以按照分解、递归求解、合并进行解决。

分解:以a[p]为基准的元素将a[p:r]切分成3段，a[p:q-1],a[q]和a[q+1:r],这样就可以使得 a[p:q-1]中任何元素小于a[q],a[q+1]中任何元素都大于a[q]。

递归求解:递归调用快速排序算法，分别递归对a[p:q-1]和a[q+1:r]进行排序。

合并数组:由于对于a[p:q-1]和a[q+1:r]是就地进行的，意思就是本身就是按照这个大小顺序排列的，所以直接合并就达到最终的数组是有序的了。

快速排序代码块:

public static void quickSort(int[] arr,int _left,int _right){

    int left = _left;
    int right = _right;
    int temp = 0;
    if(left<=right){
    
    temp = arr[left];

    while(left != right){
    
    while(right>left && arr[right] >=temp){
     right--;
   
    } 
    arr[left] = arr[right];
    
    while(arr[left]>arr[right] && arr[left] <=temp){
    left++;
    } 
    arr[right] = arr[left];
}
    arr[right] = temp;
    quickSort(arr,_left,left-1);
    quickSort(arr,right+1,_right);
    }

}

在快速排序算法对a[p:r]进行划分的同时，以元素x=a[p]作为划分的基准，分别从左右两边开始，扩展两个区域a[p:i]和a[j:r],使得a[p:i]的元素小于或者等于x,而a[j:r]中的元素大于等于x,初始时i=p,且j=r+1。

在while循环中，下标j逐渐减小，i逐渐增大，直到a[i]>=x>=a[j]，如果这两个不等式是严格的，则a[i]不会是左边区域的元素，a[j]不会是右边区域的元素，此时若i<j,就应该交换a[i]与a[j]的位置，扩展左右两个区域。

while循环重复至i>=j时候结束，这时候a[p:r]已经被划分成了a[p:q-1],a[q]和a[q+1,r]，且满足a[p:q-1]中的元素不大于a[q+1,r]中元素。

敲黑板:注意算法中的下标i和j不会超出a[p:r]的下标界，另外，在快速排序中选取a[p]作为比较基准，可以保持算法正常结束，如果选择a[r]作为划分的基准，则ar[r]又是a[p:r]中的最大元素，则算法的又会进入死循环，其实快速排序和划分是否对称是存在关系的。