本文实例讲述了C语言实现在数组A上有序合并数组B的方法，分享给大家供大家参考。具体分析如下：
题目：数组A和数组B均有序，数组A有足够大内存来容纳数组B，将数组B有序合并到数组A中
分析：如果由前至后合并，复杂度将会是O(N2)，这样的复杂度显然不是最优解，利用两个指针指向两个数组的尾部，从后往前遍历，这样的复杂度为O(n2)
由此可以写出下面的代码：
#include
#include
#include
using namespace std;
int arrayA[10] = {1, 3, 5, 7, 9};
int arrayB[] = {2, 4, 6, 8, 10};
const int sizeB = sizeof arrayB / sizeof *arrayB;
const int sizeA = sizeof arrayA / sizeof *arrayA - sizeB;
int* mergeArray(int *arrayA, int sizeA, int *arrayB, int sizeB)
{
if (arrayA == NULL || arrayB == NULL || sizeA < 0 || sizeB < 0)
return NULL;
int posA = sizeA - 1;
int posB = sizeB - 1;
while (posA >= 0 && posB >= 0)
{
if (arrayA[posA] < arrayB[posB])
{
arrayA[posA + posB + 1] = arrayB[posB];
posB--;
}
else
{
arrayA[posA + posB + 1] = arrayA[posA];
posA--;
}
copy(arrayA, arrayA + 10, ostream_iterator(cout, " "));
system("pause");
}
return arrayA;
}
void main()
{
int *result = mergeArray(arrayA, sizeA, arrayB, sizeB);
copy(result, result + 10, ostream_iterator(cout, " "));
cout = 0 && posB >= 0)
{
if (arrayA[posA] < arrayB[posB])
{
arrayA[posA + posB + 1] = arrayB[posB];
posB--;
}
else
{
arrayA[posA + posB + 1] = arrayA[posA];
posA--;
}
copy(arrayA, arrayA + size, ostream_iterator(cout, " "));
system("pause");
}
//出现两种情形：
//1. posA < 0 && posB >= 0
//2. posA >= 0 && posB < 0
//只有第1种情形需要进行处理
if (posA < 0 && posB >= 0)
{
while (posB >= 0)
{
arrayA[posA + posB + 1] = arrayB[posB];
posB--;
}
}
return arrayA;
}
相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。