‘MergeSort算法’ – JAVA中更好的实现是什么？
我知道快速排序算法，但我只关心合并排序算法。
我在互联网上发现了两种类型的合并排序算法实现。 但是当我将它们与插入算法进行比较时，它们似乎效率较低，而且对于大量项目而言并不是这样。
Enter the number of elements you want to sort: 300000 Time spent to executing BubbleSort: 362123 milliseconds Time spent to executing Selection: 108285 milliseconds Time spent to executing Insertion: 18046 milliseconds Time spent to executing MergeSort: 35968 milliseconds Time spent to executing MergeSort2: 35823 milliseconds 是否有另一种方法来实现合并排序算法，使其比插入算法更有效？
看看我的代码……
package br.com.test.test1; import java.util.Random; import java.util.Scanner; /** * * @author Joao */ public class Main { // generate an int array with random numbers between 0 and 500 public static int[] generateRand(int n){ int[] randArray = new int[n]; Random number = new Random(); // random numbers between 0 and 500 for (int i = 0; i < n; i++){ randArray[i] = number.nextInt(501); } return randArray; } public static void main(String[] args) { long startTime; Scanner input = new Scanner(System.in); int n; System.out.println("Enter the number of elements you want to sort:"); n = input.nextInt(); MyArray array = new MyArray(n); int[] aux = new int[n]; aux = generateRand(n); array.copy(aux); startTime = System.currentTimeMillis(); array.bubblesort(); // Time spent to executing BUBBLESORT System.out.println("\nTime spent to executing BubbleSort: "+(System.currentTimeMillis() - startTime)+" milliseconds"); array.copy(aux); startTime = System.currentTimeMillis(); array.selection(); // Time spent to executing SELECTION System.out.println("Time spent to executing Selection: "+(System.currentTimeMillis() - startTime)+" milliseconds"); array.copy(aux); startTime = System.currentTimeMillis(); array.insertion(); // Time spent to executing INSERTION System.out.println("Time spent to executing Insertion: "+(System.currentTimeMillis() - startTime)+" milliseconds"); array.copy(aux); startTime = System.currentTimeMillis(); array.mergeSort(0, n-1); // Time spent to executing MERGESORT System.out.println("Time spent to executing MergeSort: "+(System.currentTimeMillis() - startTime)+" milliseconds"); array.copy(aux); startTime = System.currentTimeMillis(); array.mergeSort2(0, n-1); // Time spent to executing MERGESORT 2 System.out.println("Time spent to executing MergeSort2: "+(System.currentTimeMillis() - startTime)+" milliseconds"); } }
—-和——
package br.com.test.test1; /** * * @author Joao Paulo */ class MyArray { private int[] v; private int n; // array index private int len; public MyArray(int length) { len = length; v = new int[len]; n = 0; } public void copy(int[] k){ n = 0; for (int i = 0; i < len; i++) { v[i] = k[i]; n++; } } public void show(){ for (int i = 0; i < n; i++) { System.out.print(" " + v[i]); } System.out.println("\n"); } // ******* START OF ALGORITHMS TO SORT ******* // ---------- Start of BubbleSort and Selection -------------- public void bubblesort(){ for (int i = 0; i < n; i++){ for (int j = 0; j v[j+1]) { change(j, j+1); } } } } public void selection() { int min; for (int i = 0; i < n-1; i++) { min = i; for (int j = i+1; j < n; j++){ if (v[j] < v[min]){ min = j; } } change(i, min); } } private void change(int one, int two) { int temp = v[one]; v[one] = v[two]; v[two] = temp; } // ---------- End of BubbleSort and Selection ---------------- // ---------- Start of Insertion ----------------------------- public void insertion() { int i, j; int temp; for (i=1; i 0) && (v[j-1] > temp)) { v[j] = v[j-1]; j = j - 1; } v[j] = temp; } } // ---------- End of Insertion ------------------------------- // ---------- Start of MergeSort ----------------------------- public void mergeSort (int start, int end){ if(start == end) return; int middle = (start+end)/2; mergeSort(start,middle); mergeSort(middle+1,end); merge(start,middle,end); } public void merge(int start, int middle, int end) { int[] aux = new int[v.length]; for (int x = start; x <= end; x++) { aux[x] = v[x]; } int i = start; int j = middle+1; int k = start; //emptying out array 'v' inserting items neatly in array 'aux' while (i <= middle && j <= end) { if (aux[i] < aux[j]){ v[k++] = aux[i++]; } else { v[k++] = aux[j++]; } } //copying values from 'aux' to 'v' while (i <= middle){ v[k++] = aux[i++]; } while (j = end) return; int middle = (start+end)/2; mergeSort2(start,middle); mergeSort2(middle+1,end); merge2(start,middle,end); } public void merge2(int start, int middle, int end) { int[] helper = new int[v.length]; // Copy both parts into the helper array for (int i = start; i <= end; i++) { helper[i] = v[i]; } int i = start; int j = middle + 1; int k = start; // Copy the smallest values from either the left or the right side back to the original array while (i <= middle && j <= end) { if (helper[i] <= helper[j]) { v[k] = helper[i]; i++; } else { v[k] = helper[j]; j++; } k++; } // Copy the rest of the left side of the array into the target array while (i <= middle) { v[k] = helper[i]; k++; i++; } // Since we are sorting in-place any leftover elements from the right side // are already at the right position. } // ---------- End of MergeSort 2 ------------------------------ }
单独分配工作/临时数组并避免在合并期间复制数据（除非将一个剩余的运行从一个数组移动到另一个数组）。
自下而上合并排序示例。
package jsortbu; import java.util.Random; public class jsortbu { static void MergeSort(int[] a) // entry function { if(a.length < 2) // if size < 2 return return; int[] b = new int[a.length]; BottomUpMergeSort(a, b); } static void BottomUpMergeSort(int[] a, int[] b) { int n = a.length; int s = 1; // run size if(1 == (GetPassCount(n)&1)){ // if odd number of passes for(s = 1; s < n; s += 2) // swap in place for 1st pass if(a[s] < a[s-1]){ int t = a[s]; a[s] = a[s-1]; a[s-1] = t; } s = 2; } while(s < n){ // while not done int ee = 0; // reset end index while(ee < n){ // merge pairs of runs int ll = ee; // ll = start of left run int rr = ll+s; // rr = start of right run if(rr >= n){ // if only left run do{ // copy it b[ll] = a[ll]; ll++; }while(ll < n); break; // end of pass } ee = rr+s; // ee = end of right run if(ee > n) ee = n; Merge(a, b, ll, rr, ee); } { // swap references int[] t = a; a = b; b = t; } s <<= 1; // double the run size } } static void Merge(int[] a, int[] b, int ll, int rr, int ee) { int o = ll; // b[] index int l = ll; // a[] left index int r = rr; // a[] right index while(true){ // merge data if(a[l] <= a[r]){ // if a[l] <= a[r] b[o++] = a[l++]; // copy a[l] if(l < rr) // if not end of left run continue; // continue (back to while) while(r < ee){ // else copy rest of right run b[o++] = a[r++]; } break; // and return } else { // else a[l] > a[r] b[o++] = a[r++]; // copy a[r] if(r < ee) // if not end of right run continue; // continue (back to while) while(l < rr){ // else copy rest of left run b[o++] = a[l++]; } break; // and return } } } static int GetPassCount(int n) // return # passes { int i = 0; for(int s = 1; s < n; s <<= 1) i += 1; return(i); } public static void main(String[] args) { int[] a = new int[10000000]; Random r = new Random(); for(int i = 0; i < a.length; i++) a[i] = r.nextInt(); long bgn, end; bgn = System.currentTimeMillis(); MergeSort(a); end = System.currentTimeMillis(); for(int i = 1; i < a.length; i++){ if(a[i-1] > a[i]){ System.out.println("failed"); break; } } System.out.println("milliseconds " + (end-bgn)); } }
自上而下合并排序示例。 一对相互递归的函数用于避免复制操作。 合并的方向基于递归的级别。 自下而上和自上而下的Merge（）是相同的。
package jsorttd; import java.util.Random; public class jsorttd { static void MergeSort(int[] a) // entry function { if(a.length < 2) // if size < 2 return return; int[] b = new int[a.length]; MergeSortAtoA(a, b, 0, a.length); } static void MergeSortAtoA(int[] a, int[] b, int ll, int ee) { if(ee - ll > 1) { int rr = (ll + ee)>>1; // midpoint, start of right half MergeSortAtoB(a, b, ll, rr); MergeSortAtoB(a, b, rr, ee); Merge(b, a, ll, rr, ee); // merge b to a } } static void MergeSortAtoB(int[] a, int[] b, int ll, int ee) { if(ee - ll > 1) { int rr = (ll + ee)>>1; //midpoint, start of right half MergeSortAtoA(a, b, ll, rr); MergeSortAtoA(a, b, rr, ee); Merge(a, b, ll, rr, ee); // merge a to b } else if((ee - ll) == 1) { // if just one element b[ll] = a[ll]; // copy a to b } } static void Merge(int[] a, int[] b, int ll, int rr, int ee) { int o = ll; // b[] index int l = ll; // a[] left index int r = rr; // a[] right index while(true){ // merge data if(a[l] <= a[r]){ // if a[l] <= a[r] b[o++] = a[l++]; // copy a[l] if(l < rr) // if not end of left run continue; // continue (back to while) while(r < ee){ // else copy rest of right run b[o++] = a[r++]; } break; // and return } else { // else a[l] > a[r] b[o++] = a[r++]; // copy a[r] if(r < ee) // if not end of right run continue; // continue (back to while) while(l < rr){ // else copy rest of left run b[o++] = a[l++]; } break; // and return } } } public static void main(String[] args) { int[] a = new int[10000000]; Random r = new Random(); for(int i = 0; i < a.length; i++) a[i] = r.nextInt(); long bgn, end; bgn = System.currentTimeMillis(); MergeSort(a); end = System.currentTimeMillis(); for(int i = 1; i < a.length; i++){ if(a[i-1] > a[i]){ System.out.println("failed"); break; } } System.out.println("milliseconds " + (end-bgn)); } }
这两种方法在我的系统上排序大约1秒钟（Win 7，Intel 3770K 3.5 ghz，NetBeans 8.1，Java 1.8.0_65-b17）。