算法札记之 全排列的 非递归求解

算法笔记之 全排列的 非递归求解

这个也是比较常见的方法。

先交换，再把后面的数组逆置就行了

递归的方法点下面：

算法笔记之 全排列算法 一 递归求解

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
	//排列. total 表示输出arr之后的 total个排列
	static void permutation(int[] arr,int total)
	{
//		int total = 1;
//		for(int i=2; i<= size; i++){
//			total *= i;
//		}
//		print_arr(arr);
		for(int i=1; i<total; i++){
			int k = arr.length -1;
			
			//找到要进行替换的元素下标。  
			//即从后开始遍历，找到底一个非增的元素，和后面某个刚好大于它的元素替换
			while( k>0 && arr[k] < arr[--k]);
			
			int min = Integer.MAX_VALUE;
			int minIndex = 0;
			
			//找到刚好比 替换到前面大的元素
			for(int j=arr.length-1; j>= k+1; j--){
				if(arr[j] > arr[k] && min > arr[j]){
					min = arr[j];
					minIndex = j;
				}
			}
			
			//与找到的元素 进行交换
			swap(arr, k, minIndex);
			
			//做数组的 逆置
			for(int m=0; m < (arr.length-k-1)/2; m++)
				swap(arr, k+1 + m, arr.length-1-m);
			
			print_arr(arr);
		}

	}
	
	public static void print_arr(int[] arr){
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i]);
		System.out.println();
	}


	public static void main(String[] args) {
		int arr[] = {1,2,3,4,5};
		
		print_arr(arr);
		permutation(arr,23);
	}