cite:https://blog.csdn.net/u013457167/article/details/797498821
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21int partition(vector<int> &nums, int begin, int end)
{
int key = nums[begin]; //枢轴(也可以是在begin和end之间的随机数)
// Last position where puts the no_larger element.
//凡是小于key的全部放到数组左端,pos指向<枢轴值的最后一个
//pos++指向不满足条件的（用于交换，将满足条件的换过来)
int pos = begin;
for (int i = begin + 1; i < end; ++i)
{
if (nums[i] < key)
{
pos++;
if (i != pos) //避免自身交换
swap(nums[pos], nums[i]); // 遇到比key小的，就依次放到pos上，然后pos++
}
}
swap(nums[pos], nums[begin]);
return pos;
}