《数据结构与算法之美》笔记—快速排序

快排

相对快排，大家可能更熟悉冒泡排序，冒泡排序是比较相邻的两个元素。但是在数据量大的情况下，耗时却比快排多很多。所以掌握快排也是很有必要的。

快排思想：

其实只要大家理解了分治思想(顾名思义就是分而治之)，那么快排思想也差不多掌握的差不多了。快排的解题思路，就是在待排序的数组中，找到一个参照元素，为什么要选一个参照物呢，就是为了分治，让小于和大于参照元素的其他数据，能按照小于参照元素的数据在左边，大于参照元素的在右边，在大于和小于参照元素的区间，递归执行同样的分治排序，直到分治的区间为1的时候，就说明所有的数据都排好循序了

   以这个数字为例子： int ints[] = {5, 0, 11, 88, 99, 3, 4, 9, 8};

以最后一个数据作为参照数据，按照上面说的思路进行，定一个记录小于参照元素的个数的变量 counter，循环数组和参照元素对比，如果元素比参照元素小则交换元素，并且 counter 记录的个数+ 1。

image.png

        int pivot = end;
        int counter = begin;  //记录小于参照元素的个数，begin 是循环的开始的下标，一开始也就是0
         //end 就是区间最后的一个下标
        for (int i = begin; i < end; i++) {
            //将小于 end 下标的元素(a[end])放到左边
            if (a[i] < a[pivot]) {
                int temp = a[counter];
                a[counter] = a[i];
                a[i] = temp;
                counter++;
            }
        }

经过这一步之后，我们也统计到了小于参照元素的个数，也就是 counter = 4,因为 5，0，3，4都小于8所以有4个小于的，排序后的数据数据如下：

image.png

然后我们把从第一个大于8的元素也就是99和8交换位置，就达成小于参照元素的在左边，大于参照元素的在右边：

 //将 end 元素，放到小于它的元素后面的位置，例如 1，2，3，end,...
        int temp = a[pivot];
        a[pivot] = a[counter];
        a[counter] = temp;

image.png

然后就分治成了3个区域，第一个{5,0,3,4,}, 第二个{8},第三个{11,88,9,99}，那么我们只要把第一和第三个区间的数据排好序，那么这个数组也就排好序了。他们的排序第方式和上面的排序方式是一样的也就是可以递归刚才第方法：

递归小于参照元素的：
//partition 是参照元素的下标
quickSort(a, begin, partition - 1);
递归大于参照元素的：
//end 最后一个元素的下标
quickSort(a, partition+1，end);
//结束递归的条件：
end<=begin,也就是待排序区间为1的时候

全部代码：

 /**
     * 快排思路：
     * 1.先找到一个参照对象，数组里任意一个数都可以
     * 2.然后循环数组让小于 参照对象的 排到左边，让大于参照对象的排右边
     */
    public static int[] quickSort(int[] a, int begin, int end) {
        //递归的终止条件
        if (end <= begin) return a;
        //得到参照对象的下标
        int partition = partition(a, begin, end);
        //递归左右两边，让他们自己去排序
        quickSort(a, begin, partition - 1);
        quickSort(a, partition + 1, end);
        return a;
    }

    //获取参照元素
    private static int partition(int[] a, int begin, int end) {
        int pivot = end;
        int counter = begin;
        for (int i = begin; i < end; i++) {
            //将小于 end 的元素放到左边
            if (a[i] < a[pivot]) {
                int temp = a[counter];
                a[counter] = a[i];
                a[i] = temp;
                counter++;
            }
        }
        //将 end 元素，放到小于它的元素后面的位置，例如 1，2，3，end,...
        int temp = a[pivot];
        a[pivot] = a[counter];
        a[counter] = temp;
        return counter;
    }