算法分析

假设待全排列元素集合为[1],其中有一个元素1，那么全排列的所有序列为‘1’，如果此时集合为[1,2]也就是增加一个元素2，那么所有可能的序列为'2,1','1,2'。如果此时集合为[1,2,3]，那么所有可能的序列为'3,2,1','2,3,1','2,1,3'和'3,1,2','1,3,2','1,2,3'。通过前面的分析其实很容易看到每增加一个元素，所对应的全排列的所有可能的序列就是在原有基础上的每一个序列的从前到后的位置上依次插入新增元素，当这样操作一遍之后就可以得到所有可能的序列。

Java代码实现

package zhangyuyao.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 全排列
 */
public class Arrangement {


    /**
     * @param args
     */
    public static void main(String[] args) {

        // 创建待测试的数据
        List<Integer> result = new LinkedList<>();

        // 创建待排序元素
        List<Integer> elements = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));

        // 输出排列
        func(result, elements, 0);
    }

    /**
     * @param result
     * @param elements
     * @param index
     * @param <T>
     */
    public static <T> void func(List<T> result, List<T> elements, int index) {
        if (index == elements.size()) {
            printf(result);
            return;
        }

        for (int i = 0; i <= result.size(); i++) {

            // 依次加入到队列中去
            result.add(i, elements.get(index));

            // 递归到下一个数据
            func(result, elements, index + 1);

            // 删除这个元素
            result.remove(i);
        }
    }

    /**
     * 打印结果
     *
     * @param result
     * @param <T>
     */
    private static <T> void printf(List<T> result) {
        StringBuilder sb = new StringBuilder("[");
        for (T t : result) {
            sb.append(t.toString()).append(",");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

递归

简单的理解，递归就是函数调用自身的过程，从结构上来说，递归需要一个递归结束条件，该条件能够终止递归调用，其次对于递归，我的理解是一个有去有回的过程，它能够保存函数上一次调用的信息，当然本质上来说递归也是一种栈结构在方法调用上的实现。需要好好培养一下自己的递归思维，其实就是一种树形思维。