[JAVA]合併排序(MergeSort)：小到大

2022-04-27 置頂文章
合併排序：空間換時間
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

// 空間換時間
public class MergeSort {

  public static void main(String[] args) {
//    int[] array = {0, -1, 78, 0, 23, -567, 70, 66};
    int n = 8000000;
    int[] array = new int[n];
    for (int i = 0; i < array.length; i++) {
      array[i] = (int) Math.random() * 800000;
    }
    int[] temp = new int[array.length];

    Date before = new Date();
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String beforeStr = sdf.format(before);
    System.out.println("排序前：" + beforeStr);

    doMergeSorting(array, 0, array.length-1, temp);
//    System.out.println(Arrays.toString(array));

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

  }

  /**
   * 合併排序(分治法)
   * 花費時間秒 => 陣列長度80000
   * @param array
   */
  public static void doMergeSorting(int[] array, int left, int right, int[] temp) {
    int middle = (left + right) / 2;
    // 分
    if (left < right) {
      // 在分的過程就有將分成的小組進行有序排列，所以就需要用到temp array
      doMergeSorting(array, left, middle, temp);
      doMergeSorting(array, middle + 1, right, temp);
      merge(array, left, right, middle, temp);
    }

  }

  public static void merge(int[] array, int left, int right, int middle, int[] temp) {
    int l = left;
    int r = middle + 1;
    int t = left;

    // 比較左右兩堆陣列哪邊值比較小就入temp array
    // 第一次合併 array[arrInx] = 0, right = 1 // array[arrInx] = 2, right = 3 // 第二次合併 array[arrInx] = 0, right = 3
    // 第三次合併 array[arrInx] = 4, right = 5 // array[arrInx] = 6, right = 7 // 第四次合併 array[arrInx] = 4, right = 7
    // 最後一次合併 array[arrInx] = 0, right = 7
    while (l <= middle && r <= right) {
      if (array[l] < array[r]) {
        temp[t++] = array[l++];
      } else {
        temp[t++] = array[r++];
      }
    }
    // 將某邊陣列剩餘的值入temp array
    while (l <= middle) {
      temp[t++] = array[l++];
    }
    while (r <= right) {
      temp[t++] = array[r++];
    }
    // 將temp array複製到原array
    // 每次從temp拷貝到原array值的數量視分組而定
    t = left;
    int arrInx = left;
    while (t <= right) {
      array[arrInx++] = temp[t++];
    }

  }

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