問題：
對于數(shù)組a，數(shù)組a中的一個元素k骄噪；數(shù)組a中小于k的元素放在數(shù)組的左邊躬翁，等于k的元素放在數(shù)組中間拜轨，大于k的元素放在數(shù)組右邊。
一祥得、思路
- 設定變量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（表示此時不存在小于/大于區(qū)域）怕吴；
- 循環(huán)遍歷數(shù)組，開始分類县踢，設i為當前遍歷的數(shù)組下標转绷，i初始化為0；當i < more時循環(huán)繼續(xù)（當i = more時硼啤，排序已經(jīng)完成了）议经。遍歷會出現(xiàn)3種情況：
- a[i] < k。此時將a[i++]與a[++less]互換,(將該元素換到小于區(qū))下標前進一位谴返，小于區(qū)增加一位煞肾。
- a[i] == k。此時不做交換亏镰，(不在小于/大于區(qū)就是在等于區(qū))直接i++扯旷；下標前進一位拯爽，等于區(qū)增加一位索抓。
- a[i] > k。此時a[i]與a[--more]交換(將該元素換到大于區(qū))毯炮，i不變動逼肯，下標不變（因為a[--more]是未遍歷過的數(shù)，i不應該變動桃煎，要原地對交換過來的數(shù)進行判斷分類）篮幢，
二、java代碼實現(xiàn)
默認以最后一個數(shù)為基準
public class HeLanGuoQi {
public static void f(int[] arrs) {
if(arrs.length < 2){
return;
}
//基準數(shù)
int x = arrs[arrs.length - 1];
//左邊界（小于區(qū)）
int left = -1;
//右邊界（大于區(qū)）
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;
}
}
