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

这个也是比较常见的方法。
先交换，再把后面的数组逆置就行了
递归的方法点下面：
算法笔记之 全排列算法 一 递归求解
 
[java]  
    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);  
    }  
 

补充：软件开发 , Java ,

上一个：特创论
下一个：Java排序算法