首页 > 代码库 > 我的算法学习(一)----数组的全排列

我的算法学习(一)----数组的全排列

看见别人写出来美丽有用的代码,最终下定决心好好学习算法,在这里记录下自己学习的成果。

前两天看到数组的全排列,于是自己照着别人的想法实现了一下,感觉自己理解了,有点小高兴,记载一下。

/*
 * 数组的全排列*/
public class myAllSort {
	public static void sort(int[] number,int start,int end){
		
		int temp;
//		假设发现数组对掉元素到了最后一个,那么就输出,证明已经符合要求
		if(start==end)
		{
			print(number);
		}
//		依次将数组的第一个元素和后面的元素一一对调,然后第一次对掉之后递归,
//		将数组的第二个元素和他之后的元素对掉,最后一次进行
		/*
		 * 1  2  3  4-->1 2 3 4-->1 2 3 4
		 * 				    1 2 4 3
		 * 			  1 3 2 4-->1 3 2 4
		 * 				    1 3 4 2
		 *  			  1 4 3 2-->1 4 3 2
		 *  				    1 4 2 3
		 * 2  1  3  4
		 * 3  2  1  4
		 * 4  2  3  1
		 * */
		for(int i=start;i<end;i++){
			
			temp = number[start];
			number[start] = number[i];
			number[i] = temp;
			
			sort(number,start+1,end);
//			print(number);			//输出排序的全过程
//			将对掉之后的数组便会原来的顺序,以便下次
			temp = number[start];
			number[start] = number[i];
			number[i] = temp;
//			

		}		
	}
	public static void print(int[] number){
		for(int i=0;i<number.length;i++)
		{
			System.out.print(number[i]+"--");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		int[] number = {1,2,3,4};
		sort(number,0,number.length);

	}
}
另一种数组的选择排序方法,感觉这个思想对我非常实用,详细的出处给忘了。

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

/* 
 * 从属注重选择几个数字进行排列
 * 比如:五个选三个的全排列
 * 算法原理:在数组中选取一个数字先存储到集合中,然后再依次选取其它数字,
 * */
public class ChooseServalFromNumber {
	public static final int  NUM = 4;
	
	
	public static void main(String[] args) {
		Object[] obj = new String[]{"1","2","3","4"};
		List<Object> list = Arrays.asList(obj);
		chooseNumberSort(list,new ArrayList<Object>());
	}
	public static void chooseNumberSort(List<Object> list,List<Object> target){
//		假设目标集合中的数字达到了我们需求的个数就输出
//		if(target.size()==NUM)
//			System.out.println(target+"--");
		
		if(target.size()==4)
			System.out.println(list+"  -->  "+target+"--输出");
//		else			
//			System.out.println(list+"  -->  "+target);
		
		
		for(int i=0;i<list.size();i++){
			List<Object> newList = new ArrayList<Object>(list);
			List<Object> newTarget = new ArrayList<Object>(target);
			newTarget.add(newList.get(i));
			newList.remove(i);
			
			System.out.println(list+"  -->  "+target);
			
			chooseNumberSort(newList,newTarget);
		}
	}
}
/*
    输出结果:
[1, 2, 3, 4]  -->  []
[2, 3, 4]  -->  [1]
[3, 4]  -->  [1, 2]
[4]  -->  [1, 2, 3]
[]  -->  [1, 2, 3, 4]--输出
[3, 4]  -->  [1, 2]
[3]  -->  [1, 2, 4]
[]  -->  [1, 2, 4, 3]--输出
[2, 3, 4]  -->  [1]
[2, 4]  -->  [1, 3]
[4]  -->  [1, 3, 2]
[]  -->  [1, 3, 2, 4]--输出
[2, 4]  -->  [1, 3]
[2]  -->  [1, 3, 4]
[]  -->  [1, 3, 4, 2]--输出
[2, 3, 4]  -->  [1]
[2, 3]  -->  [1, 4]
[3]  -->  [1, 4, 2]
[]  -->  [1, 4, 2, 3]--输出
[2, 3]  -->  [1, 4]
[2]  -->  [1, 4, 3]
[]  -->  [1, 4, 3, 2]--输出
[1, 2, 3, 4]  -->  []
[1, 3, 4]  -->  [2]
[3, 4]  -->  [2, 1]
[4]  -->  [2, 1, 3]
[]  -->  [2, 1, 3, 4]--输出
[3, 4]  -->  [2, 1]
[3]  -->  [2, 1, 4]
[]  -->  [2, 1, 4, 3]--输出
[1, 3, 4]  -->  [2]
[1, 4]  -->  [2, 3]
[4]  -->  [2, 3, 1]
[]  -->  [2, 3, 1, 4]--输出
[1, 4]  -->  [2, 3]
[1]  -->  [2, 3, 4]
[]  -->  [2, 3, 4, 1]--输出
[1, 3, 4]  -->  [2]
[1, 3]  -->  [2, 4]
[3]  -->  [2, 4, 1]
[]  -->  [2, 4, 1, 3]--输出
[1, 3]  -->  [2, 4]
[1]  -->  [2, 4, 3]
[]  -->  [2, 4, 3, 1]--输出
[1, 2, 3, 4]  -->  []
[1, 2, 4]  -->  [3]
[2, 4]  -->  [3, 1]
[4]  -->  [3, 1, 2]
[]  -->  [3, 1, 2, 4]--输出
[2, 4]  -->  [3, 1]
[2]  -->  [3, 1, 4]
[]  -->  [3, 1, 4, 2]--输出
[1, 2, 4]  -->  [3]
[1, 4]  -->  [3, 2]
[4]  -->  [3, 2, 1]
[]  -->  [3, 2, 1, 4]--输出
[1, 4]  -->  [3, 2]
[1]  -->  [3, 2, 4]
[]  -->  [3, 2, 4, 1]--输出
[1, 2, 4]  -->  [3]
[1, 2]  -->  [3, 4]
[2]  -->  [3, 4, 1]
[]  -->  [3, 4, 1, 2]--输出
[1, 2]  -->  [3, 4]
[1]  -->  [3, 4, 2]
[]  -->  [3, 4, 2, 1]--输出
[1, 2, 3, 4]  -->  []
[1, 2, 3]  -->  [4]
[2, 3]  -->  [4, 1]
[3]  -->  [4, 1, 2]
[]  -->  [4, 1, 2, 3]--输出
[2, 3]  -->  [4, 1]
[2]  -->  [4, 1, 3]
[]  -->  [4, 1, 3, 2]--输出
[1, 2, 3]  -->  [4]
[1, 3]  -->  [4, 2]
[3]  -->  [4, 2, 1]
[]  -->  [4, 2, 1, 3]--输出
[1, 3]  -->  [4, 2]
[1]  -->  [4, 2, 3]
[]  -->  [4, 2, 3, 1]--输出
[1, 2, 3]  -->  [4]
[1, 2]  -->  [4, 3]
[2]  -->  [4, 3, 1]
[]  -->  [4, 3, 1, 2]--输出
[1, 2]  -->  [4, 3]
[1]  -->  [4, 3, 2]
[]  -->  [4, 3, 2, 1]--输出

*/