1.理解partion
將數(shù)組分成兩部分削彬，左邊大于等于n森书，右邊大于n，（這兩個(gè)區(qū)間內(nèi)部可以無(wú)序）戏锹，要求額外空間復(fù)雜度O（1）冠胯，時(shí)間復(fù)雜度O（n）。
方法：<=區(qū)開始索引為-1
（1) arr[i] <=n時(shí)锦针，當(dāng)前數(shù)和<=區(qū)的下一個(gè)交換荠察，<=區(qū)右擴(kuò)，i++
(2) 否則i++
2.將上述問(wèn)題分成小于奈搜，等于悉盆，大于三個(gè)區(qū)
定義小于區(qū)，索引為-1馋吗，大于區(qū)索引定義為arr.length
（1）arr[i]==n,i++
(2）arr[i] <n, 當(dāng)前數(shù)和小于區(qū)下一個(gè)右一個(gè)交換焕盟，<區(qū)右擴(kuò)，i++
（3）arr[i]>n,當(dāng)前數(shù)與大于區(qū)左一個(gè)交換宏粤，大于區(qū)左擴(kuò)脚翘，i不動(dòng)
停止條件為i和大于區(qū)域邊界撞上
3.荷蘭國(guó)旗劃分
數(shù)組，每次以最后一個(gè)位置R做劃分绍哎，返回等于區(qū)的左邊界和右邊界来农。
步驟：（1）讓大于區(qū)起始位置在R，而不是R的后一個(gè)崇堰，這樣是為了保證先不讓其受到影響沃于。
（2）按照上一個(gè)進(jìn)行處理，最后將R與大于區(qū)的左邊界（more）進(jìn)行交換,返回等于區(qū)的左邊界（less+1）和右邊界（more）海诲。
4.快排
以隨機(jī)選的數(shù)繁莹，跟R做交換。然后同荷蘭國(guó)旗劃分特幔。
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; } }
