[C++知识库]1.3 向一个有序数组中插入一个新元素的算法

【问题描述】

使用一种程序设计语言写出一种向一个有序数组中插入一个新元素的算法（需要判断原数组是升序还是降序），并分析其时间复杂性。

#include <iostream>
using namespace std;
int shengxu(int a[],int x,int num);//记得声明
int jiangxu(int a[],int x,int num);
int main()
{
    int a[12]= {1,2,3,4,5,6,7,8,9,10,11,12};
    //int a[12]= {12,11,10,9,8,7,6,5,4,3,2,1};
    int x;
    cout<<"输入:";
    cin>>x;
    int num= sizeof(a) / sizeof(int);
    cout<<"整个数组的长度为："<<num<<endl;

    for(int i=0; i<2; i++)
    {
        if(a[0]<a[1])
        {
            shengxu(a,x,num);
            break;
        }
        if(a[0]>a[1])
        {
            jiangxu(a,x,num);
            break;
        }
        if(a[i]==a[i+1])
        {
            continue;
        }
    }
}

int shengxu(int a[],int x,int num)
{
    int temp=0;
    if(x>a[num-1])
    {
        a[num]=x;
        for(int i=0; i<=num; i++)
        {
            cout<<a[i]<<" ";
        }
    }
    else
    {
        for(int i=0; i<num; i++)
        {
            if(x>=a[i]&&x<a[i+1])
            {
                temp=i;
                break;
            }
        }
        for(int i=num; i>=temp; i--)
        {
            a[i+1]=a[i];//将每个数字向后移动一位
        }
        a[temp]=x;
        num++;
        for(int i=0; i<num; i++)
        {
            cout<<a[i]<<" ";
        }
    }
}

int jiangxu(int a[],int x,int num)
{
    int temp=0;

    if(x<a[num-1])
    {
        a[num]=x;
        for(int i=0; i<=num; i++)
        {
            cout<<a[i]<<" ";
        }
    }
    else
    {
        for(int i=0; i<num; i++)
        {
            if(a[i]<=x&&x<=a[i-1])
            {
                temp=i;
                break;
            }
        }
        for(int i=num-1; i>=temp; i--)
        {
            a[i+1]=a[i];
        }
        a[temp]=x;
        num++;
        for(int i=0; i<num; i++)
        {
            cout<<a[i]<<" ";
        }
    }
}