分析

上一篇是全排列的递归解法，现在按照字典序的解法处理：

1,2,3

1,3,2

给出一个数字排列的最小字典序，找到他的下一个字典序， 直到到达最大字典序值

1,2,3->3,2,1 中间的过程即为全排列的过程

字典序含义

从左到右按照位置比较，按照依次增大的顺序排列，例如123，12，21，1，2。的字典序排序后是1，12，123，2，21。

下一个序列

1、从右到左，找到第一个邻位递减的数a

2、找a右边比自己大的，最接近自己的数b

3、交换a,b位置

4、 对b右边的数字从小到大排列，即找到字典序的下一个序列

以数字举例:746532,步骤：

1、找到第一个邻位递减46中的4

2、找到比4大的最小数5

3、交换4，5。即：756432

4、5右边数据排序，即：752346

746532下一个序列就是752346

编码思路

代码及注解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//{1,2,6,5,4,3,0}
public static int[] nextOrder(int[] a) {
    int flag = -1;
    int index = 0;
    for (int i = a.length - 1; i > 0; i--) { //找到第一个邻位递减的， 记录位置index
        if (a[i] > a[i - 1]) {
            flag = a[i - 1];
            index = i - 1;
            break;
        }
    }

    if (flag == -1) { // 没找到下一个， 直接返回自己
       /* for (int i = 0, j = a.length - 1; i < j; i++, j--) {  // 注释部分表示没有下一个 从头开始
            swap(a,i,j);
        }*/
        return a;
    }

    int delta = Integer.MAX_VALUE;
    int indexSwap = 0;
    for (int i = index + 1; i < a.length; i++) { // 找到index之后第一个比index位置值大的索引位置indexswap
        if (a[i] > flag && (a[i] - flag) < delta) {
            delta = (a[i] - flag);
            indexSwap = i;
        }
    }

    swap(a, index, indexSwap); // 交换 index  indexswap 两索引位置的值
    sortIncr(a, index + 1, a.length); // 对index 之后的位置升序排列
    return a;
}

全排列：C2DicOrder.java C3Permutation.java

版权声明：本文为博主原创文章，未经允许不得转载。