用途

快速排序作为最快的排序算法之一，代码比较简洁，在面试中可能会被问到；另一方面，快排由于每次可以确定一个位置，比它大和比它小的数均会分布在两边，所以一般在第K个问题、前K个问题、后K个问题中会有很优秀的表现。

模板-递归实现

/**
 * 快速排序
 * 
 * @param nums 待排序数组
 * @param l    开始位置下标
 * @param h    结束位置下标
 */
public void QuickSort(int[] nums, int l, int h) {
    if (l >= h) {
        return;
    }
    int index = getIndex(nums, l, h);
    QuickSort(nums, l, index - 1);
    QuickSort(nums, index + 1, h);
}

public int getIndex(int[] nums, int l, int h) {
    int temp = nums[l];
    while (l < h) {
        while (l < h && nums[h] >= temp) {
            h--;
        }
        nums[l] = nums[h];

        while (l < h && nums[l] <= temp) {
            l++;
        }
        nums[h] = nums[l];
    }
    nums[l] = temp;
    return l;
}

注意：参数中的l, h均是数组的下标

模板-非递归版

public void quickSort(int[] nums) {
    int n = nums.length;
    Node all = new Node(0, n - 1);
    Stack<Node> stack = new Stack<Node>();
    stack.push(all);
    while (!stack.isEmpty()) {
        Node temp = stack.pop();
        int start = temp.start;
        int end = temp.end;
        int target = nums[start];
        int l = start, h = end;
        while (l < h) {
            while (l < h && nums[h] >= target) {
                h--;
            }
            nums[l] = nums[h];
            while (l < h && nums[l] <= target) {
                l++;
            }
            nums[h] = nums[l];
        }
        nums[l] = target;
        Node left = new Node(start, l - 1);
        Node right = new Node(l + 1, end);
        if (l + 1 < end)
            stack.push(right);
        if (start < l - 1)
            stack.push(left);
    }
}

class Node {
    int start;
    int end;

    public Node(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

非递归版主要维护一个栈和下标，显得比较臃肿，没有递归方法那么简洁。另外，结点类Node可以采用每次向栈中压两个数、取两个数来代替；非递归的循环中其实也包含了getIndex方法的代码，抽取出来也可以让代码看着简洁。