12

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

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;
            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] < r[ri]) {
                    a[i] = l[li];
                    i++;
                    li++;
                } else {
                    a[i] = r[ri];
                    i++;
                    ri++;
                }
            } else {
                if (li >= 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;
    }
}
4

12 回答 12

24

这是您的代码的更正版本：

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<r.length)) {
                if (l[li] < r[ri]) {
                    a[i] = l[li];
                    i++;
                    li++;
                }
                else {
                    a[i] = r[ri];
                    i++;
                    ri++;
                }
            }
            else {
                if (li >= 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;

    }

}
于 2012-12-05T16:30:39.033 回答
10

当您重新绑定A时mergeSort()：

        A = merge(leftArray,rightArray);

inputArray这在in 中无效main()。

您需要返回排序后的数组 frommergeSort()类似于从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]);
    }
于 2012-12-05T15:48:51.050 回答
2

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

于 2013-05-22T12:54:22.840 回答
1 
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<mid; i++){ //copy left
        left[i] = in[i];
    }
    for(int i=0; i<in.length-mid; i++){ //copy right
        right[i] = in[mid+i];
    }
    sort(left);
    sort(right);
    merge(left, right, in);
}

private static void merge(int[] a, int[] b, int[] all){
    int i=0, j=0, k=0;
    while(i<a.length && j<b.length){ //merge back
        if(a[i] < b[j]){
            all[k] = a[i];
            i++;
        }else{
            all[k] = b[j];
            j++;
        }
        k++;
    }
    while(i<a.length){ //left remaining
        all[k++] = a[i++];
    }
    while(j<b.length){ //right remaining
        all[k++] = b[j++];
    }
}

public static void main(String[] args){
    int[] a = {2,3,6,4,9,22,12,1};
    sort(a);    
    for(int j=0; j<a.length; j++){
        System.out.print(a[j] + " ");
    }   
 }
}
于 2014-04-26T13:24:57.783 回答
1

问题出在这里：

A = merge(leftArray,rightArray);

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

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

开始时，A 是对 inputArray 的引用。但是随后您将其重新分配为合并后的任何内容。不幸的是，这并没有触及 main 方法中的 inputArray 。这基本上是说“哦，看看你所做的所有工作......把它扔掉！”

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

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);
于 2012-12-05T15:52:57.890 回答
0 
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];
    }
}
于 2013-11-18T03:06:53.173 回答
0 
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<len;++i){
        aux[i]=original[i];
    }

    Sort(aux,0,len);


}

public void Sort(int[] aux,int start, int end){

    int mid = start + (end-start)/2;

    if(start < end){
        Sort(aux, start, mid-1);
        Sort(aux, mid, end);
        Merge(aux, start, mid, end);
    }
}

public void Merge(int[] aux, int start, int mid, int end){// while array passing be careful of shallow and deep copying

    for(int i=start; i<=end; ++i)
        auxilary[i] = original[i];

    int i = start;
    int k = start;
    int j = mid+1;
    while(i < mid && j <end){
        if(aux[i] < aux[j]){
            original[k++] = aux[i++];
        }
        else{
            original[k++] = aux[j++];
        }   
    }
    if(i == mid){
        while(j < end){
            original[k++] = aux[j++];
        }
    }
    if(j == end){
        while(i < mid){
            original[k++] = aux[i++];
        }
    }
}
public void disp(){
    for(int i=0;i<len;++i)
        System.out.print(original[i]+" ");
}
public static void main(String[] args) {

    MergeSort ms = new MergeSort(10);

    ms.disp();

}

}
于 2014-04-19T20:17:05.407 回答
0 
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++;
        }

    }
}
于 2018-07-10T00:41:05.557 回答
0

不妨添加我对此的看法：采用两个 int 数组并将它们合并。其中“结果”是大小为 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++;
    }
  }
}
于 2017-05-18T18:14:36.097 回答
0

我有一个并行版本的合并排序。我受益于 RecursiveAction 和 ForkJoinPool。请注意，工人的数量可以设置为常数。但是，我将其设置为机器上可用处理器的数量。

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class ParallelMergeSorter {

    private int[] array;

    public ParallelMergeSorter(int[] array) {
        this.array = array;
    }

    public int[] sort() {
        int numWorkers = Runtime.getRuntime().availableProcessors(); // Get number of available processors
        ForkJoinPool pool = new ForkJoinPool(numWorkers);
        pool.invoke(new ParallelWorker(0, array.length - 1));
        return array;
    }

    private class ParallelWorker extends RecursiveAction {
        private int left, right;

        public ParallelWorker(int left, int right) {
            this.left = left;
            this.right = right;
        }

        protected void compute() {
            if (left < right) {
                int mid = (left + right) / 2;
                ParallelWorker leftWorker = new ParallelWorker(left, mid);
                ParallelWorker rightWorker = new ParallelWorker(mid + 1, right);
                invokeAll(leftWorker, rightWorker);
                merge(left, mid, right);
            }
        }

        private void merge(int left, int mid, int right) {
            int[] leftTempArray = Arrays.copyOfRange(array, left, mid + 1);
            int[] rightTempArray = Arrays.copyOfRange(array, mid + 1, right + 1);
            int leftTempIndex = 0, rightTempIndex = 0, mergeIndex = left;
            while (leftTempIndex < mid - left + 1 || rightTempIndex < right - mid) {
                if (leftTempIndex < mid - left + 1 && rightTempIndex < right - mid) {
                    if (leftTempArray[leftTempIndex] <= rightTempArray[rightTempIndex]) {
                        array[mergeIndex] = leftTempArray[leftTempIndex];
                        leftTempIndex++;
                    } else {
                        array[mergeIndex] = rightTempArray[rightTempIndex];
                        rightTempIndex++;
                    }
                } else if (leftTempIndex < mid - left + 1) {
                    array[mergeIndex] = leftTempArray[leftTempIndex];
                    leftTempIndex++;
                } else if (rightTempIndex < right - mid) {
                    array[mergeIndex] = rightTempArray[rightTempIndex];
                    rightTempIndex++;
                }
                mergeIndex++;
            }
        }
    }

}
于 2020-11-24T01:51:52.193 回答
0

上面的代码有点混乱 千万不要使用名称为：“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--];
        }
    }
}
于 2016-09-25T23:47:25.190 回答
0

非常简单易懂

static void sort(char[] data) {
    int length = data.length;
    if (length < 2)
        return;
    int mid = length / 2;
    char[] left = new char[mid];
    char[] right = new char[length - mid];

    for(int i=0;i<mid;i++) {
        left[i]=data[i];
    }

    for(int i=0,j=mid;j<length;i++,j++) {
        right[i]=data[j];
    }

    sort(left);
    sort(right);
    merge(left, right, data);

}

static void merge(char[] left, char[] right, char[] og) {
    int i = 0, j = 0, k = 0;
    while(i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            og[k++] = left[i++];
        } else {
            og[k++] = right[j++];
        }
    }
    while (i < left.length) {
        og[k++] = left[i++];
    }
    while (j < right.length) {
        og[k++] = right[j++];
    }

}
于 2019-01-21T06:56:15.847 回答