快速排序

时间复杂度：O(NlogN)，最坏为O(N\N)(逆序的情况)

基本思想：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数

本质上是分治算法

关键步骤：

算法的关键在于实现对于数组的左右分割，即实现将比pivot小的置于其左侧，比pivot大的置于其右侧。

具体实现步骤如下：

1.选取数组的最后一项为pivot；

2.令i指向第一个比pivot大的数，即对于input[start:i-1]，都小于pivot，input[i:end-1]都大于pivot;这个过程用循环实现

3.将pivot于i指向的元素互换位置，使得比pivot小的在其左侧，比pivot大的在其右侧。

4.对pivot两边的子序列递归，进行同样的操作，直至操作序列为一个数。

下面给出一个分割的例子

假设用户输入了如下数组：

下标	0	1	2	3	4	5
数据	6	2	7	9	8	3

此时i = 0; j =0,因为input[0]>pivot,故比pivot小的数没有，不需要改变i的指向，结果如下：

下标	0	1	2	3	4	5
数据	6	2	7	9	8	3

此时i = 1; j = 1,因为j指向的元素2比pivot小（这里的input在这句话上面），故需要交换位置，并将i+1,结果如下：

下标	0	1	2	3	4	5
数据	2	6	7	9	8	3

………

最终将pivot于i的指向的值交换位置，得到如下结果：

下标	0	1	2	3	4	5
数据	2	3	7	9	8	6

然后，对pivot两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

代码实现：

class Solution {
    void quicksort(int[] input) {
        helper(input, 0, input.length - 1);
    }

    void helper(int[] input, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = input[end];
        int i = start;
        //在循环中中，每次都保证如下条件
        //对于input[start:i-1],都小于pivot
        //对于input[i:j],都大于pivot
        for (int j = start; j < end; j++) {
            if (input[j] < pivot) {
                swap(input, i, j);
                i++;
            }
        j
        //分类完成，将pivot与i指向的元素互换
        //因为i指向的是比pivot大的元素，互换不影响分割
        swap(input, i, end);
        helper(input, start, i - 1);
        helper(input, i + 1, end);
    }

    void swap(int[] x, int a, int b) {
        int tmp = x[a];
        x[a] = x[b];
        x[b] = tmp;
    }
}