Java递归合并排序

目前我对我的递归合并排序程序感到震惊，我一直在寻找问题的所在，我似乎无法找到它。Java递归合并排序

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]; 
    } 
} 

}

这里是一个什么应该发生

排序之前的样品：泽科鲍勃阿里约翰乔迪杰米比尔罗布泽科克莱顿

排序后： Ali Bill 鲍勃克莱顿杰米乔迪约翰罗布泽科泽科

也是我做我的主要驱动力是在这里也

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]); 
} 
}

来源

2015-05-02 Josh Figgles

你的输出是什么？ – Ajoy

你应该打印每一次迭代，这将有助于你看到真正发生的事情 – Typo

@Ajoy“thread in main”java.lang.ArrayIndexOutOfBoundsException中的异常：9 \t at mergesort.MergeSort.merge（MergeSort.java ：59） \t在mergesort.MergeSort.mergeSort（MergeSort.java:32） \t在mergesort.MergeSort.mergeSort（MergeSort.java:29） \t在mergesort.MergeSort.mergeSort（MergeSort.java:29） \t在mergesort.MergeSort.mergeSort（MergeSort.java:29） \t at mergesort.MergeSort.mergeSort（MergeSort.java:19） \t at mergesort.Driver.main（Driver.java ：15） “ –

你merge方法有很多问题。

取每个for循环，写一条1行注释来描述它应该做什么。
做不是声明一个变量（如j），然后重复使用它的多个循环。将循环变量限制在循环范围内，例如for (int j = ..; .. ; ..)。
更正您的缩进并确保嵌套循环确实是嵌套的。
为merge方法编写几个测试用例，并与所有递归分别测试该方法。

来源

2015-05-02 04:24:26 Misha

Java递归合并排序

回答

相关问题