快速排序

#personal/blog #algorithm/sorting

概述

快速排序（Quick Sort）的基本原理是先界定一个分界值 value，将比 value 小的值放在左边，大的放在右边；再进行递归运算（以左边为例），在左边再界定一个边界值 value2，再一分为二；直到剩最后一个元素时，递归结束。出栈后，此时 arr 就是有序数组（升序）了。
快速排序是时间复杂度为 O(N∗log2N) 与归并排序属于同一量级，但是经过大量的测试发现，其实快速排序的效率是要高于归并排序的。

思路分解

  1. 选定分界值；
  2. 设计递归逻辑；
  3. 设计函数将对应的数放在分界值左边或者右边；
  4. 主函数测试；

分步实现

  1. 选定分界值，这是初步的实现，所以我们假定选取数组最右的元素作为分界值，即
    Value=arr[R]；
  2. 设计递归逻辑：当子数组的元素个数只有一个时，退出递归，此时该子数组有序。
public static void process01(int[] arr, int L, int R) {  
    if (L >= R) {  //数据校验+递归结束条件
        return;  
    }  
    int M = partition(arr, L, R);  
    process01(arr, L, M - 1);       //左边有序  
    process01(arr, M + 1, R);       //右边有序  
}
  1. 设计函数“partition” 来实现分界：【
public static int partition(int[] arr, int L, int R) {  
    if (L > R) {  
        return -1;  
    }  
    if (L == R) {       //递归结束条件  
        return L;  
    }  
    int left = L - 1;  
    int index = L;  
    int num = arr[R];  //最后一个元素为分界值
    while (index < R) {  
        if (arr[index] <= num) {  //逻辑1
            swap(arr, ++left, index);  
        }  
        index++;  
    }  
    swap(arr, ++left, R);  //逻辑2
    return left;  
}

public static void swap(int[] arr, int a, int b) {  //交换arr[a]与arr[b]
    if (arr.length - 1 >= Math.max(a, b)) {  
        int swap = arr[a];  
        arr[a] = arr[b];  
        arr[b] = swap;  
    } else {  
        throw new RuntimeException("交换错误");  
    }  
}

分割函数 partition 解读：【

  1. 以 arr[R]为分界值，定义一个左边界（最开始 left 指向-1），辅助指针 index 指向 0；
  2. 当我们碰到比分界值小或相等的数时就让 index++，交换 index 与左边界右边的数（left+1），并且让左边界右移一位——将合理的数的划分到左边界内；如下图所示。（逻辑 1）
    image.png
  3. 当我们碰到比分界值大的数，就直接让 index++，使其处于可交换的状态，且不被划入左边界；（逻辑 1）
  4. 如此循环往复，当 index 到达了数组末尾时，就交换分界值和左边界右边的第一个元素，并右移左边界（++left）（逻辑 2）
  5. 此时数组就已经分割完毕；】 】
  1. 主函数测试：
public static void QuickSort2(int[] arr, int L, int R) {  
    if (L == R) {  
        return;  
    }  
    process01(arr, L, R);  
}

代码变式

毫无疑问，快排的核心功能是通过 partition 实现的，所以我们优化的思路就是更改这个 partition 的逻辑。
例如，原本 partition 是从左边开始的，我们可以改成左右同时开花。此时，两边同时推进，小于区域在左边，大于区域在右边，等于区域也就理所应当处在中间位置。
比原来的分割逻辑好在哪里？ 在经典实现的案例里，如果遇到相同的数，我们默认是一个个移动的，然后把这些数代入递归的过程；而这种方式的 partition 则将相同的数划分在一个区域中，然后在大于区域和小于区域进行递归，一定程度上的节省了资源，增加了效率。
实际上，这也是经典算法题——荷兰国旗问题的经典解法。

Partition 型变式——荷兰国旗问题

问题描述： 现有红白蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。这个问题之所以叫荷兰国旗问题，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。
思路解析：
我们可以把其看成是一个排序的问题，我们需要把红白蓝按照顺序排列好。仅此而已，于是我们就可以运用带快速排序的 partition 来排列。
**代码实现

public static int[] NetherlandsFlag(int[] arr, int L, int R) {  //partition过程
    if (L > R) {  
        return new int[]{-1, -1};  
    }  
    if (L == R) {  
        return new int[]{L, R};  
    }  
    int index = L;  
    int left = L - 1;  
    int right = R;  
    while (index < right) {         //当指针撞到右边的“墙”的时候停下  
        if (arr[index] == arr[R]) {  
            index++;  
        } else if (arr[index] < arr[R]) {  
            swap(arr, ++left, index++);  
        } else {  
            swap(arr, index, --right);  
        }  
    }  
    swap(arr, R, right);  
    return new int[]{left + 1, right};  
}

public static void process02(int[] arr, int L, int R) {  //排序函数
    if (L >= R) {  
        return;  
    }  
    int[] M = NetherlandsFlag(arr, L, R);  
    process02(arr, L, M[0] - 1);  
    process02(arr, M[0] + 1, R);  
}

解读：

  1. 设置左边界（小于区域）开始位于数组第一个元素的左边，下标 left 为 L-1，右边界（大于区域）位于数组最后一个位置，即 R，辅助指针 index 位于 L；
  2. 移动辅助指针，将指向的值依次与分界值 arr[R] 比较：
    1. 相等，index 向后移动——不划入任何的区域（划入相等区域）；
    2. 小于，与左边界右边第一个值（left+1）交换，并且扩大左边界；
    3. 大于，辅助指针不动，将该值与有边界左一个元素（right-1）交换。辅助指针不动是因为，我们并不确定交换过来的值，是否小于 num；
  3. 交换此时右边界的第一个值和分界值 arr[R] ，将这个值最后划入到相等区域中；
  4. 此时小于区域为 [L , left]，相等区域为 [left+1 , right]，大于区域为 [right+1 , R] ；
  5. 结束分割，继续以小于区域和大于区域分别进行递归；

分界值改进

从比较坏的角度上来说，假如我们排序的逻辑是升序，但是很巧的是数组恰好是升序。那么这就意味着，partition 中交换次数将会很多，每次 partition 只完成了一个数的排序，这就意味着其时间复杂度将提升至 O(N2) ，快速排序也就失去了其优势。
故，为了避免以上情况，我们可以考虑让分界值随机化。从正态分布的角度上来说，partition 次数越多，就能够接近中间值，从而有效的改善了数组极端情况的下的表现。
代码实现：

public static void process03(int[] arr, int L, int R) {  
    if (L >= R) {  
        return;  
    }  
    int swap_num = (int) (Math.random() * (R - L + 1));  
    swap(arr, L + swap_num, R);  
    int[] M = NetherlandsFlag(arr, L, R);  
    process03(arr, L, M[0] - 1);  
    process03(arr, M[M.length-1] + 1, R);  
}

解读：

  1. 不用改变什么，只需要将随机确定的分界值与之前确定的分界值进行交换即可。这样就又变成了以最后一个值为分界值了，这样可以以更小的代价修改源码；

模板实现

0785-快速排序