下一个排列

难度: 中等

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即,组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

示例1:

输入: nums = [1,2,3]
输出: [1,3,2]

示例2:

输入: nums = [3,2,1]
输出: [1,2,3]

示例3:

输入: nums = [1,1,5]
输出: [1,5,1]

示例4:

输入: nums = [1]
输出: [1]

提示:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

解题思路：

下一个更大的排序首先要更大比如 123
因此我们只需要将后面的大数和前面的小数交换位置即可 即将2和3交换下
要注意：因为是下一个最大序列，因此不能随便交换，要保证是下一个也就是最临近的比如
序列：321 312 213 231 都比 123大
而123最近的肯定是132
因此我们就要从数字最后一位开始往前找，找到一个大于自己前一位的就开始做交换
然后把后面的全部从小到大排序即可，比如157643下一个就是163457
过程就是从最后一位开始也就是3开始往前找找到一位他的前面一位要小于它，就会找到7的前面是5是小于它

从找到的这位7开始，后面一串中找到大于5的最小数，也就是6将6和5交换就变成了167543

然后把i后面的数字从小到大排序，其实可以发现后面7543已经是个从大到小的排序了，因此从i+1开始往后（也就是7）和从最后开始往前两两交换即可

有个极限条件就是本身就是最大序列比如321那么也就是从最后一位找到最开始都没找到前一位比它小的，那么就直接从小到大全排序即可

void nextPermutation(int* nums, int numsSize){
    for(int i=numsSize-1;i>0;i--){ //没找到，说明本身是最大排序
        if(i==1&&nums[i]<nums[i-1]){
            i--;
            while(i<numsSize/2){
                nums[i] = nums[i] + nums[numsSize-1-i];
                nums[numsSize-1-i] = nums[i] - nums[numsSize-1-i];
                nums[i] = nums[i] - nums[numsSize-1-i];
                i++;
            }
            break;
        }
        if(nums[i]>nums[i-1]){ //往前找找到前面一位小于
            i--; //找到后把前面一位标记为i
            for(int j=numsSize-1;j>=i;j--){ 
                if(nums[j]>nums[i]){//找后面大于i的最小数，和i交换
                nums[i] = nums[i] + nums[j];
                nums[j] = nums[i] - nums[j];
                nums[i] = nums[i] - nums[j];
                break; 
                }
            }
            i++;
            for(int j=0;j<(numsSize-i)/2;j++){ //从i开始交换排序，把从大到小变成从小到大
                nums[i+j] = nums[i+j] + nums[numsSize-1-j];
                nums[numsSize-j-1] = nums[i+j] - nums[numsSize-j-1];
                nums[i+j] = nums[i+j] - nums[numsSize-j-1];
            }
            break;
        }
    }
}