如何实现绑定了inclusive到exclusive的MergeSort？
如何实现绑定了inclusive到exclusive的MergeSort？
提问于 2020-04-16 08:18:21
我正在尝试用Java语言实现MergeSort算法，这样它就可以对A[start..end]中的数组进行排序。我真的很难实现它，这样它就不会包括在合并中传入的最后一个索引。我正在尝试跟踪我的代码，但一直感到困惑。
下面是我的代码：
public class MergeSort {
public static void main(String[] args) {
int[] list = new int[] { 3, 7, 5, 2, 9 };
int[] result = mergeSort(list, 0, list.length);
System.out.print("[");
for (int i = 0; i < result.length; i++) {
System.out.print(" " + result[i]);
}
System.out.println("]");
}
public static int[] mergeSort(int[] list, int start, int end) {
if (end - start < 2) {
return list;
} else {
int mid = (start + end) / 2;
mergeSort(list, start, mid);
mergeSort(list, mid + 1, end);
merge(list, start, mid, end);
return list;
}
}
public static void merge(int[] list, int start, int mid, int end) {
int[] copy = new int[list.length];
for (int i = 0; i < list.length; i++) {
copy[i] = list[i];
}
int i = start;
int k = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (copy[i] <= copy[j]) {
list[k] = copy[i];
i++;
} else {
list[k] = copy[j];
j++;
}
k++;
}
while (i <= mid) {
list[k] = copy[i];
i++;
k++;
}
while (j < end) {
list[k] = copy[j];
j++;
k++;
}
}
}回答 2
Stack Overflow用户
发布于 2020-04-16 08:29:03
或者调用mergeSort(list, 0, list.length - 1);
或者调用帮助器函数，比如F。例如，您可以调用F(list, 0, list.length);，而F唯一要做的事情就是调用mergeSort(list, 0, list.length - 1);。
这样你就不会再碰mergeSort了。你只要给F打个电话。
编辑：
public class MergeSort {
public static void main(String[] args) {
int[] list = new int[] {3, 7, 5, 2, 9};
int[] result = mergeSort(list, 0, list.length);
System.out.print("[");
for (int i = 0; i < result.length; i++) {
System.out.print(" " + result[i]);
}
System.out.println("]");
}
public static int[] mergeSort(int[] list, int start, int end) {
return F(list, start, end - 1);
}
public static int[] F(int[] list, int start, int end) {
if (end - start < 2) {
return list;
} else {
int mid = (start + end) / 2;
F(list, start, mid);
F(list, mid + 1, end);
merge(list, start, mid, end);
return list;
}
}
public static void merge(int[] list, int start, int mid, int end) {
int[] copy = new int[list.length];
for (int i = 0; i < list.length; i++) {
copy[i] = list[i];
}
int i = start;
int k = start;
int j = mid + 1;
while (i <= mid && j <= end) {
if (copy[i] <= copy[j]) {
list[k] = copy[i];
i++;
} else {
list[k] = copy[j];
j++;
}
k++;
}
while (i <= mid) {
list[k] = copy[i];
i++;
k++;
}
while (j < end) {
list[k] = copy[j];
j++;
k++;
}
}
}Stack Overflow用户
发布于 2020-04-16 13:18:12
使用定义了包含start和排除end的片调用mergesort确实是一种明智的方法，因为调用序列更简单：merge(array, 0, array.length)，并且它允许空片，这对于空数组是必要的。
您的mergesort方法有一个错误:正确的片段从mid开始，在end之前结束，因此调用应该是mergeSort(list, mid, end);
merge方法也有问题：
- 您不应该复制整个
list，而应该只复制从start到end的切片(不包括在内)。如果合并到临时数组中，并在合并后将其复制回来，则会更简单。使用此方法时，您可以在左侧部分耗尽时停止合并，因为右侧部分的剩余值已位于适当位置。 - 在将运行索引值与此方法排除的上界进行比较时，应使用
<运算符，而不是<=。
以下是更正后的版本：
public class MergeSort {
public static void main(String[] args) {
int[] list = new int[] { 3, 7, 5, 2, 9 };
int[] result = mergeSort(list, 0, list.length);
System.out.print("[");
for (int i = 0; i < result.length; i++) {
System.out.print(" " + result[i]);
}
System.out.println(" ]");
}
public static int[] mergeSort(int[] list, int start, int end) {
if (end - start < 2) {
return list;
} else {
// compute the mid point:
// the left part spans from start included to mid excluded
// the right part spans from mid included to end excluded
// avoid adding start and end to prevent overflow overflow for very large arrays
int mid = start + (end - start) / 2;
mergeSort(list, start, mid);
mergeSort(list, mid, end);
merge(list, start, mid, end);
return list;
}
}
public static void merge(int[] list, int start, int mid, int end) {
int[] temp = new int[end - start];
int k = 0; // index into the temporary array
int i = start; // index into the left part, stop at mid
int j = mid; // index into the right part, stop at end
// select from left or right slices and store into the temp array
while (i < mid && j < end) {
if (list[i] <= list[j]) {
temp[k++] = list[i++];
} else {
temp[k++] = list[j++];
}
}
// copy the remaining elements from the left part
while (i < mid) {
temp[k++] = list[i++];
}
// copy the sorted elements back to the original list
for (i = 0; i < k; i++) {
list[start + i] = temp[i];
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61240698
复制相关文章
相似问题
腾讯云开发者
