合并排序不排序数组

Question

我在阅读了归并排序后编写了下面的 Java 代码。运行代码没有错误，但合并排序没有对数组进行排序。它只是 returns 原始的未排序数组。我终生无法弄清楚问题出在哪里。我很感激任何线索。

public class mergeSort {

public void mergeSort(int array[], int n){

    if(n<2) return; 
    int m=n/2;
    int left[]=new int[m];
    int right[]=new int[n-m];
    int i;

    for(i=0; i<m;i++){
        left[i]=array[i];
    }
    for( i=m; i<n;i++){
        right[i-m]=array[i];
    }
    printArray(left);
    printArray(right);
    mergeSort(left, m);
    mergeSort(right, n-m);
    merge(array, left, m, right, m-n);
}

private void merge(int[] array, int[] left, int leftCount, int[] right, int rightCount) {
    int i=0,j=0,k=0;

    while(i<leftCount && j< rightCount){
        if(left[i]<=right[j]){
            array[k]=left[i];
            i++;
            k++;
        }else{
            array[k]=right[j];
            j++;
            k++;
        }
    }

    while(i<leftCount){
        array[k]=left[i];
        i++;
        k++;
    }
    while(j<rightCount){
        array[k]=right[j];
        j++;
        k++;
    }

}
 static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

public static void main(String[] args){
    int a[]={3,2,1,7,9,8};
    printArray(a);


    mergeSort m=new mergeSort();
    m.mergeSort(a, a.length);

    printArray(a);
}

}

Answer 1

你传递给merge方法的leftCount和rightCount是错误的。

而不是传递它，而是在合并方法中计算它。我通过以下更改尝试了您的代码，它运行良好。

 merge(array, left, right);
 ...
private void merge(int[] array, int[] left,  int[] right) {
    int i=0,j=0,k=0;
    int leftCount= left.length;
    int rightCount = right.length;

合并排序不排序数组

merge sort not sorting array

java

sorting

mergesort