NextPermutation.java

public class NextPermutation{
    public void nextPermutation(int[] num) {
        if(num == null || num.length == 0) return;
        
        int len = num.length;
        if(len == 1) return;
        
        int i = len - 2;
        while(i >= 0 && num[i] >= num[i+1]) i--;
        if(i >= 0){
            int ceilingIndex = findCeiling(num, num[i], i+1, len-1);
            swap(num, i, ceilingIndex);
        }
        // I used to sort this part. No need at all. They are always in descending order
        // if they are not, we will not be at the current switch point.
        reverse(num, i+1, len-1); 
    }
    
    private int findCeiling(int[] num, int target, int low, int high){ 
        int j = high;
        while(j >= low && target >= num[j]) j--; // be sure to use >=
        return j;
    }
    
    private void reverse(int[] num, int left, int right){
        while(left <= right) swap(num, left++, right--);
    }
    
    private void swap(int[] num, int i, int j){
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}