[数据结构与算法]java解决全排序问题

1. 说明：
   • 这里的用例是数字数组。
   • 全排序样式如; 数组[ 1,1,3]
     他的全排序为：[1,1,3] , [1,3,1] ,[3,1,1]
2. 对于全排序最简单的做法就是通过循环迭代去实现，思想是：

将所有的不同下标的数字都视为不一样的个体。然后用循环，每一个作为一次第一个元素，然后去排序其他的个体。在最里面的循环体中编成一个新的数组，并加入我们的设置的全局变量二维数组中存储起来，最后去重皆可。

如果我们数组长为n，那么需要最大的时间为; n的n次方，最小为 n!
很显然这样做需要使用到大量的嵌套循环去实现，代码量大，而且耗时长。

3. 这里介绍一种递归的方法
   他计算使用到的时间为：n的平方

	public List<List<Integer>> sort(int[] num){
		//这里实例化一个二维数组存储最终数据,将temp添加进来
		List<List<Integer>> res = new ArrayList<>();
		//这里实例化一个一维数组保存排序好的num
		List<Integer> temp = new ArrayList<>();
		
		helder(num,res, temp, 0);
		return res;
	}
	public void helder(int[] num,List<List<Integer>> res,List<Integer> temp,int index) {
		//如果index>=num.lenght的时候就将temp加入到二维列表中
		if(index >= num.length) {
			res.add(temp);
		}
		//HashSet实现了Set接口，add一个元素时，先获取元素的哈希值，达到去重的效果
		Set<Integer> set = new HashSet<Integer>();
		for(int i = index; i < num.length; i++) {
			//如果set已经包含了num[i]那么就之间跳过
			if(set.contains(num[i])) {
				continue;
			}
			//如果不重复那么更新temp的值和set的值
			set.add(num[i]);
			temp.add(num[i]);
			//添加完毕之后我们给num的第i个和第index个数据交换位置，更新num
			wrap(num, index, i);
			helder(num, res, temp, index+1);
			//做完一次排序将temp的第index个数字移除进行下一个排序
			temp.remove(index);
			wrap(num, index, i);
			
		}
	}
	public void wrap(int[] num,int i ,int j) {
		int x = num[i];
		num[i] = num[j];
		num[j] = x;
	}