算法-排序-快速排序

快速排序简称快排，它的核心思想也是分治，但是和归并完全不一样。

快排的执行逻辑是这样的：

1. 随机指定给定数组的任意一个元素p（经典快排是选择最后一个元素），以该元素为分区点。
2. 将给定数组中小于p的元素放在p的左边，大于p的元素放在p的右边，这样p在该数组中的位置就是有序的位置
3. 递归p元素左右两边的数据段，直到数据段缩小到1，这样整个数组就是有序的了

能列出递推公式了吗？
f(n-m) = f(n - q-1) + f(q+1 - m)
终止条件就是n>=m

来看看执行图吧

快排执行示意图

可能你会疑惑为什么拆分后的数组是这样排列的，下面就来详细解释第二步是怎么实现的。
可能对于小的放p点的左边，大的放p点的右边这点，最先想到的步骤可能是这样的

1. 申请两个数组，left[]和right[]
2. 遍历数组把小的放进left里，大的放进right里
3. 将两个数组中的元素以及p重新放回到原数组

这个确实能实现第二个步骤，但是同样的它也带来很多空间的消耗，那有没有一种方法可以实现原地排序呢（也就是空间复杂度是O(1)）这里有个比较巧妙的思想（如果分区点是最后一个元素则进行以下步骤，如果分区点是随机元素则需要先和end元素做置换）。

1. 设置i，j两个指向start位置的下标，遍历j
2. 对比j的值所代表的值是否小于p值
3. 如果j的值小于p的值，则交换i，j的值且把i的位置后移一格，直到j遍历到p的前一个位置（也就是end-1的位置)
4. 最后将i和p的值交换，并返回i的位置及是分区点

其实有点像插入排序的思维，保持i的左边都是小于p值的，当j遍历完成后，除p位置外，i及i的右边都是大于等于p值，所以当将i值和p的值交换后，即可达到p值的左边都是小于p值的，p的右边都是大于等于p值的。可能还是有点难理解，没关系，我们看图（以上图第一步为例子）

返回分区点的执行示意图

这样理解了吗？来看看代码吧

package sort;

/**
 * @author TioSun
 * 快速排序
 */
public class QuickSort {

    public void sort(int[] a, int n) {

        quickSort(a, 0, n - 1);

    }

    /**
     * 快速排序
     * @param a 待排序数组
     * @param start 待排序数组段的开始位置
     * @param end 待排序数组段的结束位置
     */
    private void quickSort(int[] a, int start, int end) {

        // 递归终止条件
        if (start >= end) {
            return;
        }

        // 获取分区点
        int breakPoint = findBreakPoint(a, start, end);

        // 递归排序分区点左边的数组段
        quickSort(a, start, breakPoint - 1);
        // 递归排序分区点右边的数组段
        quickSort(a, breakPoint + 1, end);

    }

    /**
     * 寻找分区点的下标
     * 分区点满足以下条件
     * 1. 分区点左边的值都小于分区点的值
     * 2. 分区点右边的值都大于等于分区点的值
     * @param a 待排序数组
     * @param start 待排序数组段的开始位置
     * @param end 待排序数组段的结束位置
     * @return 分区点的下标
     */
    private int findBreakPoint(int[] a, int start, int end) {

        // i指针，满足i的左边都小于分区点
        int i = start;
        // 设定以p为分区点
        int p = end;

        for (int j = start; j < end; j++) {
            // 如果j的值小于分区点的值则交换i,j的值，并将i后移（视为扩充小于分区点的区域）
            if (a[j] < a[p]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
            }
        }
        // 交换分区点和i的值，此时i即分区点的下标
        int temp = a[i];
        a[i] = a[p];
        a[p] = temp;

        return i;
    }
}

快排的时间复杂度和空间复杂度

快排的是一种不稳定的原地排序，所以其空间复杂度是O(1)，时间复杂度和分区是否均匀有很大关系，也就是和分区点的选择有很大关系，时间复杂度分析起来比较复杂，这里直接给出，有时间了可以再分析。快排的平均时间复杂度是O(nlogn)，最差情况下会退化到O(n^2)。