合并排序永远运行

Question

我想根据第二个元素对 2d int 数组进行排序，这就是我想出的。但这似乎不起作用。我知道有一个 Arrays.sort(array, Comparator) 我可以使用，但我想为了好玩而编写自己的排序算法。谁能帮帮我吗？

ip = [[5,10],[2,5],[4,7],[3,9]]

预期操作 = [[5,10],[3,9],[4,7],[2,5]]

void mergeSort(int[][] boxTypes){
    int mid = boxTypes.length / 2;
    int[][] left = new int[mid][2];
    int[][] right = new int[boxTypes.length - mid][2];
    
    for(int i = 0; i < mid; i++) left[i] = boxTypes[i];
    for(int i = mid; i < boxTypes.length; i++) right[i - mid] = boxTypes[i];
    
    mergeSort(left);
    mergeSort(right);
    
    merge(left, right, boxTypes);
}

void merge(int[][] left, int[][] right, int[][] boxTypes){
    int i = 0; int j = 0; int k = 0;
    
    while(i < left.length && j < right.length){
        if(left[i][1] < right[j][1]){
            boxTypes[k][0] = left[i][0];
            boxTypes[k][1] = left[i++][1];
        } else {
            boxTypes[k][0] = right[j][0];
            boxTypes[k][1] = right[j++][1];
        }
        k++;
    }
    
    while(i < left.length) boxTypes[k++] = left[i++];
    while(j < right.length) boxTypes[k++] = right[j++];
}

Answer 1

你永远不会停止递归：

在第一步中，您将 boxTypes 分成两个长度为 2 的数组。
在第二步中，您将第一个长度为 2 的数组拆分为两个长度为 1 的数组。
在第三步中，您将第一个长度为 1 的数组拆分为一个长度为 0 的数组和一个长度为 1 的数组。
在第四步（以及随后的每一步）中，您尝试将长度为 0 的数组拆分为两个长度为零的数组。

一旦 boxTypes 的长度小于或等于 1，您就需要停止递归（因为长度为 0 或 1 的数组是平凡排序的）：

void mergeSort(int[][] boxTypes){
    if (boxTypes.length <= 1) return;
    int mid = boxTypes.length / 2;
    int[][] left = new int[mid][2];
    int[][] right = new int[boxTypes.length - mid][2];
    
    for(int i = 0; i < mid; i++) left[i] = boxTypes[i];
    for(int i = mid; i < boxTypes.length; i++) right[i - mid] = boxTypes[i];
    
    mergeSort(left);
    mergeSort(right);
    
    merge(left, right, boxTypes);
}

合并排序永远运行

Merge sort runs forever

java

sorting

mergesort