Partition
小于等于區(qū)，大于區(qū)域
當(dāng)前值下標(biāo)固耘，小于等于區(qū)域邊界下標(biāo)
當(dāng)前值小于等于劃分值题篷，交換當(dāng)前值，與小于等于區(qū)域下標(biāo)厅目， 當(dāng)前值下標(biāo)++番枚，小于等于下標(biāo)++
當(dāng)前值大于劃分值，跳過
時間O(N)损敷，額外空間O(1)
擴展：荷蘭國旗問題
1）當(dāng)前數(shù)等于劃分值葫笼，跳下一個
2）當(dāng)前數(shù)小于劃分值，和小于區(qū)換嗤锉，小于區(qū)擴渔欢，跳下一個
3）當(dāng)前數(shù)大于劃分值墓塌，和大于區(qū)換瘟忱，大于區(qū)擴，當(dāng)前值不變
當(dāng)前數(shù)遇到大于區(qū)位置苫幢，停止
public static void partition(int[] arr, int start ,int end, int value) {
int lessIndex = start - 1;
int largerIndex = end + 1;
while(start < largerIndex) {
if(arr[start] < value) {
swap(arr, ++lessIndex, start++);
}else if(arr[start] > value) {
swap(arr,--largerIndex,start);
}else {
start++;
}
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
