“ 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 < 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 ------------------------------
}
问题答案：
对工作/临时数组进行一次分配，并避免在合并期间复制数据（除非将一个剩余的运行从一个数组移至另一个数组）。
自底向上合并排序示例。
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秒才能在我的系统上排序1000万个整数（Win 7，Intel 3770K 3.5 ghz，NetBeans 8.1，Java
1.8.0_65-b17）。
类似资料：
-
问题内容： 基本上，它在锡上说什么；我需要一个可在Java SE应用程序中使用的JTA实现，理想情况下，它不会承担太多框架负担。 问题答案： 我推荐Bitronix。在使用任何其他事务管理器之前，建议您进行彻底的测试。测试就像在交易的每个阶段都中断各种机器的电源一样。您希望事务性在发生故障时保护您。令人惊讶的是，有多少交易管理器未能正确实现恢复。 Bitronix确实需要JNDI，它通常是在Jav
-
用java实现以下场景，有100条商品，每个商品的价格0到1000元不等 商品数据: 例如200元 加价之后就是240元 利润是40元 首先把0到300元的商品的加价30%，301到500的加价20%，501到1000元商品的加价10%， 然后0到300元的商品订单有300条，301-500的商品订单有400条，501-1000的商品订单有300条， 最后计算他的总利润有多少，最好写出算法
-
我试图在Java中实现Prim的算法，用于我的图形HashMap LinkedList和一个包含连接顶点和权重的类Edge： 我的想法是，从一个给定的顶点开始：1）将所有顶点保存到一个LinkedList中，这样每次访问它们时我都可以删除它们2）将路径保存到另一个LinkedList中，这样我就可以得到我的最终MST 3）使用PriorityQueue找到最小权重 最后我需要MST，边数和总重量。
-
我想实现一个基准测试方法MergeSort和它的性能来衡量。我已经尝试用随机数填充要合并的数组，但是当代码运行时，数组会打印相同的随机数10次。这是为什么？ PS。我不能发布我编写的整个程序。Stackoverflow说代码太多了。
-
问题内容： 我发现Java 的根类方法没有实现： 如果我有一个and an ，如何不使用就知道the 和value ？只需执行即可。 我尝试了两个对象，但令我大吃惊的是值是相同的：它们都是1。 问题答案： 是一种方法，意味着系统库在内部被调用。有关更多详细信息，请参见Java本机接口。
-
这是我的代码： 有人能告诉我，如何更好地可视化这张图吗。或者我必须使用其他可用的图表。我使用的是GraphStream的基本示例。