java - 我的合并排序算法的输出未排序

Question

下面是我用java编写的合并排序算法的代码。它需要一个字符串和一个 int 数组，因为我需要使用 int 数组对字符串数组进行排序。此实现还计算反转。我的问题是，它可以很好地计算反转，但是当我打印出数组本身时，它根本没有改变。

主要方法是我测试一个 6 长数组并打印出反转和数组。当我运行此测试时，我会打印出以下内容。

4
1, 3, 4, 6, 2, 5
1、3、4、6、2、5

public class Test {

private static int[] intSorted;
private static String[] stringSorted;

public static void main(String[] args) {

    //Creates new string to sort

    String[] string3 = {"1","3","4","6","2","5"};

    //Creates new int to sort

    int[] intt3 = {1,3,4,6,2,5};

    //Calls sortAndCount on int and prints the number of inversions

    System.out.println(sortAndCount(intt3, string3));

    //Turns the int array into a string to print

    StringBuilder intBuild = new StringBuilder();
    for(int i = 0; i < intSorted.length; i++){
        if(i+1 == intSorted.length){
            intBuild.append(intSorted[i]);
        }
        else{
        intBuild.append(intSorted[i] + ", ");
        }
    }

    //Turns the string array into a string to print

    StringBuilder stringBuild = new StringBuilder();
    for(int i = 0; i < stringSorted.length; i++){
        if(i+1 == stringSorted.length){
            stringBuild.append(stringSorted[i]);
        }
        else{
        stringBuild.append(stringSorted[i] + ", ");
        }
    }

    System.out.println(intBuild);
    System.out.println(stringBuild);


}

private static int sortAndCount(int intToSort[], String stringToSort[]){

    int inversionsLeft;
    int inversionsRight;
    int inversionsMerged;

    if(intToSort.length == 1){
        return 0;
    }

    int m = intToSort.length/2;

    int[] intLeft = new int[m];
    String[] stringLeft = new String[m];

    int[] intRight = new int[intToSort.length-m];
    String[] stringRight = new String[intToSort.length-m];


    for (int i=0; i < m; i++){
        intLeft[i] = intToSort[i];
        stringLeft[i] = stringToSort[i];
    }

    for (int i = 0;i < intRight.length; i++){
            intRight[i] = intToSort[m+i];
            stringRight[i] = stringToSort[m+i];
    }

    inversionsLeft = sortAndCount(intLeft, stringLeft);
    inversionsRight = sortAndCount(intRight, stringRight);

    intSorted = new int[intToSort.length];
    stringSorted = new String[stringToSort.length];

    inversionsMerged = mergeAndCount(intLeft, intRight, stringLeft, stringRight);

    return(inversionsLeft + inversionsRight + inversionsMerged);

}

private static int mergeAndCount(int[] intLeft, int[] intRight, String[] stringLeft, String[] stringRight){

    int count = 0;
    int i = 0;
    int j = 0;
    int k = 0;

    while(i < intLeft.length && j < intRight.length){

        if(intLeft[i] < intRight[j]){
            intSorted[k] = intLeft[i];
            stringSorted[k] = stringLeft[i];
            i++;
        }

        else{
            intSorted[k] = intRight[j];
            stringSorted[k] = stringRight[j];
            count += intLeft.length - i + 1;
            j++;
        }

        k++;

    }

     while (i < intLeft.length)
        {
            intSorted[k] = intLeft[i];
            stringSorted[k] = stringLeft[i];
            k++;
            i++;

        }

     while (j < intRight.length)
        {
            intSorted[k] = intRight[j];
            stringSorted[k] = stringRight[j];
            j++;
            k++;

        }

     return count;

}

Answer 1

我认为问题出在这里(我添加的评论):

    // Create some arrays into which we write the result of merging the 
    // arrays intLeft, intRight, stringLeft, stringRight.
    intSorted = new int[intToSort.length];
    stringSorted = new String[stringToSort.length];

    // Do the merging into intSorted and stringSorted.
    inversionsMerged = mergeAndCount(intLeft, intRight, stringLeft, stringRight);

    // Oops... we haven't updated intToSort and stringToSort!
    // We need to copy the sorted values from intSorted and stringSorted
    // back into intToSort and stringToSort before we return.

    return(inversionsLeft + inversionsRight + inversionsMerged);

我将让你来填补这个空白。

我拿了你的代码，自己填补了空白，然后运行了它。这似乎有效；这是我得到的输出:

7
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6

祝你好运!