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

Question

我正在尝试对 size 的字符串列表实现合并排序算法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");

Answer 1

因为words您传递给的列表mergeWords永远不会被清除。mergeWords只会将新元素添加到此列表中，而不关心它已经包含的元素。只需做一个words.clear();在。。。之初mergeWords。.set(int index, E element)或者，您可以使用而不是覆盖现有元素.add()。但您需要确保列表的大小正确。一些不相关的评论：在函数调用中，您始终将列表的大小作为附加参数传递（n,&nbsp;left,&nbsp;right）。这是多余的（您可以使用 获取尺寸list.size()）。任何多余的东西都很容易变得不一致（即，如果传递错误的大小会发生什么？）。所以最好删除这些参数。当您将元素添加到列表时，您可以使用重载add(int index, E element)。这完全没问题，但我认为使用重载add(E element)更容易处理，因为您不需要跟踪在哪里添加元素。重载只会将新元素附加到列表的末尾。