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;
}
上面这段代码里，细节太多太多，居然搞了一晚上才搞出来，总的来说大方向上：
1. 要确保最后能i > j才能终止（其实终止的时候，是一定满足j + 1 == i的）；
2. 因为保留的是最左侧的数为基准，排序目标是从左到右按照从小到大排，因此最后要把pivot和j交换；
3. //a和//b里，其实只要有一个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;
}