归并排序(java)

归并排序的思想是分治法，现将数组逐级二分再二分，分到最小的两个元素后，逐级往上归并，故其核心在于归并。

归并需要有一个同等大小的辅助数组aux，现将需要归并的元素copy至辅助数组aux中，然后通过逐一比较aux中的元素，将其放至原数组中的合适位置。

 1 package 排序; 2  3 import java.util.Arrays; 4 import edu.princeton.cs.algs4.StdOut; 5  6 /** 7  * @author evasean www.cnblogs.com/evasean/ 8 */ 9 @SuppressWarnings("rawtypes")10 public class Merge归并排序 {11   private static Comparable[] aux;12   private static int num=1;13   public static void merge(Comparable[] a, int lo, int mid, int hi){14     StdOut.println("merge lo="+lo+",mid="+mid+",hi="+hi);15     int i = lo; //左半边元素索引记录16     int j = mid+1; //右半边元素索引记录17     for(int k = lo; k <= hi; k++) 18       aux[k] = a[k];19     for(int k = lo; k <= hi; k++){20       if(i > mid) a[k] = aux[j++];//左半边用尽，取右半边元素21       else if(j > hi) a[k] = aux[i++];//右半边用尽，取左半边元素22       else if(less(aux[j],aux[i])) a[k] = aux[j++];//右半边当前元素小于左半边当前元素，取右半边元素23       else a[k] = aux[i++];//右半边当前元素大于或等于左半边当前元素，取左半边元素24     }25     StdOut.println("第"+num+"次归并结果："+Arrays.toString(a));26     num++;27   }28   public static void sort(Comparable[] a){29     //自顶向下的归并排序30     aux = new Comparable[a.length];31     sort(a,0,a.length-1);32   }33   public static void sort(Comparable[] a, int lo, int hi){34     if(hi <= lo) return;35     int mid = lo + (hi-lo)/2;36     sort(a,lo,mid);37     sort(a,mid+1,hi);38     merge(a,lo,mid,hi);39   }40   public static void sortBU(Comparable[] a){41     //自底向上的归并排序42     int N = a.length;43     aux = new Comparable[N];44     for(int sz = 1; sz < N; sz=2*sz){45       for(int lo = 0; lo < N - sz; lo += 2*sz){46         merge(a,lo,lo+sz-1,Math.min(lo+2*sz-1, N-1));47       }48     }49   }50 51   @SuppressWarnings("unchecked")52   private static boolean less(Comparable v, Comparable w) {53     return v.compareTo(w) < 0;54   }55 56   private static void show(Comparable[] a) {57     for (int i = 0; i < a.length; i++)58       StdOut.print(a[i] + " ");59     StdOut.println();60   }61 62   public static boolean isSorted(Comparable[] a) {63     for (int i = 1; i < a.length; i++) {64       if (less(a[i], a[i - 1]))65         return false;66     }67     return true;68   }69 70   public static void main(String[] args) {71     String[] a = {"M","E","R","G","E","S","O","R","T","E","X","A","M","P","L","E"};72     StdOut.println(Arrays.toString(a));73     sort(a);74     assert isSorted(a);75     show(a);76   }77 }

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：归并排序(java)

关键词：JAVA