兩個有序數組合並演算法

A. 兩個已經排序的數組如何合並成一個新的有序數組

改一下排序函數就可以了。就可以不用每次去比較所宏配有元素了。void MergeArray(int* a, int size1, int* b, int size2, int* c, int size3)/*將數組遞增數組a，b合並成遞減數塵絕戚組c，size1，size2，size3分別是a，b，c數組的大小*/
{
int i = 0, j = 0, k = 0;

int temp = 0;

k = size3 - 1; /*數組c最後一個元素空間*/

while(i<size1||j<size2)
{
/*比較a，b數組當前值，取出較小元素，保存到數組派陵c中(小值在數組c中由後至前保存)*/

if(a[i] < b[j])
{
c[k] = a[i];
i++;
}
else
{
c[k] = b[j];
j++;
}
k--;
}
}

B. 如何將兩個有序數組合並為一個有序數組，用函數做，一個循環搞定

這很簡單：
代碼如下（此處不考慮Object，假設為int[ ]）：
public int[ ] getNewArrays(int[ ] one, int [] two){
int len=one.length;
int len2=two.length;
int len3=oneLength+twoLength; //得到兩數組長度和;
int[] newArray=new int [len3]; //創建第三個數組，長度=兩數組長度之和;
for(int i=0;i<len3;i++){
if(i<len){ //如果i<len,則賦值為one中的元素;
newArray[i]=one[i];
continue;
}
int t=i-len; // t 從0開始
newArray[i]=two[t]; //後面的元素 賦值為two中的元素;

} //對第三個數組一一賦值，值為前兩個數組;
Arrays.sort(newArray); //對第三個數組排序;此處使用的是java自帶的sort方法;
//也可使用冒泡排序,此處不演示;
return newArray;
}
完

C. java合並兩個有序數組

package com.lili.test;

import java.util.Random;
import java.util.Arrays;
/**]
* 合並兩數組為一個有序數組
* @作者: lili
* @日期: Nov 9, 2009
*/
public class TestMe {

/**
* @param args
* @throws ParseException
*/
public static void main(String[] args) {

int a[] = new int[6];
int b[] = new int[6];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100);
}
for (int i = 0; i < b.length; i++) {
b[i] = r.nextInt(100);
}
System.out.println("合並前--------------------------------------");
for (int i = 0; i < a.length; i++) {
System.out.print("A[" + i + "] = " + a[i]+"\t");
}
System.out.println();
for (int i = 0; i < b.length; i++) {
System.out.print("B[" + i + "] = " + b[i]+"\t");
}
System.out.println();
System.out.println("合並前--------------------------------------");
int[] c = concatArray(a, b);
System.out.println("合並後大小：" + c.length);
for (int i = 0; i < c.length; i++) {
System.out.print("c[" + i + "] = " + c[i]+"\t");
if (i % 3 == 0 && i!=0) {
System.out.println();
}
}
}

/**
* 合並兩個 int[]型數組為一個有序數組(升序)
*
* @param aArray
* @param bArray
* @return
*/
public static int[] concatArray(int[] aArray, int[] bArray) {
int[] cArray = null;
/*
* 保證參數的合法證
*/
if (aArray == null || bArray == null) {
return aArray == null ? bArray : aArray;
}
if (aArray != null && bArray != null) {
cArray = new int[aArray.length + bArray.length];
}
/*
* 合並前排序
*/
Arrays.sort(aArray);
Arrays.sort(bArray);
/*
* 各數組 的當前 index
*/
int aArray_index = 0;
int bArray_index = 0;
/*
* 開始合並
*/
for (int i = 0; i < cArray.length; i++) {
if (aArray_index > aArray.length - 1
|| bArray_index > bArray.length - 1) {
break;
} else {
int a = aArray[aArray_index];
int b = bArray[bArray_index];

if (a == getMin(a, b)) {
aArray_index++;

cArray[i] = a;
} else {
bArray_index++;
cArray[i] = b;
}
}
}
/*
* 其中一個數組被合並完畢
*/
if (aArray_index < aArray.length - 1) {
for (int i = aArray_index + bArray.length; i < cArray.length; i++) {
cArray[i] = aArray[aArray_index++];
}
} else if (bArray_index < bArray.length - 1) {
for (int i = bArray_index + aArray.length; i < cArray.length; i++) {
cArray[i] = bArray[bArray_index++];
}
}
return cArray;
}

/**
* 求兩數之間比較小的一個數
*
* @param a
* @param b
* @return
*/
public static int getMin(int a, int b) {
return a - b <= 0 ? a : b;
}
}

D. 如何用C語言編程將兩個有序數組a,b合並成一個數組c

就以你的例子來寫，可適當修改為更普遍的

演算法核心代碼為：

int i = j = k = 0;
//灶敏閉循環比較，將小的插入到C數組中

while ( i < 3 && j < 3) {
if (a [i] < b [j]) c[k++] = a[i++];
else c[k++] = b[j++];

}
//處理其中一個數組剩下

while (i < 3) c[k++] = a[i++];
while( j < 3) c[k++] = b[j++];
或許有拿帶更好的實隱裂現，你自己在想想吧！

E. LeetCode題解：合並兩個有序數組

給你兩個按非遞減排序的整數數組nums1和nums2，另外有兩個整數m和n，分別表示nums1和nums2中的元素數目。
請你合並nums1和nums2，使合喚賀掘並後的數組同樣按非遞減順序排列。
注意：最終，合並後數組不應由函數返回，而是存儲在數組nums1中。為了應對這種情況，nums1的初始長度為m+n，其中前m個元素表示應合並的元素，後n個元拍模素為0，應忽略，num2的長度為n。

輸入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出： [1,2,2,3,5,6]
解釋： 需要合並 [1,2,3] 和 [2,5,6] 。
合並結果是 [1,2,2,3,5,6] ，其中斜體加粗標注的為 nums1 中的元素。

復雜度分析

比較兩個數組的元素大小和核，每次將比較的較大值放置到當前的最大索引的位置。如果一方提前放置完畢，那麼剩下的都放置另一方的元素。

復雜度分析

F. 兩個數組合並成一個有序數組

這是個很成熟的演算法。

#include <鬧散stdio.h>

void merge(int* a, int m, int* b, int n, int* c) {

int i,j,k;

for (i=0, j=0, k=0; (i<m||j<n)&&k<(m+n);i++,j++,k++) {

if (i>=m){

c[k] = b[j];

continue;

}

if (j>=n) {

c[k] = a[i];

continue;

}

if (a[i] > b[j]) {

c[k] = b[j];

i--;

} else {

液遲氏 c[k] =a[i];

j--;

}

}

}

int main() {

int nums1[]={1,2,3,7,8,9};

int nums2[]={4,5,6};

int nums3[9]; //保存合並結果

merge(nums1, 6, nums2, 3, nums3);

for(int i=0;i<9;i++)

printf("旦沒%d ",nums3[i]);

printf(" ");

return 0;

}