要求按顺序输出数组A。但是不知道哪里错了,结果总是不正确,谁能帮忙修改一下啊?谢谢了
public class MergeTwolists {
public static void main(String[] args) {
int[] A = {2, 3, 8, 9, 66, 7, 11, 13, 46, 56};
int p = 0, q = 4, r = 9;
merge(A, p, q, r);
}
public static void merge(int[] A, int p, int q, int r) {
int s = p;
int t = q + 1;
int k = p;
int[] B = new int[10];
while(s <= q && t <= r) {
if(A[s] < A[t]) {
int n = s;
s = binarySearch(A, s, q, A[t]);
for(int j = 0; j < s - n; j++) {
B[k+j] = A[n+j];
k = k + j;
}
} else if(A[s] > A[t]) {
int n = t;
t = binarySearch(A, t, r, A[s]);
for(int j = 0; j < t - n; j++) {
B[k+j] = A[n+j];
k = k + j;
}
} else {
B[k] = A[s];
k = k + 1;
s = s + 1;
}
}
if(s == q + 1) {
int n = t;
for(int j = 0; j <= r - n; j++)
B[k+j] = A[n+j];
} else {
int n = s;
for(int j = 0; j <= q - n; j++)
B[k+j] = A[n+j];
}
for(int i = 0; i < 10; i++)
System.out.print(B[i] + " ");
}
public static int binarySearch(int[] A, int left, int right, int x) {
int i = -1;
while(left <= right && i == -1) {
int middle = (left + right) / 2;
if(x == A[middle])
i = middle;
else if(x > A[middle])
left = middle + 1;
else
right = middle - 1;
}
if(i == -1)
i = left;
return i;
}
}
这个问题的出处:http://www.cqvip.com/onlineread/onlineread.asp?ID=28562837
这个程序解决的问题是:二分搜索法在合并两个已排序表中的应用。
假定有一个数组A[1:m],p,q,r为它的索引,并有1<=p<=q<r<=m,两个子数组A[p:q]和A[q+1:r]各自按升序排列,我们要重新安排A中元素的位置,使得子数组A[p:r]也按升序排列。合并这两个子数组的算法通常是MERGE,使用两个指针s和t,初始化时各自指向A[p]和A[q+1],再用一个空数组B[p:r]做暂存器,每次比较元素A[s]和A[t],将小的元素添加到辅助数组B,如果相同就把A[s]添加进去;然后更新指针,如果A[s]<=A[t],则s加1,否则t加1,当条件s=q+1或t=r+1成立时过程结束。在第一种情况下,我们把数组A[t:r]中剩余的元素添加到B,而在另一种情况下,我们把数组A[s:r]中剩余的元素添加到B。最后再显示已经排好序的数组B。