数据结构之排序：快速排序

快速排序（Quick Sort）由 C. A. Hoare 在1962年提出，是冒泡排序的一种改进。采用了分治策略，将原问题划分成若干个规模更小但与原问题相似的子问题，然后递归方法解决，合并问题的解。

基本思想

通过一趟排序将序列分割成独立的两个部分，其中一部分的所有记录的关键值都比另外一部分的所有关键值小，按照这种方法对两部分记录分别进行快速排序，递归进行。

一趟快速排序的主要步骤

1. 设置两个变量i、j，初值分别为low,high,分别表示待排序序列的起始下标和终止下标
2. 将第i个记录暂存在变量pivot中，即pivot = r[i]
3. 从下标为j的位置开始由后向前一次搜索，当找到第1个比pivot的关键值小的记录是，将该记录向前移动到下标为i的位置，i = i + 1
4. 从下标为i的位置开始右前向后一次搜索，当找到第1个比pivot的关键字值大的记录是，将该记录向后移动到下标为j的位置上，j = j - 1
5. 重复步骤3、4，直到 i == j 为止
6. 最后，令r[i] = pivot

性能分析

空间复杂度：快速排序在系统内部需要栈结构实现递归，每层递归调用时的指针和参数均需要用栈存放。其递归过程可用一颗二叉树表示。如果每次划分较为均匀，则递归树的高度为 O(logn) ，则栈空间为 O(logn) 。最坏情况下，递归树是一颗单支树，树的高度为 O(n) ，则空间复杂度为 O(n) 。

时间复杂度：最好的情况 O(nlogn) ，最坏的情况是初始关键字序列有序或基本有序时，在快速排序过程中每次划分只能得到一个子序列，退化为冒泡排序，时间复杂度为 O(n2) 。就平均性能来说，快速排序使基于关键字比较的内部排序算法中速度最快的，平均时间复杂度为 O(nlogn) 。

java代码实现：

/**
     * 快速排序     O(nlog2n)
     * 递归实现
     * @param arr 需要排序的表
     * @param low 起始位置
     * @param high 结束位置
     */
    public static <T extends Comparable<T>> void quickSort(T[] arr,
            int low, int high) {
        if (low < high) {
            // 分割递归调用快速排序
            int pivotPos = partition(arr, low, high);
            quickSort(arr, low, pivotPos - 1);
            quickSort(arr, pivotPos + 1, high);
        }
    }
    /**
     * 快速排序分割
     * @param arr 原始表
     * @param i 起始位置
     * @param j 结束位置
     * @return
     */
    public static <T extends Comparable<T>> int partition(T[] arr,
            int i, int j) {
        T pivot = arr[i];   // 第i个元素作为支点
        // 从表的两端交替向中间扫描
        while (i < j) {
            while (i < j && pivot.compareTo(arr[j]) <= 0) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];    // 将比支点记录小的记录向前移动
                i++;
            }

            while (i < j && pivot.compareTo(arr[i]) >= 0) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];    // 将比支点记录大的向后移动
                j--;
            }
        }
        arr[i] = pivot;     // 记录支点位置并返回
        return i;
    }

参考：
1. 刘小晶，数据结构——Java语言描述（第2版），清华大学出版社
2. MARK A W， 数据结构与算法分析: Java 语言描述，机械工业出版社