java - 合并排序 Java 实现,因此合并在一个数组内工作,第二个拆分数组反转
问题描述
挑战:在关于数据结构和算法的讲座中,我遇到了一个合并排序版本,它使用合并例程,其后半部分与拆分索引相反,并从那里比较第一个和最后一个元素。我试图在java中实现,但它总是以某种方式失败。
[1, 2, 4, 8, 6]
问题:正在对数组进行排序,因此输出6
未排序。似乎递归调用没有查看6
上次merge
调用中的元素。
我尝试了什么:移动不同的索引并添加不同的打印语句进行检查。我试图j = r
在最后一个for
循环之前进行,每次都会merge
导致堆栈溢出。我试图改变计算数组大小的方式,因为我不确定伪代码是否除了数组从 1 或 0 开始。我试图转移if(p < r-1)
到if(p <= r-1)
但得到一个堆栈溢出。
我查看了 java 合并例程的不同实现,到目前为止,我发现的每一个似乎都适用于两个数组。是否有严重的原因导致上述方法无法正常工作或知道如何解决此问题?
给定以下伪代码:
void merge_sort(array<T>& A, int p, int r) {
if (p < r - 1) {
int q = Floor((p + r) / 2);
merge_sort(A, p, q);
merge_sort(A, q + 1, r);
merge(A, p, q, r);
}
}
void merge(array<T>& A, int p, int q, int r) {
array<T> B(p, r - 1);
int i, j;
for (i = p; i < q; i++)
B[i] = A[i];
// Now i=q
for (j = r; i < r; i++)
B[--j] = A[i];
i = p;
j = r - 1;
for (int k = p; k < r; k++)
A[k] = (B[i] < B[j]) ? B[i++] : B[j--];
}
我试图像这样在java中实现:
import java.util.Arrays;
public class Mergesort {
private static int[] A = new int[]{ 4, 2, 1, 8, 6 };
public static void main(String[] args) {
merge_sort(0, A.length - 1);
System.out.println(Arrays.toString(A));
}
public static void merge_sort(int p, int r) {
if (p < r - 1) {
int q = Math.floor((p + r) / 2);
merge_sort(p, q);
merge_sort(q + 1, r);
merge(p, q, r);
}
}
public static void merge(int p, int q, int r) {
int[] B = new int[r - p];
int i, j;
for (i = p; i < q; i++)
B[i] = A[i]
for (j = r; i < r; i++)
B[--j] = A[i];
i = p;
j = r - 1;
for (int k = p; k < r; k++)
A[k] = (B[i] < B[j])? B[i++] : B[j--];
}
}
解决方案
您的代码中有多个问题:
- 临时数组太短:因为
r
是最后一个元素的索引,所以大小应该是r - p + 1
.r
将要排序的切片的最后一个元素作为索引传递要简单得多。 - 第一个循环不正确:您应该在and中
for
使用不同的索引。B
A
- 第二个
for
循环B[r - 1]
向下复制,但应该使用它B[r - p]
。 - 合并循环不正确:您应该在访问和/或之前测试是否
i
并且j
仍然在各自一半的边界内。B[i]
B[j]
int q = Math.floor((p + r) / 2);
[次要]在 java 中不需要asp
和r
are have typeint
,因此除法将使用整数算术。
这是修改后的版本:
public class Mergesort {
private static int[] A = new int[]{ 4, 2, 1, 8, 6 };
public static void main(String[] args) {
merge_sort(0, A.length);
System.out.println(Arrays.toString(A));
}
public static void merge_sort(int p, int r) {
if (r - p >= 2) {
int q = p + (r - p) / 2;
merge_sort(p, q);
merge_sort(q, r);
merge(p, q, r);
}
}
public static void merge(int p, int q, int r) {
int m = q - p; // zero based index of the right half
int n = r - p; // length of the merged slice
int[] B = new int[n];
int i, j, k;
for (i = p, j = 0; j < m; j++)
B[j] = A[i++];
for (i = r, j = m; j < n; j++)
B[j] = A[--i];
for (i = 0, j = n, k = p; k < r; k++) {
// for stable sorting, i and j must be tested against their boundary
// A[k] = (i < m && (j <= m || B[i] <= B[j - 1])) ? B[i++] : B[--j];
// stability is not an issue for an array of int
A[k] = (B[i] <= B[j - 1]) ? B[i++] : B[--j];
}
}
}
反转后半部分允许更简单的合并循环而无需边界测试。但是请注意,有一种更简单的方法可以使用更少的内存并且可能更有效:
public static void merge(int p, int q, int r) {
int m = q - p; // length of the left half
int[] B = new int[m];
int i, j, k;
// only save the left half
for (i = p, j = 0; j < m; j++)
B[j] = A[i++];
for (i = 0, j = q, k = p; i < m; k++) {
A[k] = (j >= r || B[i] <= A[j]) ? B[i++] : A[j++];
}
}
推荐阅读
- deployment - NixOS 中的 NixOS?
- javascript - ajax 动态文件查看器
- python - 在 AWS lambda_function.py 中添加内联类是否需要遵循某种模式?
- python-3.x - 基于具有不同行的列合并数据框
- python - Python pandas 两列索引和区域。该地区有州,然后是城镇。我需要一个显示相应状态的新列
- javascript - GWT 异步回调
- variables - 检查变量中是否有子字符串-同一行中的命令(cmd / c)
- java - JDBC/Postgres 如何将无时区的 java.util.Date 与时间戳进行比较?
- python - AWS lambda CLI 'update-function-code' 不更新 lambda_handler 文件
- caching - Sendmail - 询问收件人总是 5 秒