Code666 (代码贴、代码片段)

[Java] java归并排序算法代码 →→→→→进入此内容的聊天室

来自 , 2020-07-29, 写在 Java, 查看 108 次.
URL http://www.code666.cn/view/331609c9
  1. package algorithm;
  2.  
  3. public class MergeSort {
  4.  // private static long sum = 0;
  5.  
  6.  /**
  7.   * <pre>
  8.   * 二路归并
  9.   * 原理：将两个有序表合并和一个有序表
  10.   * </pre>
  11.   *
  12.   * @param a
  13.   * @param s
  14.   *            第一个有序表的起始下标
  15.   * @param m
  16.   *            第二个有序表的起始下标
  17.   * @param t
  18.   *            第二个有序表的结束小标
  19.   *
  20.   */
  21.  private static void merge(int[] a, int s, int m, int t) {
  22.   int[] tmp = new int[t - s + 1];
  23.  
  24.   int i = s, j = m, k = 0;
  25.   while (i < m && j <= t) {
  26.    if (a[i] <= a[j]) {
  27.     tmp[k] = a[i];
  28.     k++;
  29.     i++;
  30.    } else {
  31.     tmp[k] = a[j];
  32.     // sum += (j - i) - (j - m);
  33.     j++;
  34.     k++;
  35.    }
  36.   }
  37.   while (i < m) {
  38.    tmp[k] = a[i];
  39.    i++;
  40.    k++;
  41.   }
  42.  
  43.   while (j <= t) {
  44.    tmp[k] = a[j];
  45.    j++;
  46.    k++;
  47.   }
  48.  
  49.   System.arraycopy(tmp, 0, a, s, tmp.length);
  50.  }
  51.  
  52.  /**
  53.   *
  54.   * @param a
  55.   * @param s
  56.   * @param len
  57.   *            每次归并的有序集合的长度
  58.   */
  59.  public static void mergeSort(int[] a, int s, int len) {
  60.  
  61.   int size = a.length;
  62.   int mid = size / (len << 1);
  63.   int c = size & ((len<<1) - 1);
  64.  
  65.   // -------归并到只剩一个有序集合的时候结束算法-------//
  66.   if (mid == 0)
  67.    return;
  68.  
  69.   // ------进行一趟归并排序-------//
  70.   for (int i = 0; i < mid; ++i) {
  71.    s = i * 2 * len;
  72.    merge(a, s, s + len, (len << 1) + s - 1);
  73.   }
  74.  
  75.   // -------将剩下的数和倒数一个有序集合归并-------//
  76.   if (c != 0)
  77.    merge(a, size - c - 2 * len, size - c, size - 1);
  78.   //
  79.   // for (int i = 0; i < a.length; ++i) {
  80.   // System.out.print(a[i] + " ");
  81.   // }
  82.   // System.out.println();
  83.  
  84.   // -------递归执行下一趟归并排序------//
  85.   mergeSort(a, 0, 2 * len);
  86.  }
  87.  
  88.  public static void main(String[] args) {
  89.   // merge(new int[] { 4, 3, 6, 1, 2, 5 }, 0, 3, 5);
  90.  
  91.   int[] a = new int[] { 4, 3, 6, 1, 2, 5};
  92.   mergeSort(a, 0, 1);
  93.  
  94.   for (int i = 0; i < a.length; ++i) {
  95.    System.out.print(a[i] + " ");
  96.   }
  97.  
  98.   // System.out.println("/n" + sum);
  99.  }
  100.  
  101. }
  102.  
  103.  
  104. //java/5904

回复 "java归并排序算法代码"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666