Java對數組完成選擇排序算法的實例詳解

Java對數組完成選擇排序算法的實例詳解。本站提示廣大學習愛好者：（Java對數組完成選擇排序算法的實例詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是Java對數組完成選擇排序算法的實例詳解正文

一. 算法描寫
    選擇排序：好比在一個長度為N的無序數組中，在第一趟遍歷N個數據，找出個中最小的數值與第一個元故舊換，第二趟遍歷剩下的N-1個數據，找出個中最小的數值與第二個元故舊換......第N-1趟遍歷剩下的2個數據，找出個中最小的數值與第N-1個元故舊換，至此選擇排序完成。
以上面5個無序的數據為例：
56 12 80 91 20（文中僅細化了第一趟的選擇進程）
第1趟：12 56 80 91 20

第2趟：12 20 80 91 56
第3趟：12 20 56 91 80
第4趟：12 20 56 80 91
二. 算法剖析
均勻時光龐雜度：O(n2)
空間龐雜度：O(1)  (用於交流和記載索引)
穩固性：不穩固 （好比序列【5， 5， 3】第一趟就將第一個[5]與[3]交流，招致第一個5移動到第二個5前面）
三. 算法完成

 
public class SelectionSort { 
  public static void main(String[] args) { 
    int len = 15; 
    int[] ary = new int[len]; 
    Random random = new Random(); 
    for (int j = 0; j < len; j++) { 
      ary[j] = random.nextInt(1000); 
    } 
    System.out.println("-------排序前------"); 
//   ary=new int[]{10,9,8,7,6,5,4,3,2,1}; //測試交流次數 
//   ary=new int[]{1,2,3,4,5,6,7,8,10,9}; //測試交流次數 
    for (int j = 0; j < ary.length; j++) { 
      System.out.print(ary[j] + " "); 
    } 
     
    selectDesc(ary); 
    selectAsc(ary); 
  } 
  /* 
   * 選擇排序：降序 
   */ 
  static void selectDesc(int[] ary) { 
    int compareCount = 0;//比擬次數 
    int changeCount = 0;//交流次數 
    int len = ary.length; 
    int maxValueIndex = -1; //記載一輪比擬上去的最小值索引 
    for (int i = 0; i < len - 1; i++) { 
      maxValueIndex = i; //從0開端 
      for (int j = i + 1; j < len; j++) { 
        if (ary[maxValueIndex] < ary[j]) { 
          maxValueIndex = j; //記載較年夜的索引 
          compareCount++; 
        } 
      } 
//     System.out.println("minValueIndex==" + maxValueIndex); 
      if (maxValueIndex != i) {//假如跟右邊的記載索引分歧，則交流 
        ary[i] = ary[maxValueIndex] + (ary[maxValueIndex] = ary[i]) * 0;//一步交流 
        changeCount++; 
      } 
    } 
     
    System.out.println("\n-------降序排序後------比擬次數：" + compareCount + "，交流次數" + changeCount); 
    for (int j = 0; j < ary.length; j++) { 
      System.out.print(ary[j] + " "); 
    } 
  } 
   
  /* 
   * 選擇排序：升序 
   */ 
  static void selectAsc(int[] ary) { 
    int compareCount = 0, changeCount = 0; 
    int len = ary.length; 
    int minIndex = -1; 
    for (int i = 0; i < len - 1; i++) { 
      minIndex = i; 
      for (int j = i + 1; j < len; j++) { 
        if (ary[minIndex] > ary[j]) { 
          minIndex = j; //記載較小的索引 
          compareCount++; 
        } 
      } 
      if (minIndex != i) {//假如跟右邊的記載索引分歧，則交流 
        ary[i] = ary[minIndex] + (ary[minIndex] = ary[i]) * 0; 
        changeCount++; 
      } 
    } 
    System.out.println("\n-------升序排序後------比擬次數：" + compareCount + "，交流次數" + changeCount); 
    for (int j = 0; j < ary.length; j++) { 
      System.out.print(ary[j] + " "); 
    } 
  } 
} 

打印

-------排序前------ 
125 350 648 789 319 699 855 755 552 489 187 916 596 731 852  
-------降序排序後------比擬次數：26，交流次數13 
916 855 852 789 755 731 699 648 596 552 489 350 319 187 125  
-------升序排序後------比擬次數：56，交流次數7 
125 187 319 350 489 552 596 648 699 731 755 789 852 855 916