java归并排序算法代码

下面是脚本之家 jb51.cc 通过网络收集整理的代码片段。

脚本之家小编现在分享给大家，也给大家做个参考。

public class MergeSort {
 // private static long sum = 0;
 
 /**
  * <pre>
  * 二路归并
  * 原理：将两个有序表合并和一个有序表
  * </pre>
  *
  * @param a
  * @param s
  *            第一个有序表的起始下标
  * @param m
  *            第二个有序表的起始下标
  * @param t
  *            第二个有序表的结束小标
  *
  */
 private static void merge(int[] a,int s,int m,int t) {
  int[] tmp = new int[t - s + 1];
 
  int i = s,j = m,k = 0;
  while (i < m && j <= t) {
   if (a[i] <= a[j]) {
    tmp[k] = a[i];
    k++;
    i++;
   } else {
    tmp[k] = a[j];
    // sum += (j - i) - (j - m);
    j++;
    k++;
   }
  }
  while (i < m) {
   tmp[k] = a[i];
   i++;
   k++;
  }
 
  while (j <= t) {
   tmp[k] = a[j];
   j++;
   k++;
  }
 
  System.arraycopy(tmp,a,s,tmp.length);
 }
 
 /**
  *
  * @param a
  * @param s
  * @param len
  *            每次归并的有序集合的长度
  */
 public static void mergeSort(int[] a,int len) {
 
  int size = a.length;
  int mid = size / (len << 1);
  int c = size & ((len<<1) - 1);
 
  // -------归并到只剩一个有序集合的时候结束算法-------//
  if (mid == 0)
   return;
 
  // ------进行一趟归并排序-------//
  for (int i = 0; i < mid; ++i) {
   s = i * 2 * len;
   merge(a,s + len,(len << 1) + s - 1);
  }
 
  // -------将剩下的数和倒数一个有序集合归并-------//
  if (c != 0)
   merge(a,size - c - 2 * len,size - c,size - 1);
  //
  // for (int i = 0; i < a.length; ++i) {
  // System.out.print(a[i] + " ");
  // }
  // System.out.println();
 
  // -------递归执行下一趟归并排序------//
  mergeSort(a,2 * len);
 }
 
 public static void main(String[] args) {
  // merge(new int[] { 4,3,6,1,2,5 },5);
 
  int[] a = new int[] { 4,5};
  mergeSort(a,1);
 
  for (int i = 0; i < a.length; ++i) {
   System.out.print(a[i] + " ");
  }
 
  // System.out.println("/n" + sum);
 }
 
}

以上是脚本之家(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得脚本之家网站内容还不错，欢迎将脚本之家网站推荐给程序员好友。

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!