2.快速排序

1.原理
划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：

1）．先从数列中取出一个数作为基准数。
2）．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3）．再对左右区间重复第二步，直到各区间只有一个数

2. 关键数为7 ，小的在左，大的在右

public class quickSort {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{100, 2, 5, 7, 8, 42};
        spitArr(arr, 0, arr.length, 7);
        System.out.println(Arrays.asList(arr));
    }


    private static void spitArr(Integer[] arr, int left, int right, int random) {

         left  = left -1;
        while (true) {
            while (left < right && arr[++left] < random) {
            }
            ;
            while (right > left && arr[--right] > random) {
            }
            ;
            if (left >= right) {
                return;
            } else {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
    }

    
}

3.实现快速排序
递归将数组最右边的值当做关键书，一直往下分，实现排序

public class quickSort {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{100, 3,2, 5, 7, 8,3, 42};
        //  spitArr(arr, 0, arr.length, arr[arr.length - 1]);
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.asList(arr));
    }


    //将大于random的数据放右边，小于random的数据放左边
    private static int spitArr(Integer[] arr, int left1, int right1, int random) {

        int left = left1 - 1;
        int right = right1 - 1;
        while (true) {
            // 从左开始 取比random的大的数
            while (left < right && arr[++left] < random) {
            }
            ;
            // 从右开始 取比random的小的数
            while (right > left && arr[--right] > random) {
            }
            ;
            if (left >= right) {
                break;
            } else {
                //
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        Integer tmp1 = arr[left];
        arr[left] = arr[right1 - 1];
        arr[right1 - 1] = tmp1;

        return left;
    }

    private static void sort(Integer[] arr, int left, int right) {
        if (right <= left) {
            return;
        }
        Integer a = arr[right];
        int par = spitArr(arr, left, right+1, a);
        sort(arr, left, par - 1);
        sort(arr, par + 1, right);
    }

}