需要幫助查找在arraylist合併排序錯誤

我想實現一個合併排序算法的字符串arraylists，但我似乎無法找到錯誤是搞砸了arraylist的順序。需要幫助查找在arraylist合併排序錯誤

private static void sort(java.util.ArrayList<String> a) 
{ 

    // End recursion 
    if (a.size() < 2) 
    { 
     return; 
    } 


    int mid = a.size()/2; 


    java.util.ArrayList<String> left = new java.util.ArrayList<String>(); 


    int i; 

    for (i = 0; i < mid; i++) 
    { 

     left.add(a.remove(i)); 

    } 


    java.util.ArrayList<String> right = new java.util.ArrayList<String>(); 

    // Copy the second half to the "right" 
    for (; i < a.size(); i++) 
    { 
     right.add(a.remove(i)); 
    } 


    sort(left); 
    sort(right); 

    merge(a, left, right); 
} 

private static void merge(java.util.ArrayList<String> result, java.util.ArrayList<String> left,java.util.ArrayList<String> right) 
{ 
    int i, l, r; 

    i = l = r = 0; 


    while (l < left.size() && r < right.size()) 
    { 
     if ((left.get(l)).compareTo(right.get(r)) < 0) 
     { 
     result.add(left.get(l)); 
     l++; 
     } 
     else 
     { 
     result.add(right.get(r)); 
     r++; 
     } 

     i++; 
    } 


    while (l < left.size()) 
    { 
     result.add(left.get(l)); 
     l++; 
     i++; 
    } 

    // Append rest of the values in the right half, if any... 
    while (r < right.size()) 
    { 
     result.add(right.get(r)); 
     r++; 
     i++; 
    } 
}

來源

2012-05-06 Bob the builder

它看起來像功課，你不告訴我們你已經嘗試過什麼，或者是什麼問題...... – tonio

其實我告訴過你如果你閱讀我的陳述是什麼問題。我說：「似乎無法找到搞亂數組列表的順序的錯誤。」換句話說，數組列表沒有被正確排序。它是一個字符串數組列表，顯然這些字符串不是按字母順序排列的。我敢打賭，你說它看起來像每個新海報的功課。無論如何，你想讓我告訴你我所嘗試的是什麼？它非常無用，告訴我試過了什麼，因爲它是一個相對較新的程序員，因爲它有很多錯誤。 –

因爲要對字符串數組進行排序，可以使用Collections.sort，或者只需將字符串放在TreeSet中（如果明智地刪除重複項），除非賦值要實現合併排序或者有充分的理由將您的自己分類。你沒有提到。 – tonio

該問題出現在sort函數中。

當您使用a.remove(i)會發生什麼？索引i上的元素將從數組中移除，因此以前位於索引i+1處的元素現在位於索引i處，並且數組大小遞減。如果您接着執行i++，並且再次執行a.remove(i)，則將跳過數組中的一個元素。

在你的sort函數中，當調用merge時，你應該檢查那個a.size() == 0。你會發現情況並非總是如此。 merge函數看起來不錯，但是你的數組分裂是不正確的：你忘記了使用remove(int i)改變了數組;其大小和元素的索引。

來源

2012-05-06 08:34:17 tonio

需要幫助查找在arraylist合併排序錯誤

回答

相關問題