荷兰为什么设置三色旗（那不是快速排序的前置知识吗）

#创作挑战赛#

  这节学习一下荷兰旗问题，为学习快排打一个基础。

  荷兰旗我还没见过呢？赶紧搜一下瞅瞅：

  这就是荷兰旗，三色啊那啥叫荷兰旗问题呢，来个例子，我有一个数组arr，还有一个数X，数组中所有小于X的放数组左边，等于X的放数组中间，大于X的放数组右边，这就是荷兰旗问题。

  造一个题呗，图来

  暴力思路来一次

  整理下：

• 有个交换动作，来个swap
• 我需要左边界L
• 我需要右边界R
• 考虑边界L>=R

  话不多说，贴上代码：

/** * arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值 <arr[R] ==arr[R] > arr[R] * * @param arr 数组 * @param L 左边界 * @param R 右边界 * @return 下标范围 */ public static int[] netherlandsFlag(int[] arr, int L, int R) { if (L > R) { // L...R L>R，不是有效范围 return new int[] { -1, -1 }; } if (L == R) { return new int[] { L, R }; } // 可以从初始位理解，刚开始的时候，左边界还没有右扩，所以less是L-1 int less = L - 1; // < 区 右边界 int more = R; // > 区 左边界 int index = L; // 当前数的位置，不能和 右区的左边界撞上 while (index < more) { if (arr[index] == arr[R]) {// 当前位置的数 和 目标数 相等的时候跳过 index ; } else if (arr[index] < arr[R]) {// 当前位置的数 小于 目标数 // 当前位置的数 和 L 1的数交换，然后位置右移，左边界右移 swap(arr, index , less); } else { // > // 当前位置的数 和 R-1的数交换，然后位置不变，右边界左移 swap(arr, index, --more); } } //more是右边界-1的位置，和R交换 swap(arr, more, R); // <[R] =[R] >[R] //等于区域的第一个数的位置，和等于区域的最后一个数的位置 return new int[] { less 1, more }; }