题意：给定一个数组，要求找出全排列的下一个排列，如[1,2,3]的下一个排列是[1,3,2]。

31. Next Permutation (opens new window)

比较数学的题目，先要找到要被交换的下标i，满足nums[i]<nums[i+1],i和它右边的某个下标j交换，j应该是比i大但是是在右边所有数字中的最小值。最后对i右边的数字做升序排序。因为在第一步找i的过程中已经i右边的数字是降序的，i和j交换后还是降序的。所以排序时直接左右交换即可。

class Solution {
    public void nextPermutation(int[] nums) {
        int i;
        // 找出第一个下标i，nums[i] < nums[i+1]
        for (i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                break;
            }
        }
        if (i >= 0) {
            // 找出i右边比nums[i]大的最小值
            int j;
            for (j = nums.length - 1; j > i; j--) {
                if (nums[i] < nums[j]) {
                    break;
                }
            }
            // 交换i和j
            swap(nums, i, j);
        }
        // i右边升序排序
        for (int k = i + 1, p = nums.length - 1; k < p; k++, p--) {
            swap(nums, k, p);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}