数据结构与算法之快速排序

核心思想：从要排序的一组数据中取出任意一个数x，作为分区点，将小于x的数放到其左边，将大于x的数放到其右边，x放中间，这就完成了一次处理。

一次操作后将数据分为了三部分，小于x的部分，x和大于x的部分，其中小于x和大于x的部分，分别重复上面的操作，即每个数据组任取一个数作为分区点，继续比较将数据分区。

看下面的例子：

[3, 2, 6, 10, 7, 1, 8, 5]		|	取分区点为数组最后一个数，值为5
[3, 2, 1]	5	[6, 10, 7, 8]	|	数组分为了三个部分
空 1 [3, 2]		[6, 7] 8 [10]	|	两个子数组各自分为了三个部分
    空 2 [3]				|	重复以上步骤
[1, 2, 3, 5, 6, 7, 8, 10]	 	|	最终没有要处理的数据，那么数组已经有序了

快排依旧是分治思想，递归处理。
每次排序都是将数组分为两部分，所以递推公式的重点就是找到两部分数据的区间
递推公式： quickSort(arrs,start,mid-1)+quickSort(arrs,mid+1,end)

代码：

public static void sort(int[] arrs, int start, int end) {
        if(start >= end) {return;}
        int mid = partition(arrs, start, end);
        sort(arrs, start, mid-1);
        sort(arrs, mid+1, end);
    }

    public static int partition(int[] arrs, int start, int end) {
        int pivot = arrs[end];
        int i = start;
        for(int j=start; j<end; j++) {
            if(arrs[j]<pivot) {
                int temp = arrs[i];
                arrs[i] = arrs[j];
                arrs[j] = temp;
                i++;
            }
        }
        int temp = arrs[i];
        arrs[i] = arrs[end];
        arrs[end] = temp;

        System.out.println();
        System.out.println("排序后的数组:");
        Arrays.stream(arrs).forEach(x->System.out.print(x + " "));
        return i;
    }

输出：

排序前的数组:
6 2 7 1 2 11 3 21 15 10 
排序中间值:
6 2 7 1 2 3 10 21 15 11 
排序中间值:
2 1 2 3 7 6 10 21 15 11 
排序中间值:
1 2 2 3 7 6 10 21 15 11 
排序中间值:
1 2 2 3 6 7 10 21 15 11 
排序中间值:
1 2 2 3 6 7 10 11 15 21 
排序中间值:
1 2 2 3 6 7 10 11 15 21 
排序后的数组:
1 2 2 3 6 7 10 11 15 21 

快速排序的时间复杂度O(nlogn)，极端情况下会退化为O(n^2)，空间复杂度为O(1)。