java这个特殊的合并排序程序是如何工作的?
我正在学习排序算法。我已经通过了以下链接给出的程序。为了简单起见,我附加了链接和程序本身
public class Mergesort {
private int[] numbers;
private int[] helper;
private int number;
public void sort(int[] values) {
this.numbers = values;
number = values.length;
this.helper = new int[number];
mergesort(0, number - 1);
}
private void mergesort(int low, int high) {
if (low < high) {
int middle = low + (high - low) / 2;
mergesort(low, middle);
mergesort(middle + 1, high);
merge(low, middle, high);
}
}
private void merge(int low, int middle, int high) {
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
while (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
}
}
我没有得到任何线索,在合并方法中,为什么最后一个while(I<;=middle)被包括在内。平均值while(j<;=高)也存在,但忽略了此条件。 我得到这个程序的链接是http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html
对不起,我解释得不好。希望有人能给我解释一下
# 1 楼答案
线索实际上在参考文章中:
考虑上半年的数字比下半年的数字都要大的情况。然后在第一个while
循环中,您将只增加j
,您将不会复制上半个循环中的任何数字。第二个while
周期复制上半个周期的剩余数字一个好问题是为什么你实际上不需要复制下半场剩下的数字。我将把它留给你。:)