我需要使用额外的数组进行归并排序。这是我的代码:
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 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右子数组的索引，然后从 left 中选择正确的元素或 right放入 buff .
元素的有效范围是(包含边界):
-
left = low...mid对于左子数组 -
right = mid+1...high对于右子数组
要评估选择哪个元素，请考虑 left 出现的条件。元素被选中。它发生在:
- 没有更多的元素可以从右边的子数组中选择(即
right > high) - OR(有条件地)仍有一个元素要从左侧子数组中选择(即
left <= mid)并且(有条件地)该元素小于或等于来自右子数组的元素(即arr[left] <= arr[right])。
重要的是使用短路条件与 && ( JLS 15.23 ) 和条件或 || ( JLS 15.24 ) 运算符，并相应地对这些条件进行排序。否则你会得到一个 ArrayIndexOutOfBoundsException .
相关问题
- What’s the difference between | and || in Java?
- Shortcut “or-assignment” (|=) operator in Java Java
- Why doesn’t Java have compound assignment versions of the conditional-and and conditional-or operators? (&&=, ||=)
求两个数的平均值
通常会看到以下内容:
int mid = (low + high) / 2; // BROKEN! Can result in negative!
问题是现在，数组/列表等很容易超过 230 个元素，而以上会导致溢出并导致负数。
Josh Bloch 提倡的新习语如下:
int mid = (low + high) >>> 1; // WORKS PERFECTLY!
这使用无符号右移运算符 ( JLS 15.19 )；它根据我们的需要正确处理加法的任何溢出。
引用资料
相关问题
- Bitwise Operations — Arithmetic Operations
- 解释位移与二次幂运算的关系
- Java’s >> versus >>> Operator?
- Difference between >>> and >> operators
- Difference between >>> and >>
关于数组声明
不要养成这样声明数组的习惯:
int x[];
您应该将括号放在类型，而不是标识符:
int[] x;
相关问题
关于java - 额外存储归并排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2861150/