寻找给定排列的下一个更大的排列

题目描述
实现函数next permutation（下一个排列）：将排列中的数字重新排列成字典序中的下一个更大的排列。将排列中的数字重新排列成字典序中的下一个更大的排列。如果不存在这样的排列，则将其排列为字典序最小的排列（升序排列）。需要使用原地算法来解决这个问题，不能申请额外的内存空间。下面有几组样例，左边是输入的数据，右边是输出的答案：
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1
思路分析
要寻找给定的已知排列的下一个更大的排列，我们可以把给定的排列分为两个部分：从最后一个数往前的一个降序子序列和剩下的序列部分，由于后半部分是降序的了，就那么些个数字排列已经得到了最大的排列了，接着求给定序列的下一个更大的排列，把降序子序列的前一个数字和后面降序子序列当中大于该数字的第一个数字进行交换，这样就可以得到一个更大的序列，但是为了得到更大的排列，这时通过前面的交换得到的可能是大很多的排列，我们就继续在前面得到的降序子序列中继续前面的操作，直到降序子序列的长度为1就结束。注意这里还有一个问题，得到的降序子序列可能是整个序列，也就是说整个序列都是降序的，这种情况要单独处理，将其变成最小的排列返回。
举例分析
假如给定的序列是 {1,7,6,5,4} ，理应输出的下一个更大的排列是{4,1,5,6,7} 下面分析怎么得到的？首先，{1,7,6,5,4}从最后一个元素寻找降序子序列得到{7,6,5,4}，然后将降序子序列的前一个元素1和子序列中大于1的第一个数字4交换得到序列{4,7,6,5,1}，接着在序列{7,6,5,1}中寻找降序子序列，发现整个序列都是降序的，那么就特殊处理得到最小排列{1,5,6,7}，再加上前面的数字4得到最后的排列{4,1,5,6,7}；
再比如给定的序列是{5,7,6,4,3}，理应输出的下一个更大的排列是{6,3,4,5,7} 下面分析如何得到的？首先，{5,7,6,4,3}从最后一个元素寻找降序子序列得到{7,6,4,3}，然后将降序子序列的前一个元素5和子序列中大于5的第一个数字6交换得到序列{6,7,5,4,3}，接着在序列{7,5,4,3}中寻找降序子序列，发现整个序列都是降序的，那么就特殊处理得到最小排列{3,4,5,7}，再加上前面的数字4得到最后的排列{6,3,4,5,7}；
代码如下

    void nextPermutation(vector<int> &num) 
    {
        int len=num.size(); //记录给定排列的长度
        if(len<2) //长度小于2就可以直接返回，不需要发生变化
            return;
        int i=0,j=len-1;
        while(j>i) //从最后一个元素开始寻找降序子序列
        {
            if(num[j]<=num[j-1])
                --j;
            else
                break;
        }
        if(j==0) //完全降序序列
        {
            for(int k=0;k<(len>>1);++k)
                swap(num[k],num[len-1-k]);
        }
        else //不是完全降序序列
        {
            while(j<len)
            {
                i=j-1; //此时j指向了降序序列的第一个元素,而i指向前一个元素
                while(j<len && num[j]>num[i]) //寻找降序子序列中第一个大于num[i]的数
                    ++j;
                swap(num[i],num[j-1]); //交换
                ++i; //后延一个元素,接着在降序子序列中进行操作
                j=len-1;
                while(j>i)
                {
                    if(num[j]<=num[j-1])
                        --j;
                    else
                        break;
                }
                if(j==i) //完全降序序列
                {
                    for(int k=i;k<=((i+len-1)>>1);++k)
                        swap(num[k],num[i+len-1-k]);
                    break;
                }
                if(j==len-1) //如果最后只剩下一个元素就退出循环，操作结束
                    break;
            }
        }
    }