额外的存储合并排序
我需要使用附加数组进行合并排序。 这是我的代码：
public class extra_storage{
public static void main(String[]args) {
int x[]=new int[]{12,9,4,99,120,1,3,10};
int a[]=new int[x.length];
mergesort(x,0,x.length-1,a);
for (int i=0;i<x.length;i++){
System.out.println(x[i]);
}
}
public static void mergesort(int x[],int low,int high, int a[]){
if (low>=high) {
return;
}
int middle=(low+high)/2;
mergesort(x,low,middle,a);
mergesort(x,middle+1,high,a);
int k;
int lo=low;
int h=high;
for (k=low;k<high;k++)
if ((lo<=middle ) && ((h>high)||(x[lo]<x[h]))){
a[k]=x[lo++];
}
else {
a[k]=x[h++];
}
for (k=low;k<=high;k++){
x[k]=a[k];
}
}
}
但有些错误。 当我运行它时，输出是这样的：
1 0 3 0 4 0 9 0
问题是什么？
您似乎有堆栈溢出。
在你的代码中
public static void mergesort(int x[],int low,int high, int a[]){
if (low>high) {
return;
}
int middle=(low+high)/2;
mergesort(x,low,middle,a);
mergesort(x,middle+1,high,a);
如果低开始低于或等于高，那么它将最终等于高，在这种情况下，middle == low == high，并且它将自称为永久。
提交答案后，问题被改为删除堆栈溢出。
以下是您的原始算法，其中包含一些更正和文体改进：
public class MergeSort {
public static void main(String[]args) {
int[] nums = {12,9,4,99,120,1,3,10};
mergeSort(nums);
System.out.println(java.util.Arrays.toString(nums));
// "[1, 3, 4, 9, 10, 12, 99, 120]"
}
static void mergeSort(int[] arr) {
mergeSort(arr, 0, arr.length - 1, new int[arr.length]);
}
static void mergeSort(int[] arr, int low, int high, int[] buff){
if (low >= high) {
return;
}
int mid = (low + high) >>> 1;
mergeSort(arr, low, mid, buff);
mergeSort(arr, mid+1, high, buff);
for (int left = low, right = mid + 1, i = low; i <= high; i++) {
if (right > high || left <= mid && arr[left] <= arr[right]) {
buff[i] = arr[left++];
} else {
buff[i] = arr[right++];
}
}
for (int i = low; i <= high; i++) {
arr[i] = buff[i];
}
}
}
与Eyal的实现不同， src和dst的作用是通过递归级别来回交换的，在这里我们总是对同一个数组对象arr排序，而数组对象buff总是只用作合并的临时缓冲区（和因此，合并阶段之后有一个复制阶段）。 这仍然是O(N log N) ，但Eyal更先进的实施将是一个不变的因素改进。
在合并循环上
基本上，左侧子阵列的left索引和right子阵列的right索引，然后从left或right选取右侧的元素以放入buff 。
元素的有效范围是（包含边界）：
left = low...mid左侧子阵列的left = low...mid right = mid+1...high对于右子阵列为right = mid+1...high 要评估选取哪个元素，请考虑拾取left元素的条件。 它发生在：
right > high ） left <= mid ）和（有条件）该元素小于或等于右子数组中的元素（即arr[left] <= arr[right] ）。 使用短路条件和&& （JLS 15.23）和条件 - 或|| （JLS 15.24）运营商，并相应地订购这些条件。 否则，你会得到一个ArrayIndexOutOfBoundsException 。
相关问题
在两个数字之间找到平均值
通常看到以下内容：
int mid = (low + high) / 2; // BROKEN! Can result in negative!
问题是，现在的数组/列表等可以轻松超过230个元素，而上述将导致溢出并导致负数。
正如Josh Bloch所倡导的那样，新的成语如下：
int mid = (low + high) >>> 1; // WORKS PERFECTLY!
这使用无符号右移运算符（JLS 15.19）; 它会根据我们的需要正确处理任何溢出。
参考
相关问题
在数组声明上
不要养成像这样声明数组的习惯：
int x[];
您应该将括号替换为类型，而不要使用标识符：
int[] x;
相关问题
Object[] x和Object x[]之间是否有区别？ int[] myArray和int myArray[]之间的区别 int[] k,i和int k[],i i不同类型！ 你的代码不够清晰，并且它有许多不相关的操作。 此外，它没有表现出你描述的行为。
您试图实现的mergesort版本的想法是使用与输入数组（目标数组）相同大小的单个辅助数组（源数组）。 这允许从一个阵列合并到另一个阵列，因为没有有效的就地合并技术。 该算法包括将目标数组的两半分类到源数组中的相应范围，然后将两半合并回目标数组。 请注意，这要求在每次调用时，两个数组在低和高指定的范围内是相同的。
以下是int数组的一个实现。 您可以添加优化，比如对小输入进行插入排序，或者添加一半而不是在可能的情况下合并它们。 这种优化可以在Arrays.sort（Object []）的实现中找到。
public static void mergeSort(int[] arr){
int[] aux = arr.clone();
mergeSort(aux, 0, arr.length, arr);
}
private static void mergeSort(int[] src, int low, int high, int[] dst) {
// One or no items - nothing to sort
if (high-low<=1)
return;
// Recursively sorting into src
int mid = (low + high) / 2;
mergeSort(dst, low, mid, src);
mergeSort(dst, mid, high, src);
// Merge halves into dst
for(int i = low, p = low, q = mid; i < high; i++) {
if (q >= high || p < mid && src[p] <= src[q])
dst[i] = src[p++];
else
dst[i] = src[q++];
}
}