我正在尝试对 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");
慕森卡
相关分类