疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

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


 

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