归并排序通用方法
发布于2024-12-11 17:23 阅读(202) 评论(0) 点赞(22) 收藏(4)
我的合并排序似乎无法正常工作。当我显示排序列表时，它没有排序，并且添加了元素，本来应该有 9 个，结果却是 49 个。有人知道我哪里出错了吗？
public static <E extends Comparable<E>> void mergeSort(List<E> A) {
int n = A.size();
if (n > 1) {
int half = n / 2;
List<E> B = copyPartialArray(A, 0, half);
List<E> C = copyPartialArray(A, half, n);
mergeSort(B);
mergeSort(C);
merge(B, C, A);
}
}
public static <E extends Comparable<E>> void merge(List<E> B, List<E> C, List<E> A) {
int n1 = B.size();
int n2 = C.size();
int i = 0;
int j = 0;
int k = 0;
while (i < n1 && j < n2) {
if (B.get(i).compareTo(C.get(j)) < 0) {
A.add(k, B.get(i));
i++;
}
else {
A.add(k, C.get(j));
j++;
}
k++;
}
if (i == n1)
for (int p = j; p < n2; p++) {
A.add(k, C.get(p)); k++;
}
else if (j == n2)
for (int p = i; p < n1; p++) {
A.add(k, B.get(p)); k++;
}
}
private static <E extends Comparable<E>> List<E> copyPartialArray(List<E> A, int first, int last) {
int n = last - first;
List<E> copy = new ArrayList<E>(n);
for (int i = 0; i < n; i++)
copy.add(i, A.get(first + i));
return copy;
}
解决方案
这个答案将尝试让您认识到问题所在。
很明显，mergeSort 不会对一个元素数组做任何事情，但如果有两个元素数组（例如 [2,1]）会发生什么？您提到结果列表（列表 A）中的元素比以前更多。为什么？merge 对该列表做了什么？提示。
所属网站分类: 技术文章 > 问答
作者：黑洞官方问答小能手
链接：http://www.javaheidong.com/blog/article/694584/f229d4ece072086d4a30/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力