Code666 (代码贴、代码片段)

[Java] Java算法学习-----------------归并排序算法 →→→→→进入此内容的聊天室

来自 , 2020-01-05, 写在 Java, 查看 169 次.
URL http://www.code666.cn/view/fe7ee8fc
  1. public class MergeSort {
  2.        
  3.         public static void mergeSort(Comparable[]a)
  4.         {
  5.                 Comparable[]b=new Comparable[a.length];
  6.                 int s=1;
  7.                 while (s<a.length)
  8.                 {
  9.                         mergePass(a,b,s);//合并到数组b
  10.                         s+=s;
  11.                         mergePass(b,a,s);//合并到数组a
  12.                         s+=s;
  13.                 }
  14.         }
  15.  
  16.         private static void mergePass(Comparable[] x, Comparable[] y, int s)
  17.         {//合并大小为s的相邻数组
  18.                 int i=0;
  19.                 while (i<=x.length-2*s)
  20.                 {//合并大小为s的两端相邻字数组
  21.                         merge(x,y,i,i+s-1,i+s*2-1);
  22.                         i=i+2*s;
  23.                 }
  24.                 //剩下的元素个数小于2s
  25.                 if (i+s<x.length)
  26.                 {
  27.                         merge(x, y, i, i+s-1, x.length-1);
  28.                 }
  29.                 else//复制到y
  30.                 {
  31.                         for (int j = i; j < x.length; j++)
  32.                         {
  33.                                 y[j] = x[j];
  34.                         }
  35.                 }
  36.         }
  37.  
  38.         private static void merge(Comparable[] c, Comparable[] d, int l, int m, int r)
  39.         {
  40.                 //合并c[l:m]和c[m+1,r]到d[l:r]
  41.                 int i=1, j=m+1,k=l;
  42.                 while (i<=m && j<=r)
  43.                 {
  44.                         if (c[i].compareTo(c[j])<=0)
  45.                         {
  46.                                 d[k++]=c[i++];
  47.                         }
  48.                         else
  49.                         {
  50.                                 d[k++]=c[j++];
  51.                         }
  52.                 }
  53.                
  54.                 if (i>m)
  55.                 {
  56.                         for (int k2 = 0; k2 <=r; k2++)
  57.                         {
  58.                                 d[k++] = c[k2];
  59.                         }
  60.                 }
  61.                 else
  62.                 {
  63.                         for (int k2 = 0; k2 <=m; k2++)
  64.                         {
  65.                                 d[k++] = c[k2];
  66.                         }
  67.                 }
  68.         }
  69. }
  70.  

回复 "Java算法学习-----------------归并排序算法"

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

captcha

贴代码片段 - Code666