java - 合并排序 - 使用 Int 数组对字符串数组进行排序

Question

对于这个项目，我得到了一个字符串数组和一个整数数组。 int[1] 是 string[1] 的排名。我需要使用 mergesort 按从 1 到 n 的顺序对 int 数组进行排序，我已经在下面完成了。但是我还需要在移动 int 数组时切换字符串数组的位置，以便对它们进行排序，如果这有意义的话？我无法弄清楚我的编码有什么问题，即使我的想法真的可行，但我一直在 stringSorted[k] = stringRight[j] 上收到数组索引越界错误，我无法弄清楚是否有一种解决这个问题的方法。本质上，当一个 int 被添加到 sortedInt 数组时，我也将该元素添加到已排序的 String 数组。感谢您的帮助，如果有任何不合理之处请告诉我

private static int sortAndCount(int intToSort[]){

    int inversionsLeft;
    int inversionsRight;
    int inversionsMerged;

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

    int m = intToSort.length/2;

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

    int[] intRight = new int[intToSort.length-m];
    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);
    inversionsRight = sortAndCount(intRight);

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

    inversionsMerged = mergeAndCount(intLeft, intRight);

    return(inversionsLeft + inversionsRight + inversionsMerged);

}

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

    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

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

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

您会在这里注意到，对于 int 数组，您正在创建新变量，对于字符串，您正在替换外部变量。这会使您的 string 数组在每次递归调用时变小，而您的 int 数组会传递给每个方法。

当您开始调用 mergeAndCount 时，stringLeft 和 stringRight 非常小，而适当大小的 intLeft 和 intRight 作为参数传递。