【leetcode】31. 下一个排列（Java）

题目链接31. 下一个排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。

1、从后面开始找，找到第一个nums[i] > nums[i - 1]
2、从nums[i]之后找到一个第一个比nums[i - 1]大的值与其进行交换;
3、将nums[i - 1]之后的数字重新进行排序;

class Solution {
    public void nextPermutation(int[] nums) {
        int flag = 0;
        //从后向前，找到第一个由大变小的
        for (int i = nums.length - 1; i > 0; i--){
            if (nums[i] > nums[i - 1]){
            	//从后向前，找到第一个比nums[i - 1]大的数，两个进行交换
                for (int j = nums.length - 1; j >= i; j--){
                    if (nums[j] > nums[i - 1]){
                        int tmp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = tmp;
                        //快速排序，这里也可以调用Arrays.sort()
                        quickSort(nums, i, nums.length - 1);
                        return;
                    }
                }
            }
        }
        //如果不存在，就是最大数，重新排列一下
        quickSort(nums, 0, nums.length - 1);
        return;
        
    }
    
	//快速排序，这里也可以调用Arrays.sort()
    public void quickSort(int[] nums, int left, int right){
        if (left >= right) return;
        int l = left, r = right;
        int tmp = nums[l];
        while (l < r){
            while (l < r && nums[r] >= tmp) r--;
            while (l < r && nums[l] <= tmp) l++;
            if (l < r){
                int x = nums[l];
                nums[l] = nums[r];
                nums[r] = x;
            }
        }
        nums[left] = nums[l];
        nums[l] = tmp;
        quickSort(nums, left, l - 1);
        quickSort(nums, l + 1, right);
    }
}