Let's begin with examples

suppose we want to get the next permutation of [3,1,2], (the answer is [3,2,1])

we first scan from the end of the sequence, in the above example, we scan from 2

we then continue scan the sequence from right to left, and want to find the first number smaller than 2, we then find 1

swap them, the sequence now becomes [3,2,1], it is correct.

Then, consider the sequence [2,3,1] (the answer if [3,1,2]), if we apply the above strategy, we get [3,2,1], it is wrong, let us revisit our above strategy.

After scanning, we get a sequence [3,2,1], we find that if we sort [2,1] in increasing order, we can get the correct answer, we edit our code and summit to leetcode, unfortunately, we get the wrong answer for the sequence [4,2,0,2,3,2] (the answer is [4,2,0,3,2,2]).

Applying our strategy to the above sequence, we get [4,2,2,2,3,0], sort it and get [4,2,2,0,2,3], the gap between our solution and the answer is that we only check 2 (the last element), and find the first number that is smaller than it, we ignore the situation that there exist a sequence [ai,aj,ak,am] such that ai < aj,ak,am, am < aj,ak, aj<ak, this observation tells us we have to check it more than once.

Thus, we can write the following code:

```
class Solution {
public:
// quick sort
int median3( vector<int> & v, int left, int right ){
int mid = left + (right-left)/2;
if(v[mid] < v[left])
swap(v[mid],v[left]);
if(v[right] < v[left])
swap(v[right],v[left]);
if(v[right] < v[mid])
swap(v[right],v[mid]);
swap(v[right-1],v[mid]);
return v[right-1];
}
void quickSort(vector<int> & v, int left, int right){
if( left < right ){
int pivot = median3(v,left,right);
int i = left;
int j = right-1;
while(i<j){
while(i<j && v[++i] < pivot);
while(i<j && v[--j] > pivot);
if(i<j)
swap(v[i],v[j]);
else
break;
}
swap(v[i],v[right-1]);
quickSort(v,left,i-1);
quickSort(v,i+1,right);
}
}
// main function
void nextPermutation(vector<int>& nums){
int find = 0; // record find or not
int prePos = INT_MIN;
int index = -1;
for( int i = nums.size()-1; i > 0; i-- ){
for( int j = i-1; j >= 0; j-- ){
if( nums[i] > nums[j] && j > prePos){
find = 1;
prePos = j;
index = i;
}
}
}
if(!find){ // not find, must be decreasing sequence, i.e. [6,5,4,3,2,1]
for( int i = 0; i < nums.size()/2; i++ )
swap(nums[i],nums[nums.size()-i-1]);
return;
}
swap(nums[index],nums[prePos]);
quickSort(nums,prePos+1,nums.size()-1);
}
};
```