1.理解partion

将数组分成两部分，左边大于等于n，右边大于n，（这两个区间内部可以无序），要求额外空间复杂度O（1），时间复杂度O（n）。
方法：<=区开始索引为-1
（1) arr[i] <=n时，当前数和<=区的下一个交换，<=区右扩，i++
(2) 否则i++

2.将上述问题分成小于，等于，大于三个区

定义小于区，索引为-1，大于区索引定义为arr.length
（1）arr[i]==n,i++
(2）arr[i] <n, 当前数和小于区下一个右一个交换，<区右扩，i++
（3）arr[i]>n,当前数与大于区左一个交换，大于区左扩，i不动
停止条件为i和大于区域边界撞上

3.荷兰国旗划分

数组，每次以最后一个位置R做划分，返回等于区的左边界和右边界。
步骤：（1）让大于区起始位置在R，而不是R的后一个，这样是为了保证先不让其受到影响。
（2）按照上一个进行处理，最后将R与大于区的左边界（more）进行交换,返回等于区的左边界（less+1）和右边界（more）。

4.快排

以随机选的数，跟R做交换。然后同荷兰国旗划分。

4.1代码示例

public class Test {
   public static void main(String[] args)  {
       int[] a = {12,5,3,89,54,37};
       quicksort(a);
       for (int x:a
            ) {
           System.out.print(x+" ");
       }
   }
  public static void quicksort(int[] arr){
       if(arr==null || arr.length<2)
           return;
       process(arr,0,arr.length-1);
  }
  public static void process(int[] arr, int L, int R){
       if(L>=R)
           return;
       swap(arr,L+(int)(Math.random()*(R-L+1)),R);
       int[] equalArea= netherLandsFlag(arr,L,R);
       process(arr,L,equalArea[0]-1);
       process(arr,equalArea[1]+1,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};
       int less = L-1;
       int more = R;
       int i = L;
       while (i<more) { //i小于大的左边界
           if(arr[i]<arr[R])
               swap(arr,i++,++less);
           else if(arr[i]==arr[R])
               i++;
           else
               swap(arr,i,--more);
       }
       swap(arr,more,R); //左边界和最后的R交换
      return new int[]{less+1,more};
  }
  public static void swap(int[] arr, int L, int R){
       int tmp = arr[L];
       arr[L]=arr[R];
       arr[R] = tmp;
  }
}