java - 自定义合并排序算法不起作用

Question

我开始研究数据结构和算法。我了解 Merge-Sort 背后的逻辑，并试图在没有引用的情况下自己编写一个这样的代码。它正在生成一些 ArrayIndexOutOfBounds 错误。我了解错误，但无法发现它。这是我的小代码:

package merge.sort;


public class MergeSort {


//implementing the merge sort Alogrithm

public int[] mergeSort (int [] numbers){
    //first step: break the array cosistently into sub-parts untill you arrive at base case.


    if(numbers.length <= 1){
             return numbers;



    }

    else {

       int [] output = new int[numbers.length];

         int[] firsthalf = new int[numbers.length/2];

        int[] secondhalf = new int[numbers.length/2];


    System.arraycopy(numbers, 0, firsthalf, 0, firsthalf.length);

    System.arraycopy(numbers, firsthalf.length, secondhalf, 0, secondhalf.length); 



        System.out.println("\nSorted 1: "+mergeSort(secondhalf)[0]+"\n\n");
        System.out.println("Sorted 2:"+mergeSort(secondhalf)[0]+"\n\n");

        int i = 0;
        int j = 0; 

        for (int k = 0; k < numbers.length; k++){
           if(mergeSort(firsthalf)[i] < mergeSort(secondhalf)[j]){
            output[k] = mergeSort(firsthalf)[i];
            i++;
            } 

           else{
            output[k] = mergeSort(secondhalf)[j];
            j++;
            }

        }

         return output;

    }

}

public static void main(String[] args) {
   MergeSort test  = new MergeSort();

   int[] positions = {4,2,7,9};
   //int[] positions = {1};
   int[] sorted = test.mergeSort(positions);

   System.out.print("The positions in sorted order:");
   for(int i =0; i<sorted.length; i++){
       if (i==sorted.length -1){
           System.out.print(sorted[i]+".");
       }
       else{
           System.out.print(sorted[i]+",");
       }

   }

}

}

Answer 1

您需要处理数字为奇数的情况。所以 firsthalf.length 应该是 numbers.length/2(向下舍入)，secondhalf.length 应该是余数。

int[] firsthalf = new int[numbers.length/2];
int[] secondhalf = new int[numbers.length - firsthalf.length];

例如，如果您有 5 个数字，则 firsthalf.length 将为 2，secondhalf.length 将为 3。

另外，不要在 firsthalf 和 secondhalf 上一遍又一遍地调用 mergeSort 会更有效率。只需调用一次:

int[] sortedfirsthalf = mergeSort(firsthalf);
int[] sortedsecondhalf = mergeSort(secondhalf);

然后引用这些数组而不是例如mergeSort(firsthalf).

最后，当你合并两者时，如果你到达一个数组的末尾，在做进一步比较时注意不要索引超过它的末尾:

for (int k = 0; k < numbers.length; k++){
    if(i >= sortedfirsthalf.length)
    {
        output[k] = sortedsecondhalf[j];
        j++;
    }
    else if(j >= sortedsecondhalf.length)
    {
        output[k] = sortedfirsthalf[i];
        i++;
    }
    else if(sortedfirsthalf[i] < sortedsecondhalf[j]) 
    {
        output[k] = sortedfirsthalf[i];
        i++;
    } 
    else
    {
        output[k] = sortedsecondhalf[j];
        j++;
    }
}

看看是否可以进一步优化它。