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

Question

对于这个项目，我得到了一个字符串数组和一个整数数组。int[1]是字符串[1]的排名。我需要使用mergesort按1到n的顺序对int数组进行排序，我在下面已经完成了这项工作。但是当int数组被移动时，我还需要切换字符串数组的位置，以便它们都被排序，如果这有意义的话？我不知道我的编码有什么问题，甚至我的想法是否真的有效，但我一直在stringSorted[k]=stringRight[j]上得到一个数组索引越界错误，我不知道是否有办法解决这个问题。本质上，当一个int被添加到sortedInt数组中时，我也将该元素添加到排序字符串数组中。谢谢你的帮助，如果有什么不对劲，请告诉我

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时，string左侧和stringright非常小，而适当大小的int左侧和intright作为参数传递。