演算法導論-歸併排序

• 2019 年 10 月 4 日
• 筆記

第二章第一節插入排序

插入排序又是增量排序

演算法如下：

/**   * 歸併排序   * 簡介:將兩個（或兩個以上）有序表合併成一個新的有序表 即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列   * 時間複雜度為O(nlogn)   * 穩定排序方式   * @param nums 待排序數組   * @return 輸出有序數組   */  public static int[] sort(int[] nums, int low, int high) {      int mid = (low + high) / 2;      if (low < high) {          // 左邊          sort(nums, low, mid);          // 右邊          sort(nums, mid + 1, high);          // 左右歸併          merge(nums, low, mid, high);      }      return nums;  }

public static void merge(int[] nums, int low, int mid, int high) {      int[] temp = new int[high - low + 1];      int i = low;// 左指針      int j = mid + 1;// 右指針      int k = 0;      // 把較小的數先移到新數組中      while (i <= mid && j <= high) {          if (nums[i] < nums[j]) {              temp[k++] = nums[i++];          } else {              temp[k++] = nums[j++];          }      }      // 把左邊剩餘的數移入數組      while (i <= mid) {          temp[k++] = nums[i++];      }      // 把右邊邊剩餘的數移入數組      while (j <= high) {          temp[k++] = nums[j++];      }      // 把新數組中的數覆蓋nums數組      for (int k2 = 0; k2 < temp.length; k2++) {          nums[k2 + low] = temp[k2];      }  }