在Java中的Mergesort

我是Java新手，并尝试在Java中实现mergesort。 但是，即使多次运行程序，而不是所需的排序输出，我得到相同的用户输入作为输出。 如果有人能帮助我理解这种意想不到的行为，我将感激不尽。

import java.io.*; import java.util.Arrays; public class MergeSort { public static void main(String[] args) throws IOException{ BufferedReader R = new BufferedReader(new InputStreamReader(System.in)); int arraySize = Integer.parseInt(R.readLine()); int[] inputArray = new int[arraySize]; for (int i = 0; i < arraySize; i++) { inputArray[i] = Integer.parseInt(R.readLine()); } mergeSort(inputArray); for (int j = 0; j  1) { int q = A.length/2; int[] leftArray = Arrays.copyOfRange(A, 0, q); int[] rightArray = Arrays.copyOfRange(A,q+1,A.length); mergeSort(leftArray); mergeSort(rightArray); A = merge(leftArray,rightArray); } } static int[] merge(int[] l, int[] r) { int totElem = l.length + r.length; int[] a = new int[totElem]; int i,li,ri; i = li = ri = 0; while ( i < totElem) { if ((li < l.length) && (ri<r.length)) { if (l[li] = l.length) { while (ri = r.length) { while (li < l.length) { a[i] = l[li]; li++; i++; } } } } return a; } } 

Answer 1

以下是您的代码的更正版本：

 import java.io.*; import java.util.Arrays; public class MergeSort { public static void main(String[] args) throws IOException{ BufferedReader R = new BufferedReader(new InputStreamReader(System.in)); int arraySize = Integer.parseInt(R.readLine()); int[] inputArray = new int[arraySize]; for (int i = 0; i < arraySize; i++) { inputArray[i] = Integer.parseInt(R.readLine()); } mergeSort(inputArray); for (int j = 0; j < inputArray.length; j++) { System.out.println(inputArray[j]); } } static void mergeSort(int[] A) { if (A.length > 1) { int q = A.length/2; //changed range of leftArray from 0-to-q to 0-to-(q-1) int[] leftArray = Arrays.copyOfRange(A, 0, q-1); //changed range of rightArray from q-to-A.length to q-to-(A.length-1) int[] rightArray = Arrays.copyOfRange(A,q,A.length-1); mergeSort(leftArray); mergeSort(rightArray); merge(A,leftArray,rightArray); } } static void merge(int[] a, int[] l, int[] r) { int totElem = l.length + r.length; //int[] a = new int[totElem]; int i,li,ri; i = li = ri = 0; while ( i < totElem) { if ((li < l.length) && (ri= l.length) { while (ri < r.length) { a[i] = r[ri]; i++; ri++; } } if (ri >= r.length) { while (li < l.length) { a[i] = l[li]; li++; i++; } } } } //return a; } } 

Answer 2

在mergeSort()重新绑定A时：

  A = merge(leftArray,rightArray); 

这对main()中的inputArray没有影响。

您需要从mergeSort()返回已排序的数组，与从merge()返回它的方式类似。

 static int[] mergeSort(int[] A) { ... return A; } 

并在main() ：

  int[] mergedArray = mergeSort(inputArray); for (int j = 0; j < mergedArray.length; j++) { System.out.println(mergedArray[j]); } 

Answer 3

问题是java是按值传递而不是通过引用传递…当您在merge方法中分配给数组A时，您正在将引用的副本更改为A而不是对A本身的引用。 因此，您需要将A传递给您的合并方法并对A进行结构更改。

Answer 4

问题在于：

 A = merge(leftArray,rightArray); 

现在您的合并数组执行此操作：

 static int[] merge(int[] l, int[] r) { int[] a = new int[totElem]; // bunch of code return a; } 

当你开始时，A是对inputArray的引用。 但后来你重新分配它是合并后的任何东西。 不幸的是，这并没有触及mainArray在main方法中的含义。 这基本上说“哦，看看你做的所有工作……扔掉它！”

你可以用类似的东西改变它

 static int[] mergeSort(int[] A) { // A = merge... // not this return merge... // use this } 

然后在你的主要方法中，你可以做到

 int[] merged = mergeSort(inputArray); for(int i : merged) System.out.println(i); 

Answer 5

 public class MergeSort{ public static void sort(int[] in){ if(in.length <2) return; //do not need to sort int mid = in.length/2; int left[] = new int[mid]; int right[] = new int[in.length-mid]; for(int i=0; i 

Answer 6

假设您的mergefunction正确：

 static int[] mergeSort(int[] A) { if (A.length > 1) { int q = A.length/2; int[] leftArray = Arrays.copyOfRange(A, 0, q); int[] rightArray = Arrays.copyOfRange(A,q+1,A.length); return merge(mergeSort(leftArray),mergeSort(rightArray)); } else return A; } 

因为我们需要返回数组，所以如果它只有一个元素，我们返回A未修改，否则我们合并排序数组的左右部分的结果。

Answer 7

 public void sort(int[] randomNumbersArrray) { copy = randomNumbersArrray.clone(); mergeSort(0 , copy.length - 1); } private void mergeSort(int low, int high) { if(low < high) { int mid = ((low + high) / 2); mergeSort(low, mid); //left side mergeSort(mid + 1, high); // right side merge(low, mid, high); //combine them } } private void merge(int low, int mid, int high) { int temp[] = new int[high - low + 1]; int left = low; int right = mid + 1; int index = 0; // compare each item for equality while(left <= mid && right <= high) { if(copy[left] < copy[right]) { temp[index] = copy[left]; left++; }else { temp[index] = copy[right]; right++; } index++; } // if there is any remaining loop through them while(left <= mid || right <= high) { if( left <= mid) { temp[index] = copy[left]; left++; index++; }else if(right <= high) { temp[index] = copy[right]; right++; index++; } } // copy back to array for(int i = 0; i < temp.length; i++) { copy[low + i] = temp[i]; } } 

Answer 8

 package Sorting; public class MergeSort { private int[] original; private int len; public MergeSort(int length){ len = length; original = new int[len]; original[0]=10; original[1]=9; original[2]=8; original[3]=7; original[4]=6; original[5]=5; original[6]=4; original[7]=3; original[8]=2; original[9]=1; int[] aux = new int[len]; for(int i=0;i 

Answer 9

上面的代码有点混乱从不使用带有名称的变量：“k”，“j”，“m”，……这使得代码非常混乱

以更简单的方式遵循代码……

 import java.util.Arrays; public class MergeSort { public static void main(String[] args) { Integer[] itens = {2,6,4,9,1,3,8,7,0}; Integer[] tmp = new Integer[itens.length]; int left = 0; int right = itens.length - 1; mergeSort(itens, tmp, left, right); System.out.println(Arrays.toString(itens)); } private static void mergeSort(Integer[] itens, Integer[] tmpArray, int left, int right) { if(itens == null || itens.length == 0 || left >= right){ return; } int midle = (left + right) / 2; mergeSort(itens, tmpArray, left, midle); mergeSort(itens, tmpArray, midle + 1, right); merge(itens, tmpArray, left, midle + 1, right); } private static void merge(Integer[] itens, Integer[] tmpArray, int left, int right, int rightEnd) { int leftEnd = right - 1; int tmpIndex = left; while (left <= leftEnd && right <= rightEnd){ if (itens[left] < itens[right] ){ tmpArray[tmpIndex++] = itens[left++]; } else { tmpArray[tmpIndex++] = itens[right++]; } } while (left <= leftEnd) { // Copy rest of LEFT half tmpArray[tmpIndex++] = itens[left++]; } while (right <= rightEnd) { // Copy rest of RIGHT half tmpArray[tmpIndex++] = itens[right++]; } while(rightEnd >= 0){ // Copy TEMP back itens[rightEnd] = tmpArray[rightEnd--]; } } } 

Answer 10

不妨添加我对此的看法：采用两个int数组并合并它们。 其中’result’是一个大小为a.length + b.length的数组

 public static void merge( int[] a, int[] b, int[] result ) { int i = 0, j = 0; while ( true ) { if ( i == a.length ) { if ( j == b.length ) return; result[ i + j ] = b[ j ]; j++; } else if ( j == b.length ) { result[ i + j ] = a[ i ]; i++; } else if ( a[ i ] < b[ j ] ) { result[ i + j ] = a[ i ]; i++; } else { result[ i + j ] = b[ j ]; j++; } } } 

Answer 11

 public class MyMergeSort { private int[] array; private int[] tempMergArr; private int length; public static void main(String a[]){ int[] inputArr = {45,23,11,89,77,98,4,28,65,43}; MyMergeSort mms = new MyMergeSort(); mms.sort(inputArr); for(int i:inputArr){ System.out.print(i); System.out.print(" "); } } public void sort(int inputArr[]) { this.array = inputArr; this.length = inputArr.length; this.tempMergArr = new int[length]; doMergeSort(0, length - 1); } private void doMergeSort(int lowerIndex, int higherIndex) { if (lowerIndex < higherIndex) { int middle = lowerIndex + (higherIndex - lowerIndex) / 2; // Below step sorts the left side of the array doMergeSort(lowerIndex, middle); // Below step sorts the right side of the array doMergeSort(middle + 1, higherIndex); // Now merge both sides mergeParts(lowerIndex, middle, higherIndex); } } private void mergeParts(int lowerIndex, int middle, int higherIndex) { for (int i = lowerIndex; i <= higherIndex; i++) { tempMergArr[i] = array[i]; } int i = lowerIndex; int j = middle + 1; int k = lowerIndex; while (i <= middle && j <= higherIndex) { if (tempMergArr[i] <= tempMergArr[j]) { array[k] = tempMergArr[i]; i++; } else { array[k] = tempMergArr[j]; j++; } k++; } while (i <= middle) { array[k] = tempMergArr[i]; k++; i++; } } }