Mergesort实际上没有排序

Question

我需要实现mergesort只使用数组为我的参数。我可以看到它将它分开并重新组装，但实际上并没有对它进行分类。我确信它与我打电话的地点/方式有关。你能帮忙指出它没有提取正确的数据，所以我可以修复它吗？

public static void mergesort(Comparable[] a) { 
    a = mergeSort(a); 
} 

public static Comparable[] mergeSort(Comparable[] a) { 
    Comparable[] first, second; 
    int length1 = a.length/2; 
    int length2 = a.length - length1; 

    first = Arrays.copyOfRange(a, 0, length1); 
    second = Arrays.copyOfRange(a, length1, a.length); 

    if(length1 > 0 && length2 > 0) { 
     first = mergeSort(first); 
     System.out.print("First: "); 
     show(first); 
     second = mergeSort(second); 
     System.out.print("Second: "); 
     show(second); 
     a = merge(first, second); 
     System.out.print("\nAfter: "); 
     show(a); 
    } 
    return a; 
} 

public static Comparable[] merge(Comparable[] a, Comparable[] b) { 
    Comparable[] temp = new Comparable[a.length + b.length]; 
    int aFirst = 0, aLast = a.length - 1; 
    int bFirst = 0, bLast = b.length - 1; 
    int index = aFirst; 

    while(aFirst <= aLast && bFirst <= bLast) { 
     if(a[aFirst].compareTo(b[bFirst]) < 0) { 
      temp[index] = a[aFirst++]; 
     } else { 
      temp[index] = b[bFirst++]; 
     } 
     index++; 
    } 

    while(aFirst <= aLast) { 
     temp[index] = a[aFirst++]; 
     index++; 
    } 

    while(bFirst <= bLast) { 
      temp[index] = b[bFirst++]; 
      index++; 
    } 
    return temp; 
} 

编辑添加：这是我正在使用的主要方法（我不能改变）的一个片段。

String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; 
    mergesort(b); 
    assert isSorted(b); 
    show(b); 

Answer 1

这两个电话：阵列first和second到新阵列

mergesort(first); 
mergesort(second); 

排序，但你忽略这些排序阵列。您的代码应该是：

first = mergeSort(first); 
second = mergesort(second); 

---

实际的问题是，你有两种方法具有类似名称（mergesort和mergeSort），但非常不同的预期的行为：这些方法中的一个尝试进行排序其输入和返回排序结果不修改输入，而另一个不返回排序结果，因此必须修改其输入。

两种方法都存在优点。但是你现在的代码将这些方法混合在一起，这就出错了。

---

你目前的代码丢失的存储分类元素放回参数数组：

public static void mergesort(Comparable[] a) { 
    Comparable[] sorted = mergeSort(a); 
    System.arrayCopy(sorted, 0, a, 0, a.length); 
} 

和：如果你的辅助方法不能从类的外部被称为使他们private这样：

private static Comparable[] mergeSort(Comparable[] a) { 
    ... 
} 

private static Comparable[] merge(Comparable[] a, Comparable[] b) { 
    ... 
} 

甚至将辅助方法重命名为mergeSortHelper。

的最终目标始终是使你的代码尽可能地易读，并显示出你的意图你的代码的任何读者。