快速排序

快速排序，顾名思义，是消耗时间较少的排序算法。其基本思想也是基于自顶向下，分而治之。

对于升序排序，首先选取一个元素，将其放到特定的位置，使这个元素左边的值都比它小，右边的值都比它大。然后问题就被化解成对左边的数组进行排序和右边的数组进行排序，直到数组元素只剩一个时，直接返回最小解。

使用递归算法的代码如下：

public static void quickSort(int[] numbers, int s, int e) {
    if (s >= e)
        return;
    int tmp = numbers[s];
    int i = s;
    int j = e;
    while (i < j) {
        while (i < j && numbers[j] >= tmp) {
            j--;
        }
        numbers[i] = numbers[j];
        while (i < j && numbers[i] <= tmp) {
            i++;
        }
        numbers[j] = numbers[i];
    }
    numbers[i] = tmp;

    quickSort(numbers, s, i - 1);
    quickSort(numbers, i + 1, e);
}

但是，使用递归总是面临着栈溢出的风险，所以也需要考虑非递归的算法，究其本质，只是使用外部栈来实现递归的过程。

其基本思想如下：

在进行一轮划分后，把右边的数组先存到栈中，继续划分左边的数组，直到没有数组可以划分，这时从栈中取出数组继续划分，循环直到栈为空。

Java代码如下：

public static void quickSort2(int[] numbers) {
    /**
     * 非递归算法，用栈来存储还未排序的片段，然后当只剩当前 一个元素时从栈中取数据，直到栈空
     */
    int s = 0;
    int e = numbers.length - 1;
    Stack<Integer> start = new Stack<>();
    Stack<Integer> end = new Stack<>();
    int tmp;
    int i;
    int j;

    while (s < e || !start.isEmpty()) {
        if (s < e) {
            tmp = numbers[s];
            i = s;
            j = e;
            while (i < j) {
                while (i < j && numbers[j] >= tmp) {
                    j--;
                }
                numbers[i] = numbers[j];
                while (i < j && numbers[i] <= tmp) {
                    i++;
                }
                numbers[j] = numbers[i];
            }
            numbers[i] = tmp;
            start.add(i + 1);
            end.add(e);
            e = i - 1;
        } else if (!start.isEmpty()) {
            s = start.pop();
            e = end.pop();
        }
    }
}