荷兰国旗

问题：

对于数组a，数组a中的一个元素k；数组a中小于k的元素放在数组的左边，等于k的元素放在数组中间，大于k的元素放在数组右边。

一、思路

• 设定变量less，more来分别标志小于k的元素范围和大于k的元素范围；
  a[0] ~ a[less]是小于k的元素，a[more] ~ a[a.length - 1]是大于k的元素；
  a[less + 1] ~ a[more - 1]是等于k的元素。
• 将less的初始值设为-1，more的初始值为a.length（表示此时不存在小于/大于区域）；
• 循环遍历数组，开始分类，设i为当前遍历的数组下标，i初始化为0；当i < more时循环继续（当i = more时，排序已经完成了）。遍历会出现3种情况：

1. a[i] < k。此时将a[i++]与a[++less]互换,(将该元素换到小于区)下标前进一位，小于区增加一位。
2. a[i] == k。此时不做交换，(不在小于/大于区就是在等于区)直接i++；下标前进一位，等于区增加一位。
3. a[i] > k。此时a[i]与a[--more]交换(将该元素换到大于区)，i不变动，下标不变（因为a[--more]是未遍历过的数，i不应该变动，要原地对交换过来的数进行判断分类），

二、java代码实现

默认以最后一个数为基准

public class HeLanGuoQi {
    
    public static void f(int[] arrs) {
        if(arrs.length < 2){
            return;
        }
               //基准数
        int x = arrs[arrs.length - 1];
               //左边界（小于区）
        int left = -1;
               //右边界（大于区）
        int right = arrs.length;
        int i = 0;
        while(i < right) {
            if(arrs[i] < x) {
               //小于
                swap(arrs, i++ , ++left);
            }else if(arrs[i] == x) {
               //等于
                i++;
            }else {
               //大于
                swap(arrs, i, --right);
            }
        }
    }
    public static void swap(int[] arrs, int a, int b) {
        int t = arrs[a];
        arrs[a] = arrs[b];
        arrs[b] = t;
    }
}