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。

的最終目標始終是使你的代碼儘可能地易讀，並顯示出你的意圖你的代碼的任何讀者。