对单词列表执行合并排序-原始单词追加回列表

Question

我正试图在大小为N的字符串列表上实现合并排序算法，我已经设法对其进行了排序，但由于某些原因，原始值被添加到排序列表的末尾。

我对实现排序算法很陌生(读作：非常新(，所以如果有人告诉我我遗漏了什么，我将不胜感激。

public static void mergeSortWords(int n, List<String> words) {
if (n < 2) {
return;
}
int mid = n / 2; // Getting the mid-point of the array
List<String> l = new ArrayList<String>(mid); // Left side of array
List<String> r = new ArrayList<String>(n-mid); // Right side of array
for (int i = 0; i < mid; i++) {
l.add(i, words.get(i));
}
for (int j = mid; j < n; j++) {
r.add(j - mid, words.get(j));
}

mergeSortWords(mid, l); // recursively sort the left side
mergeSortWords(n-mid, r); // recursively sort the right side
mergeWords(n, words, l, r, mid, n-mid); // merge the sorted arrays back together
}
public static void mergeWords(int n, List<String> words, List<String> l, List<String> r, int left, int right) {
if (words.size() > n) {
return;
}
int i = 0, j = 0, k = 0;
while (i < left && j < right) {
if (l.get(i).compareToIgnoreCase(r.get(j)) < 0) { // comparing the strings alphabetically
words.add(k++, l.get(i++));
}
else {
words.add(k++, r.get(j++));
}
}
while (i < left) {
words.add(k++, l.get(i++));
}
while (j < right) {
words.add(k++, r.get(j++));
}
}

我的单元测试是这样的：

@Test
public void mergeSortWordsTest() {
List<String> actual = new ArrayList<String>();
List<String> expected = new ArrayList<String>();
actual.add("hello");
actual.add("yo");
actual.add("hi");
actual.add("what");
actual.add("bottle");
expected.add("bottle");
expected.add("hello");
expected.add("hi");
expected.add("what");
expected.add("yo");
mergeSortWords(actual.size(), actual);
Assert.assertEquals(expected, actual);

我收到：

java.lang.AssertionError: 
Expected :[bottle, hello, hi, what, yo]
Actual   :[bottle, hello, hi, what, yo, hello, yo, hi, what, bottle]

谢谢你的指点！

Answer 1

因为传递给mergeWords的words列表从未被清除。mergeWords将只向该列表添加新元素，而不关心它已经包含的元素。只需进行

words.clear();

在CCD_ 5的开始。

或者，可以使用.set(int index, E element)而不是.add()覆盖现有图元。但是你需要确保这个列表的大小是正确的。

一些无关的评论：

在函数调用中，您总是将列表的大小作为附加参数(n、left、right(传递。这是多余的(您可以使用list.size()获得大小(。任何多余的东西都很容易变得不一致(即，如果你传错了尺寸会发生什么？(。因此，最好删除这些参数。

将元素添加到列表中时，将使用重载add(int index, E element)。这很好，但我认为使用重载add(E element)要容易得多，因为您不需要跟踪在哪里添加元素。重载只会将新元素追加到列表的末尾。