[JAVA]希爾排序(ShellSort)：小到大

2022-04-18 置頂文章

50
0
data structure
2022-04-19

希爾排序(ShellSort)

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

public class ShellSort {

  public static void main(String[] args) {
//    int[] array = {2, 6, 0, 5, 4, 7, 1, 9, 3, 8};
//    doShellSorting2(array);
//    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);
    doShellSorting2(array);
    Date afterSort = new Date();
    String after = sdf.format(afterSort);
    System.out.println("排序後時間：" + after);

  }

  /**
   * 希爾排序(交換法)
   * 花費時間5秒 => 陣列長度80000
   * @param array
   */
  public static void doShellSorting(int[] array) {
    int insertionVal = 0;

    for (int gap = array.length / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < array.length; i++) {
        for (int groupInx = i - gap; groupInx >= 0; groupInx -= gap) {
          // 倆倆交換
          if (array[groupInx] > array[groupInx + gap]) {
            insertionVal = array[groupInx];
            array[groupInx] = array[groupInx + gap];
            array[groupInx + gap] = insertionVal;
          }
        }
      }
//        System.out.println(Arrays.toString(array));
    }
  }


  /**
   * 希爾排序(移位法)
   * 花費時間1秒內 => 陣列長度80000
   * @param array
   */
  public static void doShellSorting2(int[] array) {

    for (int gap = array.length / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < array.length; i++) {
        // 陣列分成groupInx組，代表欲交換的兩值之間相隔的數字數量
        int groupInx = i;
        // 待插入的值
        int inserionVal = array[groupInx];
        while (groupInx - gap >= 0 && inserionVal < array[groupInx - gap]) {
          array[groupInx] = array[groupInx - gap];
          groupInx -= gap;
        }
        // 待插入的值一定要再找到正確的索引位置才插入(待插入的值大於左邊的值)
        array[groupInx] = inserionVal;
      }
    }
  }

}

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

回首頁