java - 归并排序问题参数

Question

import java.lang.reflect.Array; 

public class Sorting {
public static void mergeSort(CompareInt[] arr) {

   for(int i=0;i<=arr.length-1;i++){
        System.out.println("Initial Arr element:"+arr[i].val);
        } 
    CompareInt[] arrAux;
    arrAux = new CompareInt[arr.length];
    mergeS(arr,0,arr.length-1,arrAux);       
}

public static void mergeS(CompareInt[] arr,int startI,int endI,CompareInt[] arrAux){
    //System.out.println("StartIndex:"+startI+" EndIndex:"+endI);
    if(endI-startI<=0)
        return;

    int mid = (startI+endI)/2;
   // System.out.println("Midpoint value:"+mid);

    mergeS(arr,startI,mid);
    mergeS(arr,mid+1,endI);

  //  System.out.println("Inside mergeS");
  //  System.out.println("StartIndex:"+startI+" EndIndex:"+endI+" Midpoint value:"+mid);
 //   System.out.println("Arr length:"+arr.length);

    arrAux = merge(arr,mid);

    for(int i=0;i<=arr.length-1;i++){
        arr[i]=arrAux[i];
        System.out.println("Arr element:"+arr[i].val);
        }
}


public static CompareInt[] merge(CompareInt[] arr,int midpoint){
int i=0,j=0,k=0;
int n1 = arr.length-midpoint;
int n2 = arr.length-n1;

//System.out.println("Midpoint value inside merge:"+midpoint);
//System.out.println("N1:"+n1+" N2:"+n2);

CompareInt[] L;
CompareInt[] R;
CompareInt[] resA;
L = new CompareInt[n1];
R = new CompareInt[n2];
resA = new CompareInt[n1+n2];


for(i=0;i<n1;i++){
    L[i]=arr[i];
  // System.out.println("Inside Left loop"+i);
  // System.out.println(L[i].val);
    }

for(j=0;j<n2;j++){
    R[j]=arr[midpoint+j+1];
   // System.out.println("Inside Right loop "+j);
   // System.out.println(R[j].val);
}

i=0;
j=0;
k=0;

while(i<n1 && j<n2){
    if(L[i].compareTo(R[j])<=0){
        resA[k]=L[i];
       // System.out.println(resA[i].val);
        i++;
    }
    else{
        resA[k]=R[j];
       // System.out.println(resA[j].val);
        j++;
    }
    k++;
}

while(i<n1){
    resA[k]=L[i];
    //System.out.println(resA[k].val);
    i++;
    k++;
}

while(j<n2){
    resA[k]=R[j];
    //System.out.println(resA[k].val);
    j++;
    k++;
}

 return resA;  
}
}

我在 mereS(..) 行得到的实际参数列表和正式参数列表的长度不同 如何解决此错误？是否有任何方法可以在实际参数和形式参数中使用不同数量的参数运行。

这就是Pseudo code给出 .. 伪代码修改: if (hi - lo <= 0)”，而不是“if (hi - lo <= 1)”。 aux <- 合并(A[lo:mid], A[mid+1:hi])

Answer 1

此代码将解决您的问题:

public static void main(String[] args) {

    int arr[] = {12, 11, 13, 5, 6, 7};

    System.out.println("\nSorted array");
    for(int i=0;i<=arr.length-1;i++){
        System.out.println("Initial Arr element:"+arr[i]);
    }

    mergeS(arr, 0, arr.length-1);

    System.out.println("\nSorted array");
    for(int i=0;i<=arr.length-1;i++){
        System.out.println("Sorted Arr element:"+arr[i]);
    }
}


public static void mergeS(int[] arr,int startI,int endI){
    //System.out.println("StartIndex:"+startI+" EndIndex:"+endI)

    if (startI< endI)
    {
        // Find the middle point
        int m = (startI+endI)/2;

        // Sort first and second halves
        mergeS(arr,startI, m);
        mergeS(arr , m+1, endI);

        // Merge the sorted halves
        merge(arr, startI,m, endI);
    }
}


public static void merge(int arr[], int startI, int midpoint, int endI){
    // Find sizes of two subarrays to be merged
    int n1 = midpoint - startI + 1;
    int n2 = endI - midpoint;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[startI + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[midpoint + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = startI;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}