java - 保持两个数组，String[] 和 int[]，与归并排序并行

Question

我无法在我的合并排序算法中保持两个数组并行。假设我有数组 defMergeSort 和 intMergeSort2。

我想按字典顺序对 String defMergeSort，

String[] defMergeSort = {"Echo", "Alpha", "Charlie", "Beta", "Alpha", "Echo"};

数组intMergeSort2表示与defMergeSort平行的元素位置。 (例如:defMergeSort[0] = Echo 取决于 intMergeSort2[0] = 0，defMergeSort[3] = Beta 取决于 intMergeSort2[3] = 3)intMergeSort2 将与 defMergeSort 并行重新排列，尽管不是按数字排序，

int[] intMergeSort2 = {0,1,2,3,4,5};

最终结果应该与此类似(不确定我示例中 intMergeSort2[] 的并行排序对于 defMergeSort[] 中的重复字符串是否正确):

• defMergeSort[0] Alpha = intMergeSort2[1] 1
• defMergeSort[1] Alpha = intMergeSort2[4] 4
• defMergeSort[2] Beta = intMergeSort2[3] 3
• defMergeSort[3] 查理 = intMergeSort2[2] 2
• defMergeSort[4] Echo = intMergeSort2[0] 0
• defMergeSort[5] Echo = intMergeSort2[5] 5

下面的合并排序算法可以按字典顺序对 defMergeSort 进行排序，尽管我无法弄清楚如何按照上面的规定保持 defMergeSort 并行:

//mergeSort code found at:
//http://www.buildingjavaprograms.com/code-files/2ed/ch13/MergeSort.java
public static void mergeSort(String[] defMergeSort, int[] intMergeSort2) {
    if (defMergeSort.length > 1) {
        // split array into two halves
        String[] left = leftHalf(defMergeSort);
        String[] right = rightHalf(defMergeSort);
        // recursively sort the two halves
        mergeSort(left, intMergeSort2);
        mergeSort(right, intMergeSort2);
        // merge the sorted halves into a sorted whole
        merge(defMergeSort, intMergeSort2, left, right);
    }
}

// Returns the first half of the given array.
public static String[] leftHalf(String[] defMergeSort) {
    int size1 = defMergeSort.length / 2;
    String[] left = new String[size1];
    for (int i = 0; i < size1; i++) {
        left[i] = defMergeSort[i];
    }
    return left;
}

// Returns the second half of the given array.
public static String[] rightHalf(String[] defMergeSort) {
    int size1 = defMergeSort.length / 2;
    int size2 = defMergeSort.length - size1;
    String[] right = new String[size2];
    for (int i = 0; i < size2; i++) {
        right[i] = defMergeSort[i + size1];
    }
    return right;
}

// Merges the given left and right arrays into the given
// result array.  Second, working version.
// pre : result is empty; left/right are sorted
// post: result contains result of merging sorted lists;
public static void merge(String[] defMergeSort, int[] intMergeSort2,
String[] left, String[] right){
    int i1 = 0;   // index into left array
    int i2 = 0;   // index into right array
    for(int i = 0; i < defMergeSort.length; i++){
        if (i2 >= right.length || (i1 < left.length &&
        left[i1].compareTo(right[i2]) <= 0)) {
            defMergeSort[i] = left[i1];
            i1++;
        } else {
            defMergeSort[i] = right[i2];
            i2++;
        }
    }
}

Answer 1

定义一个包含整数和字符串值的对象，拥有该对象的单个数组，对该数组进行排序。

即

class DataElement {
    final String str;
    final int i;

    //Add constructor here
}

DataElement[] array; // sort this array

请注意，您需要在 DataElement 中实现 Comparable 或为排序方法指定一个 Comparator 以控制排序。