实现代码import java.lang.reflect.array;import java.util.*; public class mergesort{ // 我们的算法类不允许产生任何实例 private mergesort(){} // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(comparable[] arr, int l, int mid, int r) { comparable[] aux = arrays.copyofrange(arr, l, r+1); // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1 int i = l, j = mid+1; for( int k = l ; k <= r; k ++ ){ if( i > mid ){ // 如果左半部分元素已经全部处理完毕 arr[k] = aux[j-l]; j ++; } else if( j > r ){ // 如果右半部分元素已经全部处理完毕 arr[k] = aux[i-l]; i ++; } else if( aux[i-l].compareto(aux[j-l]) < 0 ){ // 左半部分所指元素 < 右半部分所指元素 arr[k] = aux[i-l]; i ++; } else{ // 左半部分所指元素 >= 右半部分所指元素 arr[k] = aux[j-l]; j ++; } } } // 递归使用归并排序,对arr[l...r]的范围进行排序 private static void sort(comparable[] arr, int l, int r, int depth) { system.out.print(repeatcharacters('-', depth*2)); system.out.println("deal with [ " + l + " , " + r + " ]"); if (l >= r) return; int mid = (l+r)/2; sort(arr, l, mid, depth + 1); sort(arr, mid + 1, r, depth + 1); merge(arr, l, mid, r); } private static string repeatcharacters(char character, int length){ stringbuilder s = new stringbuilder(length); for(int i = 0 ; i < length ; i ++) s.append(character); return s.tostring(); } public static void sort(comparable[] arr){ int n = arr.length; sort(arr, 0, n-1, 0); } // 测试mergesort public static void main(string[] args) { // merge sort是我们学习的第一个o(nlogn)复杂度的算法 // 可以在1秒之内轻松处理100万数量级的数据 // 注意：不要轻易尝试使用selectionsort, insertionsort或者bubblesort处理100万级的数据 // 否则，你就见识了o(n^2)的算法和o(nlogn)算法的本质差异：）// int n = 1000000;// integer[] arr = sorttesthelper.generaterandomarray(n, 0, 100000);// sorttesthelper.testsort("bobo.algo.mergesort", arr); integer[] arr = new integer[8]; for(int i = 0 ; i < 8 ; i ++) { arr[i] = new integer(8-i);// arr[i] = 8 -i; } // arr = sorttesthelper.generaterandomarray(50, 1, 50); mergesort.sort(arr); return; }}
import java.lang.reflect.method;import java.lang.class;import java.util.random; public class sorttesthelper { // sorttesthelper不允许产生任何实例 private sorttesthelper(){} // 生成有n个元素的随机数组,每个元素的随机范围为[rangel, ranger] public static integer[] generaterandomarray(int n, int rangel, int ranger) { assert rangel <= ranger; integer[] arr = new integer[n]; for (int i = 0; i < n; i++) arr[i] = new integer((int)(math.random() * (ranger - rangel + 1) + rangel)); return arr; } // 生成一个近乎有序的数组 // 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swaptimes对数据 // swaptimes定义了数组的无序程度: // swaptimes == 0 时, 数组完全有序 // swaptimes 越大, 数组越趋向于无序 public static integer[] generatenearlyorderedarray(int n, int swaptimes){ integer[] arr = new integer[n]; for( int i = 0 ; i < n ; i ++ ) arr[i] = new integer(i); for( int i = 0 ; i < swaptimes ; i ++ ){ int a = (int)(math.random() * n); int b = (int)(math.random() * n); int t = arr[a]; arr[a] = arr[b]; arr[b] = t; } return arr; } // 打印arr数组的所有内容 public static void printarray(object[] arr) { for (int i = 0; i < arr.length; i++){ system.out.print( arr[i] ); system.out.print( ' ' ); } system.out.println(); return; } // 判断arr数组是否有序 public static boolean issorted(comparable[] arr){ for( int i = 0 ; i < arr.length - 1 ; i ++ ) if( arr[i].compareto(arr[i+1]) > 0 ) return false; return true; } // 测试sortclassname所对应的排序算法排序arr数组所得到结果的正确性和算法运行时间 public static void testsort(string sortclassname, comparable[] arr){ // 通过java的反射机制，通过排序的类名，运行排序函数 try{ // 通过sortclassname获得排序函数的class对象 class sortclass = class.forname(sortclassname); // 通过排序函数的class对象获得排序方法 method sortmethod = sortclass.getmethod("sort",new class[]{comparable[].class}); // 排序参数只有一个，是可比较数组arr object[] params = new object[]{arr}; long starttime = system.currenttimemillis(); // 调用排序函数 sortmethod.invoke(null,params); long endtime = system.currenttimemillis(); assert issorted( arr ); system.out.println( sortclass.getsimplename()+ " : " + (endtime-starttime) + "ms" ); } catch(exception e){ e.printstacktrace(); } }}
实现效果
以上就是怎么用java实现归并排序的详细内容。