Java 递归归并排序

Question

目前我对递归合并排序程序感到震惊，我一直在寻找问题出在哪里，但似乎找不到它。

package mergesort;

import java.util.ArrayList;

public class MergeSort {

public MergeSort() {
    // TODO Auto-generated constructor stub
}

public static <T extends Comparable<? super T>> void mergesort(T[] list, int n)
{
    mergeSort(list,0,n-1);
}

static <T extends Comparable<? super T>> 
void mergeSort(T[] tempArray, int firstHalfSorted, int secondHalfSorted){
    T[] temp = (T[]) new Comparable <?>[tempArray.length];
    mergeSort(tempArray, temp, firstHalfSorted, secondHalfSorted);

}


private static <T extends Comparable<? super T>> 
void mergeSort (T[ ] tempArray, T[] a, int firstHalfSorted, int secondHalfSorted){
    if (firstHalfSorted < secondHalfSorted)
    {
        int mid =   (firstHalfSorted + secondHalfSorted) / 2;
        mergeSort(tempArray,a,firstHalfSorted, mid);
        mergeSort(tempArray,a,mid+1, secondHalfSorted);
        if(tempArray[mid].compareTo(tempArray[mid+1])>0)
            merge(tempArray,a,firstHalfSorted, mid, secondHalfSorted);
    }
}

private static <T extends Comparable<? super T>> 
void merge(T[] a, T[] tempArray, int firstHalfSorted, int mid, int secondHalfSorted)
{
    int bhalf1 = firstHalfSorted;
    int ehalf1 = mid;
    int bhalf2 = mid + 1;
    int ehalf2 = secondHalfSorted;
    int j = 0;
    for(;(bhalf1 <= ehalf1) && (bhalf2 <= ehalf2); j++)
    {
        if (a[bhalf1].compareTo(a[bhalf2]) < 0)
        {
            tempArray[j] = a[bhalf1];   
            bhalf1++;
        }
        else 
        {
            tempArray[j] = a[bhalf2];
            bhalf2++;

        }

    for(;bhalf1 <= ehalf1; bhalf2++, j++)
        tempArray[j] = a[bhalf1];   
    for(;bhalf2 <= ehalf2; bhalf2++, j++)
        tempArray[j] = a[bhalf2];   
    for(j = firstHalfSorted; j <= secondHalfSorted; j++)
        a[j] = tempArray[j];
    }
}

}

这是应该发生的情况的示例

排序前:泽克鲍勃阿里约翰乔迪杰米账单抢泽克克莱顿

排序后:阿里账单鲍勃克莱顿杰米乔迪约翰抢泽克泽克

我制作的主要驱动程序也在这里

package mergesort;
import java.util.ArrayList;
import java.util.Arrays;

public class Driver <T extends Comparable<? super T>>{

public Driver() {
    // TODO Auto-generated constructor stub
}

public static <T> void main(String[] args) {

       String array[] = new String[] {"Zeke,"Bob","Ali","John","Jody","Jamie","Bill","Rob", "Zeke", "Clayton"};
    MergeSort sortList = null;
    sortList.mergeSort(array,0,10);
    for(int a=0;a<array.length;a++)
        System.out.println(array[a]);
}
}

Answer 1

您的merge方法有很多问题。

1. 获取其中的每个 for 循环，并编写一条 1 行注释来描述它应该执行的操作。
2. 请勿声明变量(如j)，然后将其重复用于多个循环。将循环变量限制在循环范围内，例如for (int j = ..; .. ; ..)。
3. 更正缩进并确保嵌套循环确实是嵌套的。
4. 为 merge 方法编写一些测试用例，并与所有递归分开测试该方法。