合并两个有序数组

admin1

合并两个有序数组
问题描述
有两个排序的数组a和b，内存在a的末尾有足够多的剩余空间容纳b
实现一个函数将b中所有的数字插入到a，最终结果是有序的

实现思路
由于a、b两个数组已经排序，并且题目提示在a数组的末尾有足够多空间容纳b数组，因此我们将b数组赋值给a数组时，可以考虑从两个数组的末尾元素开始比较，每次比较a数组和b数组的最后一个元素，将较大的那个元素作为新的a数组的最后一个元素，这样时间复杂度为O(n)，而空间复杂度为O(1)

代码
显示数组的函数[code]#include<iostream>
#include<cstdio>
using namespace std;

//显示数组
void DisplayArray( char *arrayName, int *a, int len )
{
    if ( a== NULL || len <= 0)
    {
        cout<<"数组 "<<arrayName<<" 为空"<<endl;
        return;
    }
    cout<<"Element in array : "<<arrayName<<endl;
    for (int i = 0; i < len; i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}[/code][code][code][code]/*合并两个数组
a：第一个数组，b：第二个数组
totalalen, a数组中的总长度， alen：a数组实际长度，blen：b数组长度
*/
void MergeArray(int *a, int *b,  int totalalen, int alen, int blen )
{
    //参数检查
    if ( a== NULL || b== NULL  )
    {
        cout<<"输入数组为空，请检查"<<endl;
        return;
    }

    if ( alen <= 0 || blen <= 0 || totalalen < alen+blen)
    {
        cout<<"输入数组长度错误，请检查"<<endl;
        return;
    }

    int newidx = alen + blen - 1;//合并后数组的索引
    int aidx = alen -1;//a数组的索引
    int bidx = blen -1;//b数组的索引

    while (aidx >= 0 && bidx >= 0)
    {
        if (a[aidx] > b[bidx] )
            a[newidx--] = a[aidx--];
        else
            a[newidx--] = b[bidx--];
    }

    while ( bidx >= 0)
    {
        a[newidx--] = b[bidx--];
    }
}[/code][/code][/code]