在单词列表上实现合并排序-原始单词附加回列表？

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++));
        }
    }

I单元测试如下：

    @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.clear();

在合并文字的开头。

或者，您可以使用. set（int index， E元素）而不是. add（）覆盖现有元素。但是您需要确保列表的大小正确。

一些不相关的评论：

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

将元素添加到列表时，使用重载add（int index，E element）。这很好，但我认为使用重载添加（E元素）要容易得多，因为您不需要跟踪添加元素的位置。重载只会将新元素附加到列表的末尾。