Next Permutation 全排列

mplement 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

全排列的问题，根据当前的序列，返回下一个紧邻它的全排列。我们可以从当前序列的最后一个数字开始往前比较，找到一个数字比紧邻它的后面的数字小的位置，记为i, 此时i位置上的数字比
i+1位置上的数字小，如果将这两个数字交换，这个全排列肯定在当前序列的后面，但不能保证是紧邻的，例如当前序列为12365，我们从后面开始找，5小于6 ，如果交换后为12356，这个序列肯定在当前序列的后面；继续往前找，6大于3，交换后的序列为12635，在当前序列的后面，但是不是紧邻当前序列的，我们想要的结果为12536。因此我们找到第一个f(i) < f(i + 1)的位置后，还要把f(i)元素与f(i + 1)后面的元素进行比较，找到第一个比f(i)大的元素f(x), 然后将f(x)与f(i)交换，再将i 后面的元素排列，就得到了结果。代码如下：

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 0) return;
        for(int i = nums.length - 1; i > 0; i--) {
            if(nums[i] > nums[i - 1]) {
                int j = nums.length - 1;
                while(j > i - 1 && nums[j] <= nums[i - 1]) j --;
                int tem = nums[i - 1];
                nums[i - 1] = nums[j];
                nums[j] = tem;
                java.util.Arrays.sort(nums, i, nums.length);
                return;
            }
        }
        //当前序列为321这种情况时
        reverse(nums);
    }
    public void reverse(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while(l < r) {
            int tem = nums[l];
            nums[l++]= nums[r];
            nums[r--] = tem;
        }
    }
}