我有2个排序数组，分别为a1和a2，分别为l1和l2。数组a2在长度l1的末尾具有空白，因此除其自身的元素外，它还可以容纳a1的所有元素。现在，我想将a1合并到a2中，以便a2将按排序顺序包含a1和a2的所有元素。理想情况下，应使用O（1）辅助存储空间。我有以下鳕鱼，但是出了点问题：
public static int[] merge(int []a1,int a2[],int l1, int l2){
System.out.println("l1 =" +l1 + " l2=" +l2);
int es = l2-l1;
int fs = l2-es;
System.out.println("es= " +es);
System.out.println("fs = " + fs);
int j=0;
for(int i=0;i< l1;i++){
if(j<fs){
// System.out.println("i= " + i + "a1[i]=" + a1[i]);
// System.out.println("j= " + j + "a2[j]=" + a2[j]);
if(a1[i]<a2[j]){
add(a2,j,a1[i],l2);
//i++;
fs++;
}
}else{
System.out.println("***");
a2[j]=a1[i];
}
j++;
}
return a2;
}
public static void add(int []a,int p,int key,int l){
for(int i=l-1;i>p;i--){
a[i]= a[i-1];
}
a[p]= key;
}
有人对如何解决此问题有任何想法吗？我使用以下数据来运行代码：
int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;
输出是
l1 =4 l2=7
es= 3
fs = 4
-1
0
1
3
9
0
0
很难说出您的代码是做什么的，但是它似乎具有次佳（O(n^2)）的复杂性：add方法中有第二个循环。另外，请注意fs始终等于l1。
但是还有一种更简单的方法：从背面开始。如果您考虑一下，总是有足够的空间。
这样的东西
int i = l1 - 1;
int j = l2 - 1;
int result_pos = l1 + l2 - 1;
while (i >= 0 || j >= 0) {
if (a1[i] >= a2[j]) {
a2[result_pos--] = a1[i--];
} else {
a2[result_pos--] = a2[j--];
}
}
PS对于循环中i和j之一为负的情况，您需要添加处理。显然，在这种情况下，应该复制另一个元素。
编辑以后可以在这种情况下完成
if (j < 0 || (i >= 0 && a1[i] >= a2[j])) {
而不是
if (a1[i] >= a2[j]) {
如果a1和a2中的元素已排序，则您将具有以下内容：
a1 : [-1] [0] [7] [8]
a2 : [1] [3] [9] [] [] [] []
因此，在代码中，您可以这样做：
int a1i = 0; // pointer to the ith element in the array a1
int tmp = 0;
int i = 0;
for(i = 0; i < a1.length; i++) {
if(a2[i] > a1[a1i]) {
tmp = a2[i];
a2[i] = a1[a1i];
a1[a1i] = tmp;
Arrays.sort(a1); // This might take more memory though...
} else {
a1i++;
}
}
a1i = 0;
for(i; i < a2.length; i++) {
a2[i] = a1[a1i];
a1i++;
}
这可以解决：
a1 : [-1] [0] [7] [8]
^
a2 : [1] [3] [9] [] [] [] []
^
SWAP
a1 : [1] [0] [7] [8]
^
a2 : [-1] [3] [9] [] [] [] []
^
SORT
a1 : [0] [1] [7] [8]
^
a2 : [-1] [3] [9] [] [] [] []
^
SWAP
a1 : [3] [1] [7] [8]
^
a2 : [-1] [0] [9] [] [] [] []
^
SORT
a1 : [1] [3] [7] [8]
^
a2 : [-1] [0] [9] [] [] [] []
^
SWAP
a1 : [9] [3] [7] [8]
^
a2 : [-1] [0] [1] [] [] [] []
^
SORT
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [] [] [] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [] [] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [7] [] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [7] [8] []
^
COPY
a1 : [3] [7] [8] [9]
^
a2 : [-1] [0] [1] [3] [7] [8] [9]
^
END
[首先，将a1的元素移到a1的后面。第二次合并a1和a2从a1的开头开始（即，将与当前索引比较的两个元素中的最小值写入a1，其中当前索引从0开始，最大范围为a1.length + a2.length-1） 。这将防止您覆盖a1的任何元素。
我将从头开始合并。
在最后一个元素处，输入max(lastOf(a1), lastOf(f2))。继续从任一阵列的其余部分一次咬下一个元素，直到耗尽其中一个。将其余数组的其余部分放到开始（也许我不能操作）。
有很多好的答案。我只想添加一些内容（评论已经被掩埋了）：
这只是merge-sort或类似内容（例如k-way sort）的合并阶段。仅使用就地合并例程。 “较小的数组”或“空白空间”都可以用于存储当前不在排序顺序中的“较大的数组”中的值。
可以借用不同算法的点点滴滴：-）
为什么要编写自己的代码？如果a2有足够的空白空间来容纳a1的元素，只需将tha元素从a1复制到a2中（使用arraycopy），然后使用Arrays.sort（）。这将为您提供O（n * log（n）），而您的简单方法无论如何似乎都是O（n * n）。
（但是可以在O（n）中完成合并。]
我假设您对算法的时间复杂度没有限制。我的建议是将a1的值附加到a2并应用任何快速排序等O（nlogn）排序算法。但是，如果您想进行合并，我认为这段代码可以帮助您：
public static void main(String[] args) {
// TODO Auto-generated method stub
int a1[]= new int[]{-1,0,7,8};
int a2[]= new int[7];
a2[0]=1;
a2[1]=3;
a2[2]=9;
merge(a1, a2, 3);
}
private static void merge(int[] a1, int[] a2, int lastPos) {
for ( int i = 0; i < a1.length; i++)
{
for ( int j = 0; j < a2.length; j++)
if ( a1[i] < a2[j] )
{
add(a1[i], a2, j, lastPos);
lastPos++;
break; //since a2 is also sorted
}
}
}
private static void add(int val, int[] a2, int j, int lastPos) {
for ( int i = lastPos; i > j; i--)
a2[i] = a2[i-1];
a2[j] = val;
}
合并两个排序的数组而不使用额外的内存
#include<iostream>
using namespace std ;
const int N = 100 ;
int a[N] , b[N] , n , m , len , L ;
int main() {
cin >> n ;
for( int i = 0 ; i < n ; i++ ) cin >> a[i] ;
cin >> m ;
for( int i = 0 ; i < m ; i++ ) cin >> b[i] ;
len = n + m - 1 ;
L = n + m ;
n-- , m-- ;
while( len >= 0 ) {
if( m < 0 ) a[len] = a[n--];
else if( n < 0 ) a[len] = b[m--];
else if( a[n] > b[m] ) a[len] = a[n--];
else a[len] = b[m--];
len--;
}
for( int i = 0 ; i < L ; i++ ) cout << a[i] << " " ;
}
这不过是合并排序的合并阶段，
(1,2,3,4)的所有元素复制到a1 (5,6,7,8)的末尾，现在a1将包含(4,5,6,7,8,1,2,3,4)inPlaceMerge(collection, 0<low>,3<mid>,7<high>);下的合并算法这是Java中的算法，
public static <T extends Comparable<? super T>> void inPlaceMerge(T[] collection, int low, int mid, int high) {
int left = low;
int right = mid + 1;
if(collection[mid].equals(collection[right])) {
return ;//Skip the merge if required
}
while (left <= mid && right <= high) {
// Select from left: no change, just advance left
if (collection[left].compareTo(collection[right]) <= 0) {
left ++;
} else { // Select from right: rotate [left..right] and correct
T tmp = collection[right]; // Will move to [left]
rotateRight(collection, left, right - left);
collection[left] = tmp;
// EVERYTHING has moved up by one
left ++; right ++; mid ++;
}
}
}
private static <T extends Comparable<? super T>> void rotateRight(T[] collection, int left, int numberOfElements) {
System.arraycopy(collection, left, collection, left+1, numberOfElements);
}
这里是单元测试
@Test
public void inPlaceMergeFirstTest() {
Integer[] collection = new Integer[]{5,6,7,8,1,2,3,4};
ArrayUtils.<Integer>inPlaceMerge(collection, 0,3,7);
Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
assertThat(collection, equalTo(result));
}
解决问题的更好方法是将插入排序用于合并O（1）辅助空间中的两个排序数组。
/ *，因为我们必须合并array2中的2个排序数组。我们从array2的末尾开始，并在acc的正确位置插入array元素。插入排序* /
public static int [] merge（int [] a1，int a2 []，int l1，int l2）{
int len2=l2-l1;
for(int i=l1-1;i>=0;i--){
int j=len2-1;
for(;j>=0 && j+1<l2 && a2[j]>a[i];j--){
a2[j+1]=a2[j];
}
a2[j+1]=a1[i];
len2++;
}
}
您是否尝试过System.arrayCopy？像：
...
System.arraycopy(a2, 0, a2, a1.length, a2.length);
System.arraycopy(a1, 0, a1, 0, a1.length);
...
应该在不浪费时间的情况下做到这一点（arraycopy已针对这些用例进行了优化）。