[JAVA]插入排序(InsertionSort)：小到大

2022-04-15 置頂文章

插入排序(InsertionSort)：小到大

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class InsertionSort {



  public static void main(String[] args) {
//    int[] array = {101, 34, 5, 77, -1, 4};
//    System.out.println("排序前陣列：");
//    System.out.println(Arrays.toString(array));
//    doInsertionSorting(array);
//    System.out.println("排序後陣列：");
//    System.out.println(Arrays.toString(array));


    int n = 80000;
    int[] array = new int[n];
    for (int i = 0; i < array.length; i++) {
      array[i] = (int) (Math.random() * 800000);
    }
    Date beforeSort = new Date();
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String before = sdf.format(beforeSort);
    System.out.println("排序前時間：" + before);

    doInsertionSorting(array);

    Date afterSort = new Date();
    String after = sdf.format(afterSort);
    System.out.println("排序後時間：" + after);


  }

  /**
   * 插入排序
   * 外層迴圈循環次數array.lenth-1
   * @param array
   */
  public static void doInsertionSorting(int[] array) {

    for (int i = 0; i < array.length-1; i++) {
      // 待插入的值
      int insertionVal = array[i+1];
      // 待插入的索引位置
      int insertionInx = i;

      // 避免索引越界的狀況進行交換
      while (insertionInx >= 0 && insertionVal < array[insertionInx]) {
        // 先讓第1個值與第二個值相等
        array[insertionInx + 1] = array[insertionInx];
        array[insertionInx] = insertionVal;
        // 每趟內層循環只進行交換一次，跳出循環條件
        insertionInx--;
      }
    }
  }
}

如有敘述錯誤，還請不吝嗇留言指教，thanks!

回首頁