class Solution {
    public void nextPermutation(int[] nums) {
        //Arrays.sort(int[] nums, int fromIndex, int toIndex) 这个方法对nums中的fromIndex到toIndex - 1的部分进行排序
        // 从后向前遍历，一旦出现一个数大于前面的数，说明存在更大的数，记录该索引i
        // 下一个更大的数是，后面的数按从小到大排，将后面的数中第一个比i-1 大的数据与之交换
       int n = nums.length;
       for (int i = n - 1; i >= 0; i--) {
            if (i == 0) {
                Arrays.sort(nums);  //当前排序是最大排序，返回最小排序
            } else if (nums[i] > nums[i-1]) {  //nums[i] > nums[i-1] 说明存在下一个更大的排列
                Arrays.sort(nums, i, n);      //并且nums[i]之后的部分满足最大排列，下一个更大的排列，即对nums[i]和之后的部分排序 
                for (int index = i; index < n; index++) {  // 并取出第一个比nums[i-1]大的部分，进行交换
                    if (nums[index] > nums[i-1]) {
                        int temp = nums[i - 1];
                        nums[i - 1] = nums[index];
                        nums[index] = temp;
                        return;
                    }
                }
            }
       }
 }
}