快速排序本身也有好多种实现方式,实现细节有差异

自己的理解,如有错误地方 欢迎留言

1 双向指针   

B站视频地址:舞动的排序算法 快速排序  https://www.bilibili.com/video/BV1xW411Y7g3?t=4

感谢视频原创作者

  /**
     * q1:为什么右边先行,基数是数组首元素时候,需要从数组尾部开始
     * q2:为什么枢纽值正好位于i=j那个位置上,因为找到需要交换的值时候,枢纽值会被交换到暂停的位置,最终暂停点的条件就是i=j
     * q3:为什么数据重复,能正确排序,因为递归结束条件是只有一个元素
     * @param ints
     * @param low 0开始
     * @param high 最大下标=length-1
     */
    public void quick(Integer[] ints, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivot = ints[low];

        int i = low;
        int j = high;
        // 右边先行
        for (; j >= 0; j--) {
            //找到第一个小于枢纽值的元素
            if (ints[j] < pivot) {
                this.swap(ints, i, j);
                //左边开始,找到第一个大于枢纽值的元素
                for (; i < ints.length; i++) {
                    if (ints[i] > pivot) {
                        this.swap(ints, i, j);
                        break;
                    }
                    if (i >= j) {
                        break;
                    }
                }
            }

            // 为啥是末尾判断,因为内部break后 外层循环会再进入一次,导致j少1
            if (i >= j) {
                break;
            }
        }
        // 中心点左侧,debug时候,会发现,i处就是枢纽值,将i左右2边分开,进行递归,左边的开始永远是0,右边的结尾是数组最大下标
        quick(ints, low, i - 1);
        // 中心点右侧
        quick(ints, i + 1, high);
    }


@Test
    public void quick_sort1() {
        Integer[] ints = {7, 3, 7, 10, 2, 10, 1, 4, 9, 8, 3, 20};
        /* 递归时候,往往是先写一次循环的逻辑
        int pivotP = 0;
        int pivot = ints[pivotP];

        int i = pivotP;
        int j = ints.length - 1;

        for (; j > 0; j--) {
            if (ints[j] < pivot && i < j) {
                this.swap(ints, i, j);
                i++;
                for (; i < ints.length; i++) {
                    if (ints[i] > pivot && i < j) {
                        this.swap(ints, i, j);
                        break;
                    }
                }
            }
        }*/
        quick(ints, 0, ints.length - 1);

        log.info("{}", JSON.toJSONString(ints));

    }