合併排序（看似隨機重複）

所以，我有一個合併分揀機的代碼有一個小bug，其中從數組列表中的一些項目將被複制並扔進一個奇怪的位置合併排序（看似隨機重複）

Sorted List Unsorted List 
apricot  gray 
aqua   maize 
bittersweet mahogany 
blue   green 
brick   red 
cornflower  apricot 
flesh   bittersweet 
gray   flesh 
green   cornflower 
lemon   orchid 
magenta  pink 
maize   orange 
mahogany  maroon 
bittersweet blue 
melon   yellow 
orange   melon 
orange   magenta 
maroon   violet 
blue   silver 
pearl   tan 
periwinkle  periwinkle 
purple   turquoise 
purple   thistle 
olive   white 
purple   sienna 
tan   lemon 
turquoise  pearl 
brick   aqua 
olive   brick 
purple   olive 
purple   purple

這裏是我寫的代碼，我很欣賞的任何及所有反饋：

ArrayList<String> a = new ArrayList<String>(); 

public MergeSorter(ArrayList<String> aList) 
{ 
    a = aList; 
} 

public void sort() 
{ 
    if (a.size() <= 1) return; 
    ArrayList<String> first = new ArrayList<String>(); 
    ArrayList<String> second = new ArrayList<String>(); 
    for (int i = 0; i < a.size()/2; i++) 
     first.add(a.get(i)); 
    for (int i = a.size()/2; i < a.size(); i++) 
     second.add(a.get(i)); 
    MergeSorter firstSorter = new MergeSorter(first); 
    MergeSorter secondSorter = new MergeSorter(second); 
    firstSorter.sort(); 
    secondSorter.sort(); 
    merge(first, second); 
} 

private void merge(ArrayList<String> first, ArrayList<String> second) 
{ 
    int iFirst = 0; 
    int iSecond = 0; 
    int j = 0; 

    while(iFirst < first.size() && iSecond < second.size()) 
    { 
     if(first.get(iFirst).compareTo(second.get(iSecond)) < 0) 
     { 
      a.set(j, first.get(iFirst)); 
      iFirst++; 
     } 
     else 
     { 
      a.set(j, second.get(iSecond)); 
      iSecond++; 
     } 
     j++; 
    } 
    //System.arraycopy(first, iFirst, a, j, first.size() - iFirst); 
    for (int i = iFirst; i < first.size() - iFirst; i++) 
    { 
     a.set(j, first.get(i)); 
     j++; 
    } 

    //System.arraycopy(second, iSecond, a, j, second.size() - iSecond); 
    for (int i = iSecond; i < second.size() - iSecond; i++) 
    { 
     a.set(j, second.get(i)); 
     j++; 
    } 

} 

}

來源

2015-04-16 Bailey Tincher

看看你的合併功能。 while循環後發生了什麼，當'second'數組仍然有元素需要複製？最後的for循環能夠到達數組的最後一個元素嗎？ –

@ChrisDodd Yep剛剛注意到我忘記了增加它。但是，我正在使用的測試數據集並沒有經過第二個循環，因爲第二個循環已經複製了它的所有值。這個問題特別在於合併類的第一個循環（至少似乎）。 –

你不是遍歷遠遠不夠：

for (int i = iFirst; i < first.size() - iFirst; i++) 
{ 
    a.set(j, first.get(i)); 
    j++; 
} 
for (int i = iSecond; i < second.size() - iSecond; i++) 
{ 
    a.set(j, second.get(i)); 
    j++; 
}

此時，其中一個列表已被完全消耗，您只需將其他列表的所有其餘元素複製到結果列表中。這意味着從「結束開始」（iFirst）到列表末尾（first.size()）迭代。

出於某種原因，您減去了iFirst，因此並非所有值都被複制。相反，未排序的值（分揀機初始化的值）保留在列表的末尾，其中一些值將從結果列表中實際排序的部分重複。

這應該工作：

for (int i = iFirst; i < first.size(); i++) 
{ 
    a.set(j, first.get(i)); 
    j++; 
} 
for (int i = iSecond; i < second.size(); i++) 
{ 
    a.set(j, second.get(i)); 
    j++; 
}

來源

2015-04-16 02:45:15 dddsnn

合併排序（看似隨機重複）

回答

相關問題