快速排序

一、思路

二、结论

1. 先找基准点，使用的是数组下标中间值为基准点
2. 注意在左边找比基准点大的值，右边找比基准点小的值。若当前值不符合要求则找下一个数
3. 当发现左边下标与右边的下标相等时，证明左边的值已经小于基准点了右边的值大于基准点了，此时第一轮排序已经完成。
4. 接下来只需要分别按上述规则在左边和右边分别进行排序(递归)

三、代码

public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[]{3, 9, -1, 10, 20, 5};
        int[] ints = quickSort(array, 0, array.length - 1);
//        quickSort1(array, 0, array.length - 1);
//        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(ints));

    }
    public static int[] quickSort(int[] array, int left, int right){
        int l = left;// 左下标
        int r = right;// 右边下标
        int base = array[(right + left) / 2]; // 整个数组中间的值
        int temp = 0;// 临时变量
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while (l < r){
            while (array[l] < base){ // 在左边寻找比base大的值
                l += 1;
            }
            while (array[r] > base){// 在右边寻找比base小的值
                r -= 1;
            }
            // 发现l >= r 了说明左边的数比base小 右边的数比base大，就可以结束循环，
            // 如果发现l < r 说明 左边的数比 base要大，得进行交换才行
            if (l >= r){在结束前将下标的位置进行重置
                r++;// 这里debug可以看得更清楚。
                l--;
                break;
            }
            // 将上面找到的值进行交换
            temp = array[r];
            array[r] = array[l];
            array[l] = temp;

            //如果交换完后，发现这个array[l] == pivot值 相等 r--， 前移
            if(array[l] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个array[r] == pivot值 相等 l++， 后移
            if(array[r] == pivot) {
                l += 1;
            }
        }

        // 判断是否进行递归。
        if (l > left){ // 向左递归
            quickSort(array, left, l);
        }
        if (r < right){//  向右递归
            quickSort(array, r, right);
        }
        return array;
    }

    public static void quickSort1(int[] array,int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        //pivot 中轴值
        int pivot = array[(left + right) / 2];
        int temp = 0; //临时变量，作为交换时使用

        while( l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while( array[l] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while(array[r] > pivot) {
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if( l >= r) {
                break;
            }

            //交换
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;

            //如果交换完后，发现这个array[l] == pivot值 相等 r--， 前移
            if(array[l] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个array[r] == pivot值 相等 l++， 后移
            if(array[r] == pivot) {
                l += 1;
            }
        }

        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if(left < r) {
            quickSort(array, left, r);
        }
        //向右递归
        if(right > l) {
            quickSort(array, l, right);
        }
    }
}