荷兰国旗问题以及快速排序算法-数据结构java快速排序

大家好，我是周一。
最近几篇算法，我们都是聊的归并排序，归并排序也说的差不多了，今天聊聊快速排序。
一、荷兰国旗问题 1、啥是荷兰国旗问题荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：

文章图片

假设这样的条纹有多条，且各种颜色的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但不仅仅只有这一种情况：

文章图片

需求是：把这些条纹按照颜色排好，红色的在上半部分，白色的在中间部分，蓝色的在下半部分，我们把这类问题称作荷兰国旗问题。
2、荷兰国旗问题的抽象我们把荷兰国旗问题抽象成数组的形式是下面这样的：
给定一个整数数组和一个值M（存在于原数组中），要求把数组中小于M的元素放到数组的左边，等于M的元素放到数组的中间，大于M的元素放到数组的右边，最终返回一个整数数组，只有两个值，0位置是等于M的数组部分的左下标值、1位置是等于M的数组部分的右下标值。
进一步抽象为更加通用的形式是下面这样的：
给定数组arr，将[l, r]范围内的数（当然默认是 [ 0 - arr.length - 1 ]），小于arr[r]（这里直接取数组最右边的值进行比较）放到数组左边，等于arr[r]放到数组中间，大于arr[r]放到数组右边。最后返回等于arr[r]的左, 右下标值。
3、解决的思路定义一个小于区，一个大于区；遍历数组，挨个和arr[r]比较，
（1）小于arr[r]，与小于区的后一个位置交换，当前位置后移；
（2）等于arr[r]，当前位置直接后移；
（3）大于arr[r]，与大于区的前一个位置交换，当前位置不动（交换到此位置的数还没比较过，所以不动）。
遍历完后，arr[r]和大于区的最左侧位置交换。
最后返回，此时小于区的后一个位置，大于区的位置，即是最后的等于arr[r]的左, 右下标值。
4、详细的参考代码

/** * 荷兰国旗问题 * * 把数组arr中，[l, r]范围内的数，小于arr[r]放到数组最左边，等于arr[r]放到数组中间，大于arr[r]放到数组最右边 * * @return 返回等于arr[r]的左, 右下标值 */ public static int[] netherlandsFlag(int[] arr, int l, int r) { if (l > r) { return new int[]{-1, -1}; } if (l == r) { return new int[]{l, r}; } // 小于arr[r]的右边界，从L的左边一位开始 int less = l - 1; // 大于arr[r]的左边界，从r开始，即当前右边界里已经有arr[r] int more = r; // 当前正在比较的下标 int index = l; // 不能与大于arr[r]的左边界撞上 while (index < more) { if (arr[index] < arr[r]) { // 小于时，将当前位置的数和小于arr[r]的右边界的下一个位置交换 // 当前位置后移一位 swap(arr, index++, ++less); } else if (arr[index] == arr[r]) { // 等于时，当前位置后移一位即可 index++; } else { // 大于时，当前位置的数和大于arr[r]的左边界的前一个位置交换 // 当前位置不动 swap(arr, index, --more); } } // 将arr[r]位置的数和大于arr[r]的左边界的数交换 // 此时整个数组就按照小于、等于、大于arr[r] 分成了左中右三块 swap(arr, more, r); // 最后整个数组中，等于arr[r]的左右边界分别是less + 1, more return new int[]{less + 1, more}; }

二、快速排序 1、啥是快排（排序流程）首先设定一个分界值，通过该分界值将数组分成左中右三部分。
（1）将小于分界值的数据集中到数组的左边，等于分界值的数据集中到数组的中间，大于分界值的数据集中到数组右边。
（2）然后，左边和右边的数据可以独立排序。对于左侧的数据，又可以取一个分界值，将该部分数据分成左中右三部分，同样在左边放较小值，中间放等于值，右边放较大值。右边数据也做同样的处理。
（3）重复上述过程，可以看出，这是一个递归过程。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
当看完了快排的流程，是不是发现快排的核心方法就是荷兰国旗问题，所以知道为啥本文一开始就介绍荷兰国旗问题了吧。
2、抽象后的快排流程（1）随机将数组中的某个数放到比较位置上（即最右侧位置）
（2）调用荷兰国旗方法，（此时等于区的数即在最后排好序的位置上），拿到等于区的左右下标
【荷兰国旗问题以及快速排序】（3）小于区和大于区再各自递归调用（1）（2）步即可将小于区和大于区排好序。
3、详细的参考代码

/** * 随机快排 */ public static void quickSortRandom(int[] arr) { if (arr == null || arr.length < 2) { return; } processRandom(arr, 0, arr.length - 1); }private static void processRandom(int[] arr, int l, int r) { if (l >= r) { return; } // 随机将数组中的某个数放到比较位置上（即数组最右边位置） // 这一步是保证快排时间复杂度是O(N*logN)的关键，不然，快排的时间复杂度是O(N^2) swap(arr, l + (int) ((r - l + 1) * Math.random()), r); // 将数组划分为小于、等于、大于arr[r] 的左中右三块 int[] equalArea = netherlandsFlag(arr, l, r); // 此时等于区域的值已经处于最后排序结果的位置了 // 递归将左半部分的排好序 processRandom(arr, l, equalArea[0] - 1); // 递归将右半部分的排好序 processRandom(arr, equalArea[1] + 1, r); }public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }