如何将两个已排序的数组合并为一个已排序的数组？

小开

任何可以做的改进都是微观优化，整个算法是正确的。

小开

最佳答案

一个小的改进，但是在主循环之后，当到达另一个输入数组的末尾时，您可以使用 System.arraycopy来复制其中一个输入数组的尾部。但是，这不会改变解决方案的 O(n)性能特征。

小开

public static int[] merge(int[] a, int[] b) {


int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;


while (i < a.length && j < b.length)
answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];


while (i < a.length)
answer[k++] = a[i++];


while (j < b.length)
answer[k++] = b[j++];


return answer;
}

有点紧凑，但完全一样！

小开

我不得不用 javascript 写下来，就是这样:

function merge(a, b) {
var result = [];
var ai = 0;
var bi = 0;
while (true) {
if ( ai < a.length && bi < b.length) {
if (a[ai] < b[bi]) {
result.push(a[ai]);
ai++;
} else if (a[ai] > b[bi]) {
result.push(b[bi]);
bi++;
} else {
result.push(a[ai]);
result.push(b[bi]);
ai++;
bi++;
}
} else if (ai < a.length) {
result.push.apply(result, a.slice(ai, a.length));
break;
} else if (bi < b.length) {
result.push.apply(result, b.slice(bi, b.length));
break;
} else {
break;
}
}
return result;
}

小开

//How to merge two sorted arrays into a sorted array without duplicates?
//simple C Coding
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


main()
{
int InputArray1[] ={1,4,5,7,8,9,12,13,14,17,40};
int InputArray2[] ={4,5,11,14,15,17,18,19,112,122,122,122,122};
int n=10;
int OutputArray[30];
int i=0,j=0,k=0;
//k=OutputArray
while(i<11 && j<13)
{
if(InputArray1[i]<InputArray2[j])
{
if (k == 0 || InputArray1[i]!= OutputArray[k-1])
{
OutputArray[k++] = InputArray1[i];
}
i=i+1;
}
else if(InputArray1[i]>InputArray2[j])
{
if (k == 0 || InputArray2[j]!= OutputArray[k-1])
{
OutputArray[k++] = InputArray2[j];
}
j=j+1;
}
else
{
if (k == 0 || InputArray1[i]!= OutputArray[k-1])
{
OutputArray[k++] = InputArray1[i];
}
i=i+1;
j=j+1;
}
};
while(i<11)
{
if(InputArray1[i]!= OutputArray[k-1])
OutputArray[k++] = InputArray1[i++];
else
i++;
}
while(j<13)
{
if(InputArray2[j]!= OutputArray[k-1])
OutputArray[k++] = InputArray2[j++];
else
j++;
}
for(i=0; i<k; i++)
{
printf("sorted data:%d\n",OutputArray[i]);
};
}

小开

    public class Merge {


// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {


// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);


// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}


// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if      (i > mid)              a[k] = aux[j++];
else if (j > hi)               a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else                           a[k] = aux[i++];
}


// postcondition: a[lo .. hi] is sorted
assert isSorted(a, lo, hi);
}


// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}


public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}




/***********************************************************************
*  Helper sorting functions
***********************************************************************/


// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}


// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}




/***********************************************************************
*  Check if array is sorted - useful for debugging
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}


private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}




/***********************************************************************
*  Index mergesort
***********************************************************************/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {


// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
}


// merge back to a[]
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if      (i > mid)                    index[k] = aux[j++];
else if (j > hi)                     index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
else                                 index[k] = aux[i++];
}
}


// return a permutation that gives the elements in a[] in ascending order
// do not change the original array a[]
public static int[] indexSort(Comparable[] a) {
int N = a.length;
int[] index = new int[N];
for (int i = 0; i < N; i++)
index[i] = i;


int[] aux = new int[N];
sort(a, index, aux, 0, N-1);
return index;
}


// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
}


// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}


// Read strings from standard input, sort them, and print.
public static void main(String[] args) {
String[] a = StdIn.readStrings();
Merge.sort(a);
show(a);
}
}

小开

这里是更新的功能。它删除副本，希望有人会发现这个可用:

public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) {
long[] answer = new long[a.length + b.length];
int i = 0, j = 0, k = 0;
long tmp;
while (i < a.length && j < b.length) {
tmp = a[i] < b[j] ? a[i++] : b[j++];
for ( ; i < a.length && a[i] == tmp; i++);
for ( ; j < b.length && b[j] == tmp; j++);
answer[k++] = tmp;
}
while (i < a.length) {
tmp = a[i++];
for ( ; i < a.length && a[i] == tmp; i++);
answer[k++] = tmp;
}
while (j < b.length) {
tmp = b[j++];
for ( ; j < b.length && b[j] == tmp; j++);
answer[k++] = tmp;
}
return Arrays.copyOf(answer, k);
}

小开

我认为为更大的排序数组引入跳过列表可以减少比较的次数，并且可以加快复制到第三个数组的过程。如果数组太大，这可能是好事。

小开

因为这个问题没有假设任何特定的语言。假设数组已经排序。

方法1-使用数字数组: 进口麻木

arr1 = numpy.asarray([ 1,  2,  3,  4,  5,  6,  7,  8,  9, 11, 14, 15, 55])
arr2 = numpy.asarray([11, 32, 43, 45, 66, 76, 88])


array = numpy.concatenate((arr1,arr2), axis=0)
array.sort()

方法2-使用列表，假设列表已排序。

list_new = list1.extend(list2)
list_new.sort()

小开

import java.util.Arrays;


public class MergeTwoArrays {


static int[] arr1=new int[]{1,3,4,5,7,7,9,11,13,15,17,19};
static int[] arr2=new int[]{2,4,6,8,10,12,14,14,16,18,20,22};


public static void main(String[] args){
int FirstArrayLocation =0 ;
int SecondArrayLocation=0;
int[] mergeArr=new int[arr1.length + arr2.length];


for ( int i=0; i<= arr1.length + arr2.length; i++){
if (( FirstArrayLocation < arr1.length ) && (SecondArrayLocation < arr2.length)){
if ( arr1[FirstArrayLocation] <= arr2[SecondArrayLocation]){
mergeArr[i]=arr1[FirstArrayLocation];
FirstArrayLocation++;
}else{
mergeArr[i]=arr2[SecondArrayLocation];
SecondArrayLocation++;
}
}
else if(SecondArrayLocation < arr2.length){
mergeArr[i]=arr2[SecondArrayLocation];
SecondArrayLocation++;
}else if ( FirstArrayLocation < arr1.length ){
mergeArr[i]=arr1[FirstArrayLocation];
FirstArrayLocation++;
}
}
}
}

小开

除了使用 System.arrayCopy 复制其余的数组元素之外，这个解决方案与其他文章非常相似。

private static int[] sortedArrayMerge(int a[], int b[]) {
int result[] = new int[a.length +b.length];
int i =0; int j = 0;int k = 0;
while(i<a.length && j <b.length) {
if(a[i]<b[j]) {
result[k++] = a[i];
i++;
} else {
result[k++] = b[j];
j++;
}
}
System.arraycopy(a, i, result, k, (a.length -i));
System.arraycopy(b, j, result, k, (b.length -j));
return result;
}

小开

下面是用 javascript 编写的一个简短形式:

function sort( a1, a2 ) {


var i = 0
, j = 0
, l1 = a1.length
, l2 = a2.length
, a = [];


while( i < l1 && j < l2 ) {


a1[i] < a2[j] ? (a.push(a1[i]), i++) : (a.push( a2[j]), j++);
}


i < l1 && ( a = a.concat( a1.splice(i) ));
j < l2 && ( a = a.concat( a2.splice(j) ));


return a;
}

小开

它可以在下面的4个语句中完成

 int a[] = {10, 20, 30};
int b[]= {9, 14, 11};
int res[]=new int[a.legth+b.length];
System.arraycopy(a,0, res, 0, a.length);
System.arraycopy(b,0,res,a.length, b.length);
Array.sort(res)

小开

public int[] merge(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int aIndex, bIndex = 0;


for (int i = 0; i < result.length; i++) {
if (aIndex < a.length && bIndex < b.length) {
if (a[aIndex] < b[bIndex]) {
result[i] = a[aIndex];
aIndex++;
} else {
result[i] = b[bIndex];
bIndex++;
}
} else if (aIndex < a.length) {
result[i] = a[aIndex];
aIndex++;
} else {
result[i] = b[bIndex];
bIndex++;
}
}


return result;
}

小开

Apache 集合从版本4开始就支持校对方法; 您可以使用 collate方法在:

org.apache.commons.collections4.CollectionUtils

这里引用 javadoc 的话:

collate(Iterable<? extends O> a, Iterable<? extends O> b, Comparator<? super O> c)
将两个已排序的集合 a和 b合并为一个, 排序的列表，使元素的顺序根据保留比较器 c。

不要重新发明轮子! 参考文档: Http://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/collectionutils.html

小开

var arrCombo = function(arr1, arr2){
return arr1.concat(arr2).sort(function(x, y) {
return x - y;
});
};

小开

public static int[] merge(int[] a, int[] b) {
int[] mergedArray = new int[(a.length + b.length)];
int i = 0, j = 0;
int mergedArrayIndex = 0;
for (; i < a.length || j < b.length;) {
if (i < a.length && j < b.length) {
if (a[i] < b[j]) {
mergedArray[mergedArrayIndex] = a[i];
i++;
} else {
mergedArray[mergedArrayIndex] = b[j];
j++;
}
} else if (i < a.length) {
mergedArray[mergedArrayIndex] = a[i];
i++;
} else if (j < b.length) {
mergedArray[mergedArrayIndex] = b[j];
j++;
}
mergedArrayIndex++;
}
return mergedArray;
}

小开

我最喜欢的编程语言是 JavaScript

function mergeSortedArrays(a, b){
var result = [];


var sI = 0;
var lI = 0;
var smallArr;
var largeArr;
var temp;


if(typeof b[0] === 'undefined' || a[0]<b[0]){
smallArr = a;
largeArr = b;
} else{
smallArr = b;
largeArr = a;
}


while(typeof smallArr[sI] !== 'undefined'){
result.push(smallArr[sI]);
sI++;


if(smallArr[sI]>largeArr[lI] || typeof smallArr[sI] === 'undefined'){
temp = smallArr;
smallArr = largeArr;
largeArr = temp;
temp = sI;
sI = lI;
lI = temp;
}
}
return result;
}

小开

我很惊讶没有人提到这个更酷、更高效、更紧凑的实现:

public static int[] merge(int[] a, int[] b) {
int[] answer = new int[a.length + b.length];
int i = a.length - 1, j = b.length - 1, k = answer.length;


while (k > 0)
answer[--k] =
(j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
return answer;
}

兴趣点

请注意，它与其他任何 O (n)算法执行的操作数相同或更少，但是在一个 while 循环中只执行一条语句！
如果两个数组的大小大致相同，那么 O (n)的常数是相同的。然而，如果数组真的是不平衡的，那么使用 System.arraycopy的版本将会获胜，因为在内部它可以使用单个 x86汇编指令来完成这项工作。
注意 a[i] >= b[j]而不是 a[i] > b[j]。这保证了“稳定性”，即当 a 和 b 的元素相等时，我们需要 a 之前 b 的元素。

小开

算法可以通过多种方式进行改进，例如，检查 a[m-1]<b[0]或 b[n-1]<a[0]是否合理。在任何一种情况下，都没有必要进行更多的比较。算法可以按照正确的顺序将源数组复制到生成的数组中。

更复杂的增强可能包括搜索交错部分并仅为它们运行合并算法。当合并数组的大小相差几十倍时，它可以节省很多时间。

小开

这个问题与归并排序算法有关，归并排序算法是将两个排序的子数组合并成一个单独的排序子数组。CLRS书给出了一个算法的例子，通过在每个数组的末尾添加一个前哨值(一个比较值和“大于其他任何值”的值) ，清除了检查是否已经到达终点的需要。

这是我用 Python 写的，但也可以很好地翻译成 Java:

def func(a, b):
class sentinel(object):
def __lt__(*_):
return False


ax, bx, c = a[:] + [sentinel()], b[:] + [sentinel()], []
i, j = 0, 0


for k in range(len(a) + len(b)):
if ax[i] < bx[j]:
c.append(ax[i])
i += 1
else:
c.append(bx[j])
j += 1


return c

小开

也许可以用 System.arraycopy

public static byte[] merge(byte[] first, byte[] second){
int len = first.length + second.length;
byte[] full = new byte[len];
System.arraycopy(first, 0, full, 0, first.length);
System.arraycopy(second, 0, full, first.length, second.length);
return full;
}

小开

public static void main(String[] args) {
int[] arr1 = {2,4,6,8,10,999};
int[] arr2 = {1,3,5,9,100,1001};


int[] arr3 = new int[arr1.length + arr2.length];


int temp = 0;


for (int i = 0; i < (arr3.length); i++) {
if(temp == arr2.length){
arr3[i] = arr1[i-temp];
}
else if (((i-temp)<(arr1.length)) && (arr1[i-temp] < arr2[temp])){
arr3[i] = arr1[i-temp];
}
else{
arr3[i] = arr2[temp];
temp++;
}
}


for (int i : arr3) {
System.out.print(i + ", ");
}
}

产出为:

1,2,3,4,5,6,8,9,10,100,999,1001,

小开

您可以使用三元运算符使代码更加紧凑一些

public static int[] mergeArrays(int[] a1, int[] a2) {
int[] res = new int[a1.length + a2.length];
int i = 0, j = 0;


while (i < a1.length && j < a2.length) {
res[i + j] = a1[i] < a2[j] ? a1[i++] : a2[j++];
}


while (i < a1.length) {
res[i + j] = a1[i++];
}


while (j < a2.length) {
res[i + j] = a2[j++];
}


return res;
}

小开

下面是我的 Java 实现，它可以删除重复。

public static int[] mergesort(int[] a, int[] b) {
int[] c = new int[a.length + b.length];
int i = 0, j = 0, k = 0, duplicateCount = 0;


while (i < a.length || j < b.length) {
if (i < a.length && j < b.length) {
if (a[i] == b[j]) {
c[k] = a[i];
i++;j++;duplicateCount++;
} else {
c[k] = a[i] < b[j] ? a[i++] : b[j++];
}
} else if (i < a.length) {
c[k] = a[i++];
} else if (j < a.length) {
c[k] = b[j++];
}
k++;
}


return Arrays.copyOf(c, c.length - duplicateCount);
}

小开

public static int[] mergeSorted(int[] left, int[] right) {
System.out.println("merging " + Arrays.toString(left) + " and " + Arrays.toString(right));
int[] merged = new int[left.length + right.length];
int nextIndexLeft = 0;
int nextIndexRight = 0;
for (int i = 0; i < merged.length; i++) {
if (nextIndexLeft >= left.length) {
System.arraycopy(right, nextIndexRight, merged, i, right.length - nextIndexRight);
break;
}
if (nextIndexRight >= right.length) {
System.arraycopy(left, nextIndexLeft, merged, i, left.length - nextIndexLeft);
break;
}
if (left[nextIndexLeft] <= right[nextIndexRight]) {
merged[i] = left[nextIndexLeft];
nextIndexLeft++;
continue;
}
if (left[nextIndexLeft] > right[nextIndexRight]) {
merged[i] = right[nextIndexRight];
nextIndexRight++;
continue;
}
}
System.out.println("merged : " + Arrays.toString(merged));
return merged;
}

只是和原来的解决方案有一点点不同

小开

您可以使用2个线程来填充结果数组，一个从前面，一个从后面。

在数字的情况下，这可以在没有任何同步的情况下工作，例如，如果每个线程插入一半的值。

小开

GallopSearch 合并: **O (log (n) * log (i))**而不是 O (n)

我在评论中实施了灰胡子的建议。主要是因为我需要这段代码的一个高效的关键任务版本。

代码使用一个 gallopSearch，它是 O (log (i)) ，其中 i 是与当前指数的距离存在相关指数。
代码使用 binarySearch 作为 gallop 搜索之后的确定了适当的，范围。因为飞驰限制了这个较小的 Range 生成的 binarySearch 也是 O (log (i))
奔跑和合并是向后进行的，这看起来不像任务关键，但它允许在地方合并数组。如果其中一个你的数组有足够的空间来存储结果值，你可以简单地使用它作为合并数组还有结果数组。在这种情况下，必须指定数组内的有效范围。
在这种情况下，它不需要分配内存(在关键操作中节省大量内存)。它只是确保不会也不能覆盖任何未处理的值(这只能向后进行)。实际上，对于输入和结果都使用相同的数组。不会有任何不良影响。
我一直使用 Integer.compare () ，这样就可以将其转换为其他用途。
有一些机会，我可能有一点失误，没有利用的信息，我以前已经证明。例如，在两个值的范围内进行二进制搜索，已经为其检查了一个值。也许还有一种更好的方法来声明主循环，如果将反转的 c 值按顺序组合成两个操作，那么就不需要这个 c 值了。既然你知道你每次都会做一个然后做另一个。还有地方可以擦亮。

这应该是最有效的方法，其时间复杂度为 O (log (n) * log (i))而不是 O (n)。以及 O (n)的最坏情况时间复杂度。如果你的数组是块状的并且有很长的值串在一起，这将使其他任何方法相形见绌，否则它只会比它们更好。

它在合并数组的末端有两个读取值，在结果数组中有一个写入值。在找出哪个是最终值较小之后，它对该数组进行快速搜索。1、2、4、8、16、32等等。当它找到另一个数组的读取值较大的范围时。它进行二进制搜索(将范围缩减一半，搜索正确的一半，重复直到单个值)。然后数组将这些值复制到写入位置。请记住，由于需要，移动副本时不能覆盖任一读数组中的相同值(这意味着写数组和读数组可以是相同的)。然后它对另一个数组执行相同的操作，现在已知该数组小于另一个数组的新读取值。

static public int gallopSearch(int current, int[] array, int v) {
int d = 1;
int seek = current - d;
int prevIteration = seek;
while (seek > 0) {
if (Integer.compare(array[seek], v) <= 0) {
break;
}
prevIteration = seek;
d <<= 1;
seek = current - d;
if (seek < 0) {
seek = 0;
}
}
if (prevIteration != seek) {
seek = binarySearch(array, seek, prevIteration, v);
seek = seek >= 0 ? seek : ~seek;
}
return seek;
}


static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = list[mid];
int cmp = Integer.compare(midVal, v);
if (cmp < 0) {
low = mid + 1;
} else if (cmp > 0) {
high = mid - 1;
} else {
return mid;// key found
}
}
return -(low + 1);// key not found.
}


static public int[] sortedArrayMerge(int[] a, int[] b) {
return sortedArrayMerge(null, a, a.length, b, b.length);
}


static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
int write = aRead + bRead, length, gallopPos;
if ((results == null) || (results.length < write)) {
results = new int[write];
}
if (aRead > 0 && bRead > 0) {
int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
while (aRead > 0 && bRead > 0) {
switch (c) {
default:
gallopPos = gallopSearch(aRead, a, b[bRead-1]);
length = (aRead - gallopPos);
write -= length;
aRead = gallopPos;
System.arraycopy(a, gallopPos--, results, write, length);
c = -1;
break;
case -1:
gallopPos = gallopSearch(bRead, b, a[aRead-1]);
length = (bRead - gallopPos);
write -= length;
bRead = gallopPos;
System.arraycopy(b, gallopPos--, results, write, length);
c = 1;
break;
}
}
}
if (bRead > 0) {
if (b != results) {
System.arraycopy(b, 0, results, 0, bRead);
}
} else if (aRead > 0) {
if (a != results) {
System.arraycopy(a, 0, results, 0, aRead);
}
}
return results;
}

这应该是最有效的方法。

有些答案具有重复删除能力。这将需要一个 O (n)算法，因为您必须实际比较每个项目。因此，这里有一个独立的，适用于事后的事实。如果您需要查看所有的条目，那么您不能快速浏览多个条目，但是如果您有很多重复条目，那么您可以快速浏览重复条目。

static public int removeDuplicates(int[] list, int size) {
int write = 1;
for (int read = 1; read < size; read++) {
if (list[read] == list[read - 1]) {
continue;
}
list[write++] = list[read];
}
return write;
}

更新: 以前的答案，不是可怕的代码，但明显低于上述。

又一个不必要的超优化。它不仅为结束位调用数组拷贝，还为开始位调用数组拷贝。通过 binarySearch 将 O (log (n))中的任何介绍性非重叠处理到数据中。O (log (n) + n)等于 O (n) ，在某些情况下，这种效果会非常明显，特别是在合并数组之间根本没有重叠的情况下。

private static int binarySearch(int[] array, int low, int high, int v) {
high = high - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = array[mid];
if (midVal > v)
low = mid + 1;
else if (midVal < v)
high = mid - 1;
else
return mid; // key found
}
return low;//traditionally, -(low + 1);  // key not found.
}


private static int[] sortedArrayMerge(int a[], int b[]) {
int result[] = new int[a.length + b.length];
int k, i = 0, j = 0;
if (a[0] > b[0]) {
k = i = binarySearch(b, 0, b.length, a[0]);
System.arraycopy(b, 0, result, 0, i);
} else {
k = j = binarySearch(a, 0, a.length, b[0]);
System.arraycopy(a, 0, result, 0, j);
}
while (i < a.length && j < b.length) {
result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
}
if (j < b.length) {
System.arraycopy(b, j, result, k, (b.length - j));
} else {
System.arraycopy(a, i, result, k, (a.length - i));
}
return result;
}

小开

为了在 O (m + n)时间复杂度下对两个排序的数组进行边缘化，可以使用下面的方法，只用一个循环。 M 和 n 是第一个数组和第二个数组的长度。

public class MargeSortedArray {
public static void main(String[] args) {
int[] array = new int[]{1,3,4,7};
int[] array2 = new int[]{2,5,6,8,12,45};
int[] newarry = margeToSortedArray(array, array2);
//newarray is marged array
}


// marge two sorted array with o(a+n) time complexity
public static int[] margeToSortedArray(int[] array, int[] array2) {
int newarrlen = array.length+array2.length;
int[] newarr = new int[newarrlen];


int pos1=0,pos2=0;
int len1=array.length, len2=array2.length;


for(int i =0;i<newarrlen;i++) {
if(pos1>=len1) {
newarr[i]=array2[pos2];
pos2++;
continue;
}
if(pos2>=len2) {
newarr[i]=array[pos1];
pos1++;
continue;
}


if(array[pos1]>array2[pos2]) {
newarr[i]=array2[pos2];
pos2++;
} else {
newarr[i]=array[pos1];
pos1++;
}
}


return newarr;
}


}

小开

var arr1 = [2,10,20,30,100];
var arr2 = [2,4,5,6,7,8,9];
var j = 0;
var i =0;
var newArray = [];


for(var x=0;x< (arr1.length + arr2.length);x++){
if(arr1[i] >= arr2[j]){                //check if element arr2 is equal and less than arr1 element
newArray.push(arr2[j]);
j++;
}else if(arr1[i] < arr2[j]){            //check if element arr1 index value  is less than arr2 element
newArray.push(arr1[i]);
i++;
}
else if(i == arr1.length || j < arr2.length){    // add remaining arr2 element
newArray.push(arr2[j]);
j++
}else{                                                   // add remaining arr1 element
newArray.push(arr1[i]);
i++
}


}


console.log(newArray);

如何将两个已排序的数组合并为一个已排序的数组？

GallopSearch 合并: O (log (n) * log (i))而不是 O (n)

GallopSearch 合并: **O (log (n) * log (i))**而不是 O (n)