千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構

手機站
千鋒教育

千鋒學(xué)習站 | 隨時(shí)隨地免費學(xué)

千鋒教育

掃一掃進(jìn)入千鋒手機站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習站小程序
隨時(shí)隨地免費學(xué)習課程

當前位置:首頁(yè)  >  千鋒問(wèn)問(wèn)  > 歸并算法java實(shí)現方法怎么操作

歸并算法java實(shí)現方法怎么操作

匿名提問(wèn)者 2023-10-16 15:45:42

歸并算法java實(shí)現方法怎么操作

推薦答案

  遞歸實(shí)現,遞歸是最常見(jiàn)的歸并排序實(shí)現方式。這個(gè)方法將數組分為左右兩部分,分別對左右兩部分進(jìn)行遞歸排序,然后再合并它們。

Java教程

  public class MergeSort {

  public static void merge(int[] arr, int left, int mid, int right) {

  int n1 = mid - left + 1;

  int n2 = right - mid;

  int[] L = new int[n1];

  int[] R = new int[n2];

  for (int i = 0; i < n1; i++) {

  L[i] = arr[left + i];

  }

  for (int j = 0; j < n2; j++) {

  R[j] = arr[mid + 1 + j];

  }

  int i = 0, j = 0, k = left;

  while (i < n1 && j < n2) {

  if (L[i] <= R[j]) {

  arr[k] = L[i];

  i++;

  } else {

  arr[k] = R[j];

  j++;

  }

  k++;

  }

  while (i < n1) {

  arr[k] = L[i];

  i++;

  k++;

  }

  while (j < n2) {

  arr[k] = R[j];

  j++;

  k++;

  }

  }

  public static void mergeSort(int[] arr, int left, int right) {

  if (left < right) {

  int mid = left + (right - left) / 2;

  mergeSort(arr, left, mid);

  mergeSort(arr, mid + 1, right);

  merge(arr, left, mid, right);

  }

  }

  public static void main(String[] args) {

  int[] arr = {12, 11, 13, 5, 6, 7};

  mergeSort(arr, 0, arr.length - 1);

  System.out.println("Sorted array:");

  for (int num : arr) {

  System.out.print(num + " ");

  }

  }

  }

 

  這個(gè)方法使用遞歸將數組分成左右兩半,然后分別對左右兩半進(jìn)行排序,最后合并左右兩半得到有序數組。

其他答案

  •   迭代實(shí)現,迭代方法不使用遞歸,而是使用循環(huán)來(lái)實(shí)現歸并排序。它需要使用一個(gè)輔助數組來(lái)保存中間結果,以避免頻繁創(chuàng )建和銷(xiāo)毀數組。

      public class MergeSort {

      public static void merge(int[] arr, int left, int mid, int right) {

      int n1 = mid - left + 1;

      int n2 = right - mid;

      int[] L = new int[n1];

      int[] R = new int[n2];

      for (int i = 0; i < n1; i++) {

      L[i] = arr[left + i];

      }

      for (int j = 0; j < n2; j++) {

      R[j] = arr[mid + 1 + j];

      }

      int i = 0, j = 0, k = left;

      while (i < n1 && j < n2) {

      if (L[i] <= R[j]) {

      arr[k] = L[i];

      i++;

      } else {

      arr[k] = R[j];

      j++;

      }

      k++;

      }

      while (i < n1) {

      arr[k] = L[i];

      i++;

      k++;

      }

      while (j < n2) {

      arr[k] = R[j];

      j++;

      k++;

      }

      }

      public static void mergeSort(int[] arr) {

      int n = arr.length;

      for (int currentSize = 1; currentSize < n; currentSize *= 2) {

      for (int left = 0; left < n - 1; left += 2 * currentSize) {

      int mid = Math.min(left + currentSize - 1, n - 1);

      int right = Math.min(left + 2 * currentSize - 1, n - 1);

      merge(arr, left, mid, right);

      }

      }

      }

      public static void main(String[] args) {

      int[] arr = {12, 11, 13, 5, 6, 7};

      mergeSort(arr);

      System.out.println("Sorted array:");

      for (int num : arr) {

      System.out.print(num + " ");

      }

      }

      }

      這個(gè)方法使用循環(huán)迭代來(lái)排序數組,避免了遞歸調用,同時(shí)利用了一個(gè)輔助數組進(jìn)行合并操作。

  •    自底向上的迭代實(shí)現,這種實(shí)現方式也是使用迭代,但與上述方法略有不同,它是自底向上的迭代,從單個(gè)元素開(kāi)始,逐漸增加合并的區間大小。

      ```java

      public class MergeSort {

      public static void merge(int[] arr, int left, int mid, int right) {

      int n1 = mid - left + 1;

      int n2 = right - mid;

      int[] L = new int[n1];

      int[] R = new int[n2];

      for (int i = 0; i < n1; i++) {

      L[i] = arr[left + i];

      }

      for (int j = 0; j < n2; j++) {

      R[j] = arr[mid + 1 + j];

      }

      int i = 0, j = 0, k = left;

      while (i < n1 && j < n2) {

      if (L[i] <= R[j]) {

      arr[k] = L[i];

      i++;

      } else {

      arr[k] = R[j];

      j++;

      }

      k++;

      }

      while (i < n1) {

      arr[k] = L[i];

      i++;

      k++;

      }

      while (j < n2) {

      arr[k] = R[j];

      j++;

      k++;

      }

      }

      public static void mergeSort(int[] arr) {

      int n = arr.length;

      for (int currentSize = 1; currentSize < n; currentSize *= 2) {