我在用Java实现合并排序算法时遇到了问题:我已经完成了合并排序算法,但是无法产生正确的结果。我还从该函数返回排序列表。我也该怎么办?
这是我在下面定义的合并排序算法。
mergeSort方法:
public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr) {
ArrayList<Person> helper = new ArrayList<Person>();
mergeSort(personList, helper, 0, personList.size() - 1, compTr);
}
mergeSort函数:
private static void mergeSort(ArrayList<Person> list,
ArrayList<Person> helper,
int low,
int high,
Comparator<Person> compTr) {
if (low < high) {
int middle = (low + high) / 2;
mergeSort(list, helper, low, middle, compTr); //sort left half
mergeSort(list, helper, middle + 1, high, compTr); //sort right half
merge(list, helper, low, middle, high, compTr); // merge
}
}
合并算法:
private static void merge(ArrayList<Person> list,
ArrayList<Person> helper,
int low,
int middle,
int high,
Comparator<Person> compTr) {
//This loop throws Exception
for (int i = low; i < high + 1; i++) {
helper.add(i, list.get(i));
}
int helperLeft = low;
int helperRight = middle + 1;
int current = low;
while (helperLeft < middle && helperRight < high) {
if (isGreaterThan(helper.get(helperLeft), helper.get(helperRight), compTr)) {
list.set(current, helper.get(helperLeft));
helperLeft++;
} else {
list.set(current, helper.get(helperRight));
helperRight++;
}
current++;
}
//Copy remaining elements
int remaining = middle - helperLeft;
for (int j = 0; j <= remaining; j++) {
list.set(current + j, helper.get(helperLeft + j));
}
// RETURN LIST(list) _-> TO DO
}
实施比较器功能
public static boolean isGreaterThan(Person helperLeft, Person helperRight, Comparator<Person> compTr) {
return greaterThan(compTr, helperLeft, helperRight);
}
private static boolean greaterThan(Comparator comp, Person x, Person y) {
return comp.compare(x, y) > 0;
}
我该怎么做?
我无法从合并功能获得返回值作为列表
如果我对您的理解正确,您正在寻找一种返回排序列表的方法。但是在您的实现中,您正在尝试对原始列表进行排序。这意味着您在调用合并功能时已经有一个指向结果排序列表的变量:在调用
时用作参数的变量public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr)
例如,如果您的人员在一个名为“列表”的ArrayList中,则您正在对该“列表”进行排序。
ArrayList<Person> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(new Person());
}
System.out.println(list);
mergeSort(list, Comparator.<Person>naturalOrder());
System.out.println(list);
有关更多信息,您所使用的称为inout参数-如在函数中输入您的内容并通过该参数接收其输出。
正如评论中指出的那样,代码还存在其他问题。我怀疑这里是一个错误(<=代替
(helperRight <= high)
另一个是您在就地合并排序中使用了临时列表。
这里有一个工作示例:How to sort in-place using the merge sort algorithm?
无需返回排序后的数组:该数组已就位排序。
但是请注意这些问题:
辅助数组的初始大小应等于要排序的数组的大小。这避免了helper.add(i, list.get(i));
的问题,该问题一直将元素插入到辅助数组中。
您将使用以下方法分配辅助数组
ArrayList<Person> helper = new ArrayList<Person>(personList.size());
您将使用helper.set(i, list.get(i))
保存数组元素。
for
中的merge
循环应迭代到并包括上限:
while (helperLeft <= middle && helperRight <= high)
包含上限的约定很容易混淆并且容易出错,排除上限更容易,因为它消除了对-1
/ +1
调整的需要。
这里是修改后的版本:
public static void mergeSort(ArrayList<Person> personList, Comparator<Person> compTr) {
ArrayList<Person> helper = new ArrayList<Person>(personList.size());
mergeSort(personList, helper, 0, personList.size(), compTr);
}
private static void mergeSort(ArrayList<Person> list,
ArrayList<Person> helper,
int low,
int high,
Comparator<Person> compTr) {
if (high - low >= 2) {
int middle = low + (high - low) / 2;
mergeSort(list, helper, low, middle, compTr); //sort left half
mergeSort(list, helper, middle, high, compTr); //sort right half
merge(list, helper, low, middle, high, compTr); // merge
}
}
private static void merge(ArrayList<Person> list,
ArrayList<Person> helper,
int low,
int middle,
int high,
Comparator<Person> compTr) {
for (int i = low; i < high; i++) {
helper.set(i, list.get(i));
}
int helperLeft = low;
int helperRight = middle;
int current = low;
while (helperLeft < middle && helperRight < high) {
if (isGreaterThan(helper.get(helperLeft), helper.get(helperRight), compTr)) {
list.set(current, helper.get(helperLeft));
helperLeft++;
} else {
list.set(current, helper.get(helperRight));
helperRight++;
}
current++;
}
// Copy remaining elements
while (helperLeft < middle) {
list.set(current, helper.get(helperLeft));
helperLeft++;
current++;
}
}
这是我的答案
我更改了密码
while(helperLeft < middle && helperRight < high) {
to
while(helperLeft <= middle && helperRight <= high) {