Java 快速排序多种实现

快速排序思想

每一轮遍历选择一个基准点（pivot）进行分区。

小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区。

当分区完成时，基准点的位置就是排序后该元素应该处于的位置。

在每个子分区中重复以上过程，直到分区中元素少于等于 1 。

快排实现方式

快排有多种实现方式，一般可以按分区方案分为两种。

单边循环 （lomuto 洛穆托分区）

单边循环的方案代码量相对比较少，也更好理解。双边循环的方案也是在此基础上进行的优化。

实现思路：

• 选择最右边的元素作为基准点元素
• 维护两个变量 i,j，j 负责找到比基准点小的元素
• 找到比基准点小的元素，就与 i 进行交换
• i 记录小于基准点元素的边界，也是每次交换的目标位置
• 最后基准点与 i 交换
• 重复以上过程

双边循环（hoare 霍尔分区）

双边循环方案是快排最初的实现版本，由于快排是由 hoare 提出的，因此由称之为 霍尔分区。

实现思路：

• 选择最左边元素作为基准点元素
• 维护两个变量 i,j，j 负责从右向左找到比基准点小的元素
• i 负责从左向右找到比基准点大的元素
• 一旦找到符合的元素，就交换二者，直到 i,j 相交
• 最后基准点与 i 交换

代码实现

先来模拟一次遍历：

public static void main(String[] args) {
    int[] nums = {5, 9, 7, 4, 1, 8, 3, 2, 6};
    System.out.println("排序前 " + Arrays.toString(nums));

    // i 初始值最左边
    int i = 0;
    int right = nums.length - 1;
    // 基准点取最后一个元素
    int pv = nums[right];
    // 遍历所有元素
    for(int j = 0; j < right; j++){
        // 每个元素和基准点比较
        if(nums[j] < pv){
            System.out.println("交换 " + nums[i] + " 与 " + nums[j] + "; ");
            // 比基准点小的元素，放到左区间
            swap(nums, i, j);
            // 左区间“扩容”
            i++;
        }
    }
    // 把基准点元素放到它应该所处的位置
    swap(nums,right, i);
    System.out.println("i=" + i + "，数组为 " + Arrays.toString(nums));
}

private static void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

当选择最后一个元素 6 为基准点，一趟遍历后，比 6 小的元素都在左边，比 6 大的元素都在右边。

为了方便之后的遍历过程，将上面的代码重构一下：

public static void main(String[] args) {
    int[] nums = {5, 9, 7, 4, 1, 8, 3, 2, 6};
    System.out.println("排序前 " + Arrays.toString(nums));
    partition(nums, 0, nums.length - 1);
}

private static void partition(int[] nums, int left, int right) {
    int i = left;
    int pv = nums[right];
    // 遍历所有元素
    for (int j = 0; j < right; j++) {
        // 每个元素和基准点比较
        if (nums[j] < pv) {
            System.out.println("交换 " + nums[i] + " 与 " + nums[j] + "; ");
            // 比基准点小的元素，放到左区间
            swap(nums, i, j);
            // 左区间“扩容”
            i++;
        }
    }
    // 把基准点元素放到它应该所处的位置
    swap(nums, right, i);
    System.out.println("i=" + i + "，数组为 " + Arrays.toString(nums));
}

注意遍历的部分，实际上我们只需要遍历 left 到 right 区间内的元素即可。因为 left 左边的元素一定比基准点元素小。

当然还需要该方法返回基准点正确的位置，作为下一次遍历的 left 。

改造后：

private static int partition(int[] nums, int left, int right) {
    int i = left;
    int pv = nums[right];
    for (int j = left; j < right; j++) {
        if (nums[j] < pv) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, right, i);
    return i;
}

循环思路

这里采用递归的思路实现遍历：

private static void quickSort(int[] nums, int left, int right){
    if(left >= right){
        return;
    }
    // 基准点的正确位置
    int cur = partition(nums, left, right);
    // 基准点左分区
    quickSort(nums, left, cur -1);
    // 基准点右分区
    quickSort(nums, cur + 1, right);
}

从上面的打印日志，可以发现有相同元素的交换，实际上可以在交换之前加判断，阻止相同元素交换。

完整代码

单边循环快排的完整代码：

public class QuickSingle {

    public static void main(String[] args) {
        int[] nums = {5, 9, 7, 4, 1, 8, 3, 2, 6};
        System.out.println("排序前 " + Arrays.toString(nums));
        quickSort(nums, 0, nums.length - 1);
    }

    private static void quickSort(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        int cur = partition(nums, left, right);
        quickSort(nums, left, cur -1);
        quickSort(nums, cur + 1, right);
    }

    private static int partition(int[] nums, int left, int right) {
        int i = left;
        int pv = nums[right];
        for (int j = left; j < right; j++) {
            if (nums[j] < pv) {
                System.out.println("交换 " + nums[i] + " 与 " + nums[j] + "; ");
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, right, i);
        System.out.println("i=" + i + "，数组为 " + Arrays.toString(nums));
        return i;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

双边循环

双边循环的代码只有分区部分不同，其他的代码可以不用修改。

private static int partition(int[] nums, int left, int right) {
    // 基准点选择最左边的元素
    int pv = nums[left];
    int i = left;
    int j = right;
    while(i < j){
        // j 从右边开始找比基准点的小的元素
        while(i < j && nums[j] > pv){
            j--;
        }
        // i 从左边开始找比基准点大的元素
        while (i < j && nums[i] <= pv){
            i++;
        }
        swap(nums, i, j);
    }
    swap(nums, left, i);
    return i;
}

双边循环需要注意的点比较多：

• 必须先操作 j ，再操作 i，也就是先在右边找比基准点大的元素
• 外层有while(i < j)控制i 和 j 的值，内层也需要 while(i < j && xx) ， i< j 不能省
• 操作 i 时，左边第一个元素和基准点是相等的，此时也需要 i++ ，因此 nums[i] <= pv 中的等号不能省

快排总结

• 快排的平均时间复杂度尾 O(nlogn)
• 当数组中重复元素很多时，复杂度最差会退化到 O(n²)
• 快排是不稳定的排序
• 数据规模较小时，快排没有优势
• 单边循环实现简单，但是性能没有双边循环好，双边循环性能大约是单边循环的 3 倍