Java 中的 Mergesort

algorithm sorting java mergesort

2022-09-05 00:25:12

我是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 < 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;
    }
}

答案 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<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;

    }

}

答案 2

当您重新绑定时：AmergeSort()

        A = merge(leftArray,rightArray);

这在中没有影响。inputArraymain()

您需要从中返回排序的数组，其方式与从返回数组的方式类似。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]);
    }