快速排序详解（一文解决）

排序算法跳转总目录

快速排序

问：整体流程是什么？
答：整体流程就是将大于衡量数的放在右边，小的放在左边；
问：怎样实现的？
答：借助栈内指针（即，将传入的值赋值于另一个变量进行操作）
问：具体怎么放的？
答：因为衡量数已经赋值于其它变量了，我就借助衡量数原先在数组中的位置，倒来倒去
问：会有很多情况会越界吗？
答：会的，在代码多次调试解决；

代码兼解析：

java">    /**
     * 1. 随机取出来一个数作为衡量数，
     * 2. 小于衡量数的放于左边（采用当前栈内指针）
     * 3. 大于衡量数的放于右边（采用当前栈内指针）
     * 4. 此处简单说明一下，
     * 白话文：衡量数在数组中的位置，我可以将数组的一个小于衡量数的值覆盖衡量数在数组中的位置，
     *        此时覆盖衡量数的值原先的位置，我找大于衡量数的值覆盖，
     *        覆盖来覆盖去，最后我把最后空下来的位置给衡量数
     *        此时一轮操作就完成了
     * 所以：我说：是宏观上交换，微观上是赋值
     * 5. 向左，向右，递归
     *
     * @param arr 传入数组
     * @param l   传入左指针位置
     * @param r   传入右指针位置
     */
    private static void quickSort(int[] arr, int l, int r) {
        //6.下面看完再看此处；给出口：当什么情况下我就排序完成了呢？
        //  因为涉及到递归，而且传入的都是什么r+1，r-1的，所以至少得l>=r
        if (l >= r) {
            return;
        }

        //1.确定衡量数—（这里小编采取第一位，你也可以中间，后边）
        int temp = arr[l];
        //2.因为涉及到栈的运算，所以每一个递归栈应该有自己的左右指针(不懂得话，先看下去，等下面的递归明白了，这就通了)
        int left = l;
        int right = r;
        //3.进行：小于衡量数的放于左边；大于衡量数的放于右边操作
        while (left < right) {//当左指针小于右指针，说明此轮尚未全部比较

            //3.1:找出第一个比衡量数小的数
            while (arr[right] >= temp && left < right) {//当右指针指的数大于等于衡量数，说明需要判断下一个
                right--;//判断下一个
            }//退出while：说明当右指针指的数不大于衡量数，当前right就指向了该数，下面对该数进行操作（宏观上可以说是换位，但是细细的看只能说是赋值）
            //3.2：并将该数赋值于衡量数在数组中的位置（正是left指向的数），因为left指向的数已经记录在衡量数内，不害怕丢失
            arr[left] = arr[right];
            //3.1,3.2意欲何为：将从右指针遍历过来的第一个小于衡量数的数，放在我不会覆盖其它值的位置（即我的left指针指向的位置，原因是：left指针指向的数记录给了衡量数）

            //3.3：找出第一个比衡量数大的数
            while (arr[left] <= temp && left < right) {//当左指针指的数小于等于衡量数，说明需要判断下一个
                left++;//判断下一个
            }//退出while循环：说明找到了比衡量数大的数
            //3.4：将该值赋值于可以覆盖的数，（哪一个呢？上面的3.1，3.2得到的数和它原本的位置不是正好赘余了吗！那么就覆盖上面的rigth指针的位置）
            arr[right] = arr[left];
            //3.3,3.4意欲何为：将从左指针遍历过来的第一个大于衡量数的数，放在我不会覆盖其它值的位置（即我的right指针指向的位置，原因是：right指针指向的数记录给了其它位置）

            //3.5：left指针和right指针相碰撞的那一刻，说明了衡量数前面的比衡量数小，后面的比衡量数大，而此时只有衡量数没有位置，就将衡量数赋值于此
            if (left >= right) {
                arr[left] = temp;
            }
            //3.5意欲何为：将衡量数的值确定下来
        }
        //4.向左递归
        quickSort(arr, l, right - 1);
        //5.向右递归
        quickSort(arr, right + 1, r);
    }