我一直在尝试实现我的“自己的”mergesort,它似乎适用于较小的值,但我在一个随机顺序为1-100000的数组中尝试,当我打印出来时,得到一些奇怪的数字。我已经追踪了10次都没找到。

public static void mergeSort(int[] array){
    if(array.length > 1){

       int midPoint = array.length/2;

       int[] leftArray = new int[midPoint];
       int[] rightArray = new int[array.length - midPoint];

       System.arraycopy(array, 0, leftArray, 0, midPoint);
       System.arraycopy(array, midPoint, rightArray, 0, array.length - midPoint);

       mergeSort(leftArray);
       mergeSort(rightArray);

       merge(leftArray, rightArray, array);
    }
}

public static void merge(int[] left, int[] right, int[] bigArray){
    int counterLeft = 0, counterRight = 0, counterNewArray = 0;

    while(counterLeft < left.length && counterRight < right.length){
        if(left[counterLeft] < right[counterRight]){
            bigArray[counterNewArray] = left[counterLeft];
            counterLeft++;
            counterNewArray++;
        }else{
            bigArray[counterNewArray] = right[counterRight];
            counterRight++;
            counterNewArray++;
        }
    }

        while(counterLeft < left.length){
                bigArray[counterNewArray] = left[counterLeft];
                counterLeft++;
        }

        while(counterRight < right.length){
                bigArray[counterNewArray] = right[counterRight];
                counterRight++;
        }

        if(bigArray.length < 500){
            System.out.println("Merged array:");
            for(int i = 0; i < bigArray.length; i++){
                System.out.println(bigArray[i]);
            }
        }
}

最佳答案

merge结束时,当您添加每边的剩余部分时…您不会递增counterNewArray这将导致一组值被分配到一个点,相互覆盖…并在bigArray的尾部留下无效值(零,IIRC)。

关于java - 合并排序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14658362/

10-10 08:04