题目

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

分析

寻找一个数组的下一个字典序排列，如果已经是最大了，就给出最小的字典序排列。
我是从后往前升序寻找，直至找到一个前面的数字大于紧挨的后一个数字，这时为了达到字典序的下一个排列，就需要将该数字与数组之后的一个数值稍大的数字交换，并对后面的数字进行快速排序即可。
C代码如下，已通过。

void sort(int *a, int left, int right)//快速排序
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
     
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
         
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
         
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
    }
     
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
void nextPermutation(int* nums, int numsSize) {
    if(numsSize==1)
        return;
    int i=numsSize-2,j=numsSize-1,temp=0,p;
    while(i>=0)
    {
        if(nums[i]>=nums[j])
        {
            i--;
            j--;
        }
        else
            break;
    }
    p=j;
    j++;
    while(j<numsSize)
    {
        if(nums[j]>nums[i]&&nums[j]<nums[p])
            p=j;
        j++;
    }
    if(i>=0)
    {
        temp=nums[i];
        nums[i]=nums[p];
        nums[p]=temp;
        sort(nums,i+1,numsSize-1);
    }
    else
        sort(nums,0,numsSize-1);
    return;
}