錯誤的合併排序

我正在合併排序程序，按標題按字母順序排序電影。但是，它並未將列表排序完成。我研究過合併排序，並查看了本網站和其他地方的各種其他示例，但無法找到我的錯誤。錯誤的合併排序

public static Movie4[] myMovies; 

/** 
* printMovies traverses an array of movies and prints each respective title 
*/ 
public static void printMovies(Movie4[] movies) 
{ 
    for (int i = 0; i < movies.length; i ++) 
    { 
     System.out.println(movies[i]); 
    } 
} 

/** 
* sortTitles sorts an array of movies alphabetically by title 
*/ 
public static void sortTitles(Movie4[] movies, int low, int high) 
{ 
    if (low == high) 
    { 
     return; 
    } 
    else 
    { 
     Movie4[] firstHalf = new Movie4[movies.length/2]; 
     Movie4[] secondHalf = new Movie4[movies.length - movies.length/2]; 
     int midpoint = (low + high)/2; 
     for (int i = 0; i < firstHalf.length; i ++) 
     { 
      firstHalf[i] = movies[i]; 
     } 
     for (int i = 0; i < secondHalf.length; i ++) 
     { 
      secondHalf[i] = movies[i + movies.length/2]; 
     } 
     sortTitles(firstHalf, low, midpoint); 
     sortTitles(secondHalf, midpoint + 1, high); 
     mergeTitles(movies, firstHalf, secondHalf); 
    } 
} 

/** 
* mergeTitles works in conjunction with sortTitles to merge sort an array of Movie4 objects 
*/ 
public static void mergeTitles(Movie4[] movies, Movie4[] first, Movie4[] second) 
{ 
    int i = 0; 
    int i2 = 0; 
    for (int index = 0; index < movies.length; index ++) 
    { 
     if (i2 >= second.length || (i < first.length && 
             first[i].getTitle().compareTo(second[i2].getTitle()) < 0)) 
     { 
      movies[index] = first[i]; 
      i ++; 
     } 
     else 
     { 
      movies[index] = second[i2]; 
      i2 ++; 
     } 
    } 
} 

public static void main(String[] args) 
{ 
    myMovies = new Movie4[10]; 
     myMovies[0] = new Movie4("The Muppets Take Manhattan", 2001, "Columbia Tristar"); 
     myMovies[1] = new Movie4("Mulan Special Edition", 2004, "Disney"); 
     myMovies[2] = new Movie4("Shrek 2", 2004, "Dreamworks"); 
     myMovies[3] = new Movie4("The Incredibles", 2004, "Pixar"); 
     myMovies[4] = new Movie4("Nanny McPhee", 2006, "Universal"); 
     myMovies[5] = new Movie4("The Curse of the Were-Rabbit", 2006, "Aardman"); 
     myMovies[6] = new Movie4("Ice Age", 2002, "20th Century Fox"); 
     myMovies[7] = new Movie4("Lilo and Stich", 2002, "Disney"); 
     myMovies[8] = new Movie4("Robots", 2005, "20th Century Fox"); 
     myMovies[9] = new Movie4("Monsters Inc.", 2001, "Pixar"); 

    System.out.println("Original List:"); 
    System.out.println(); 
    printMovies(myMovies); 
    System.out.println(); 
    System.out.println("List Sorted by title, ascending:"); 
    System.out.println(); 
    sortTitles(myMovies, 0, myMovies.length - 1); 
    printMovies(myMovies); 
}

請假定getTitle()方法在別處定義，只是返回每個對象的第一String，獲得標題。這是錯誤的輸出;

List Sorted by title, ascending: 

Ice Age, 2002, 20th Century Fox. 
Lilo and Stich, 2002, Disney. 
Mulan Special Edition, 2004, Disney. 
Robots, 2005, 20th Century Fox. 
Monsters Inc., 2001, Pixar. 
Shrek 2, 2004, Dreamworks. 
The Curse of the Were-Rabbit, 2006, Aardman. 
The Incredibles, 2004, Pixar. 
Nanny McPhee, 2006, Universal. 
The Muppets Take Manhattan, 2001, Columbia Tristar.

我認爲錯誤可能是與我的條件語句，因爲如果我的compareTo值設置爲> 0，則排序正確，只是在錯誤的順序。

來源

2017-06-02 Hunter Moore

我會建議學習使用調試器。 – lucasvw

你的代碼看起來像是自頂向下[merge sort]的實現（https://en.wikipedia.org/wiki/Merge_sort）。你有沒有考慮自下而上的方法？我感覺更直觀。我也會用'[Comparable]'來實現算法，並給'Movie4'一個適當的比較方法（單線）。 – 9000

你不應該分配新的數組或複製元素。應使用low和high來管理sortTitles()中的所有內容。同樣，你不應該傳遞三個數組到mergeTitles();取而代之的是，傳遞一個數組和值low,midpoint和high以讓它知道要合併的數組的哪些部分。

您當前的代碼似乎有一個柵欄柱問題：您使用(low + high)/2計算midpoint，但使用movies.length/2第一個數組的長度。由於low以0開始，high以myMovies.length - 1開頭，因此當myMovies.length爲偶數時，這些長度將有所不同。您可能有其他索引問題，但我沒有深入研究，因爲整個方法有缺陷，正如我在第一段中所述。

來源

2017-06-02 18:19:00

錯誤的合併排序

回答

相關問題