int partition(vector<int>& nums, int i, int j) {
int pivot = i++;
while (true) {
while (i <= j && nums[i] <= nums[pivot]) ++i; //a
while (j >= i && nums[j] >= nums[pivot]) --j; //b
if (i > j) {
break;
}
int t = nums[i]; nums[i++] = nums[j]; nums[j--] = t; //c
}
int t = nums[j]; nums[j] = nums[pivot]; nums[pivot] = t;
return j;
}
上面這段代碼里，細(xì)節(jié)太多太多，居然搞了一晚上才搞出來，總的來說大方向上：
1. 要確保最后能i > j才能終止（其實(shí)終止的時(shí)候，是一定滿足j + 1 == i的）；
2. 因?yàn)楸Ａ舻氖亲钭髠?cè)的數(shù)為基準(zhǔn)，排序目標(biāo)是從左到右按照從小到大排，因此最后要把pivot和j交換；
3. //a和//b里，其實(shí)只要有一個(gè)nums[i]/nums[j]和nums[pivot]的等于判斷就可以了，這里為了一致性，都保留了對等于的判斷；
4. //c里增加了i和j各自挪一步的操作，因此如下寫法更好：
int partition(vector<int>& nums, int i, int j) {
int pivot = i++;
while (true) {
while (i <= j && nums[i] <= nums[pivot]) ++i;
while (j >= i && nums[j] >= nums[pivot]) --j;
if (i > j) {
break;
}
swap(nums[i++], nums[j--]);
}
swap(nums[pivot], nums[j]);
return j;
}