下一个排列

public void nextPermutation(int[] num) {
        if(num == null || num.length <= 1)
            return;
        
        int length = num.length;
        
        int markIndex = length - 1;
        //找不满足递增的点
        while(markIndex > 0 && num[markIndex] <= num[markIndex-1]){
            markIndex--;
        }
        //无递增，代表是全排列第一个输出
        if(markIndex == 0){
            reverse(num);
        }else{
            int j = num.length - 1;
            //找到大于乱序点前一个数的第一个数
            while(num[j] <= num[markIndex-1]){
                j--;
            }
            //交换两数
            swap(num,markIndex-1,j);
            //对交换后乱序点之后的数进行排序，这里是length，因为左闭右开
            Arrays.sort(num,markIndex,length);
        }
    }
    
    public void reverse(int[] num){
        int length = num.length;
        int tmp = 0;
        for(int i = 0 ; i < length/2 ; i++){
            tmp = num[i];
            num[i] = num[length - i - 1];
            num[length - i - 1] = tmp;
        }
    }
    
    public void swap(int[] num,int i,int j){
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }

import java.util.*;
public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length <= 1) {
			return;
		}

		// 从右往左找，相邻的两个增序位置，用 a,b记录
		int a = -1,b = -1,c = -1;
		for (int j = nums.length - 1; j >= 1; j--) {
			if (nums[j] > nums[j - 1]) {
				a = j - 1;
				b = j;
				break;
			}
			// 如果 j == 1,代表整个数组都是降序的，直接返回升序
			if (j == 1) {
				Arrays.sort(nums);
				return;
			}
		}

		// 从 end到b 最小的一个比a大的数
		boolean flag = false;
		for(int j = nums.length - 1; j > a; j--) {
			if (nums[j] > nums[a] && !flag) {
				nums[j] = nums[j] ^ nums[a];
				nums[a] = nums[j] ^ nums[a];
				nums[j] = nums[j] ^ nums[a];
				flag = true;
				continue;
			}
			if (nums[j] < nums[a] && flag) {
				nums[j] = nums[j] ^ nums[a];
				nums[a] = nums[j] ^ nums[a];
				nums[j] = nums[j] ^ nums[a];
			}
		}
		Arrays.sort(nums,b,nums.length);
    }
}

public class Solution {
    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        int index1 = -1;
        for (int i = num.length - 2; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                index1 = i;
                break;
            }
        }
        if (index1 == -1) {
            reverse(num, 0, num.length - 1);
            return;
        }

        int index2 = -1;
        for (int i = num.length - 1; i > index1; i--) {
            if (num[i] > num[index1]) {
                index2 = i;
                break;
            }
        }
        swap(num, index1, index2);
        reverse(num, index1 + 1, num.length - 1);
    }

    public void reverse(int[] num, int i, int j) {
        while (i < j) {
            swap(num, i++, j--);
        }
    }

    public void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
}

import java.util.Arrays;

public class Solution {
    public void nextPermutation(int[] num) {
        if(num.length <= 1)
            return;
        int len = num.length;
        int i = len - 1;
        while(i > 0 && num[i] <= num[i-1]){
            i--;
        }
        if(i == 0){
            Arrays.sort(num);
        }
        else{
            for(int j = len - 1; j >= 0; j--){
                if(num[j] > num[i - 1]){
                    //交换两数
                    int tmp = num[i - 1];
                    num[i - 1] = num[j];
                    num[j] = tmp;
                    Arrays.sort(num, i, len);
                    break;
                }
            }
        }
    }
}

My idea is for an array:

1. Start from its last element, traverse backward to find the first one with index i that satisfy num[i-1] < num[i]. So, elements from num[i] to num[n-1] is reversely sorted.
2. To find the next permutation, we have to swap some numbers at different positions, to minimize the increased amount, we have to make the highest changed position as high as possible. Notice that index larger than or equal to i is not possible as num[i,n-1] is reversely sorted. So, we want to increase the number at index i-1, clearly, swap it with the smallest number between num[i,n-1] that is larger than num[i-1]. For example, original number is 121543321, we want to swap the '1' at position 2 with '2' at position 7.
3. The last step is to make the remaining higher position part as small as possible, we just have to reversely sort the num[i,n-1]

The following is my code:

public void nextPermutation(int[] num) { int n=num.length; if(n<2) return; int index=n-1; while(index>0){ if(num[index-1]<num[index]) break;
        index--;
    } if(index==0){
        reverseSort(num,0,n-1); return;
    } else{ int val=num[index-1]; int j=n-1; while(j>=index){ if(num[j]>val) break;
            j--;
        }
        swap(num,j,index-1);
        reverseSort(num,index,n-1); return;
    }
}

public void swap(int[] num, int i, int j){ int temp=0;
    temp=num[i]; num[i]=num[j]; num[j]=temp;
}

public void reverseSort(int[] num, int start, int end){ if(start>end) return; for(int i=start;i<=(end+start)/2;i++)
        swap(num,i,start+end-i);
}