白话排序算法–快速排序

前言：

　　写到快速排序时，之前已经进行了冒泡、选择、插入排序，发现算法问题很多东西都是和实际问题相逆的，实际你可能会由外及里，由上及下，可是算法里面它有时就需要你由里往外去扩散，好比最里面的是小成果，然后一次次往外变化，成果也慢慢变大，最后直至达到最终成果为止。本篇快速排序方法因为调用了递归，你就可以逆着由里及外来思考问题。　　写这篇文章光画图就花费了我2小时时间，越抽象就越不好形容和比喻，画的不好，希望各位不要吐槽。

快速排序：先快速排序将队列一分为二，然后对每个队列进行递归调用快速排序方法，直至不能再次分解后依次返回成果。

情景描述：

　　紧接选择排序情景，有一天，被同学称为大湿的体育老师胃疼请假休息了，真好数学老师闲着就来代课了，同样要排列队形，但是数学老师牛了，说同学们，我今天教你们一种快速排序的方法，到时候来了别忘了教你们的体育老师哦（体育老师估计胃更疼了…）

一、

　我们就把第一个同学当做基数，其他同学和他进行比较，期间，基数不变，此时基数同学站出来，留下了个空位
　首先从最后一个同学开开始，依次向前和基数进行比较，第一个比基数同学等高或者矮了，就站到基数的位置，自己的位置又空下了
　步骤2后，我们再从第一位依次向后和基数比较，如果等于或者比基数高，就站到步骤二留下的空位，自己位置空出来
排除前后已经换过位置的同学，重复步骤2和3，依次和基数比较，然后坐入空位，留下新空位　　　
直到都和基数进行比较过，然后基数同学站到最后的空位里面

二、

   通过步骤一我们把要排列的队分为了两队，而两队之内还是高低不齐的
   首先来排前面的，让前面的队依旧以第一个为基数，结尾到分割线同学的前一位，执行步骤一
   接着排后面的，以分割线同学的后一位为开始，队列末尾为结束，执行步骤一
重复执行步骤2和3，直至不能再拆分即排列完成

步骤一图解

上图为一轮快速排序方法

步骤二图解

上图为依次递归调用快速排序方法，对每次的新队列进行快速排序

代码片段

/**
     * 快速排序，返回一个中轴下标
     * @param arr
     * @param low    队列起始下标
     * @param high    队列结束下标
     * @return
     */
    public int quickSort(int[] arr, int low, int high) {
        int tmp = arr[low]; // 数组的第一个作为中轴
        
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high]; // 比中轴小的记录移到低端
            
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low]; // 比中轴大的记录移到高端
        }

        arr[low] = tmp; // 中轴记录到尾
        return low; // 返回中轴的位置
    }
    
    /** 递归调用快速排序方法，对数组进行排序 **/
    public void _quickSort(int[] list, int low, int high) {
        if (low < high) {
            int middle = quickSort(list, low, high); // 获得中轴下标
            // 对前部分进行排序，递归进行，此时不会执行后半部分，直至不能再次拆分，再依次执行下半部分
            _quickSort(list, low, middle - 1);
            // 对下半部分进行排序
            _quickSort(list, middle + 1, high); 
        }
    }

　　代码挺少，但是没图的话理解起来太抽象了，还得边拿笔画着边执行着，完了才领悟了其原理。

再来严谨的总结下步骤：

设置两个变量i、j，排序开始的时候：i=0，j=N-1
从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换
从j开始向前搜索，即由后开始向前搜索（j — ），找到第一个小于key的值A[j]，A[i]与A[j]交换
从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换
重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束