1)[ i ] == num ,i++
2) [ i ] < num , [ i ]与 <区 右一个交换,<区右扩 ,i++
3) [ i ] > num , [ i ]与 >区 左一个交换 ,>区左扩 ,i原地不变(因为交换后的那个数还没比较)
当 i 的值比>区的左边界大时 ,结束。
public static void swap(int[]arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; }
public static int partition(int[]arr,int i,int j){ if(L>R) reutrn -1; if(L==R) return L; int lessEqual=L-1; int index=L; while(index<R){ if(arr[index]<=arr[R]) swap(arr,index,++lessEqual); index++; } swap(arr,++lessEqual,R); return lessEqual; }
//荷兰国旗问题 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; while(index<more){ if(arr[index]==arr[R]) index++; else if(arr[index]<arr[R]) swap(arr,index++,++less); else swap(arr,index,--more); } swap(arr,more,R); return new int[]{less+1,more}; }