'MergeSort 算法' - JAVA 中更好的实现是什么? [英] 'MergeSort Algorithm' - What's the better implementation in JAVA?
本文介绍了'MergeSort 算法' - JAVA 中更好的实现是什么?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我知道快速排序算法，但我只关心归并排序算法.
I know quick sort algorithm, but I am concerned with merge sort algorithm only.
我在互联网上发现了两种类型的归并排序算法实现.但是当我将它们与插入算法进行比较时，它们似乎效率较低，而且对于大量项目来说这不是预期的.
I found out on internet two types of merge sort algorithm implementation. But when I compare them with insertion algorithm, they seem less efficient and this is not expected for a large number of items.
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
有没有其他方法可以实现归并排序算法，使其比插入算法更高效?
Is there another way to implement the merge sort algorithm to make it more efficient than the insertion algorithm?
看看我的代码...
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("
Time 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");
}
}
---- 和 ------
---- and ------
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("
");
}
// ******* 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 < n-1; j++) {
if (v[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 < n; i++) {
temp = v[i]; // marked variable
j = i;
while ((j > 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){
v[k++] = aux[j++];
}
}
// ---------- End of MergeSort -------------------------------
// ---------- Start of MergeSort 2 ----------------------------
public void mergeSort2 (int start, int end) {
if(start >= 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 ------------------------------
}
推荐答案
对工作/临时数组进行一次分配，并避免在合并期间复制数据(除非将剩余的单个运行从一个数组移动到另一个数组).
Do a single allocation of the working/temp array and avoid copying of data during merge (unless moving a single remaining run from one array to the other).
自下而上的归并排序示例.
Bottom up merge sort example.
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() 对于自下而上和自上而下都是相同的.
Top down merge sort example. A pair of mutually recursive functions are used to avoid copy back operations. The direction of merge is based on the level of recursion. Merge() is the same for both bottom up and top down.
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));
}
}
这两种方法在我的系统(Win 7、Intel 3770K 3.5 ghz、NetBeans 8.1、Java 1.8.0_65-b17)上对 1000 万个整数进行排序都需要大约 1 秒的时间.
Both methods take about 1 second to sort 10 million integers on my system (Win 7, Intel 3770K 3.5 ghz, NetBeans 8.1, Java 1.8.0_65-b17).
这篇关于'MergeSort 算法' - JAVA 中更好的实现是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
