void InsertOrderList(SqList &L,ElemType x)
  {
   int i=0,j;
   while(i<L.length && x>=L.elem[i]) i++;
   for(j=L.length;j>i;j--)
     L.elem[j]=L.elem[j-1];
   L.elem[i]=x;
   L.length++;
  }

先找到与插入数x值相等的第一个元素,把后面的元素都向后移动一个单元,再把x插入
时间复杂度为O(L.length)

//我刚写完这个，没办法，不够熟练，只好练练实现
//***************************p17 2.11********************
#include <stdlib.h>
#include <stdio.h>
//本章涉及的顺序表和线性链表的类型定义如下：
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define INFEASIBLE -1
typedef int ElemType;
typedef int status;

#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量
#define LISTINCREMENT 5 //线性表存储空间的分配增量

typedef struct{
    ElemType *elem;//存储空间的基址
    int length;//当前长度
    int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位
}SqList;

//*********************************************************
status InitList_Sq(SqList &L){
    //构造一个空的线性表L
    if(!(L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)))) exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}

//************以下是线性表的输入和显示************************
status build_Sq(SqList &L){
    //如果线性表为空，则从左到右输入顺序线性表数据。
    ElemType *p;
    p=L.elem;
    int temp;
    if(L.length==0){    
        printf("请输入顺序线性表数据（输入0结束输入，请按顺序输入）\n");
        scanf("%d",&temp);
        while(temp!=0){
            if(L.length==L.listsize){ 
                //如果长度超限，则动态增加LISTINCREMENT长度
                L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
                if(!L.elem) exit(OVERFLOW);
                L.listsize+=LISTINCREMENT;
                p=L.elem+L.length;    //p指向L的最后一个结点的后续。
            }
            *p++=temp; L.length++; temp=0;
            scanf("%d",&temp);
        }
        return OK;
    }
    else return ERROR;
}

void show_Sq(SqList &L){
    //显示线性表
    int i;
    ElemType *p;
    printf("\n顺序线性表，长度为：%d，容量：%d\t*****************\n",L.length,L.listsize);
    p=L.elem;
    if(L.length==0)
        printf("线性表为空\n");
    else
        for(i=1;i<=L.length;i++){
            printf("结点%d:[%d]\t-->",i,*p++);
            if(i%4==0) printf("\n");                    //控制一行输出4个结点。
        }
    printf("\n******************************************************\n");
}
//************以上是线性表的输入和显示************************

status ListInsert(SqList &L,int i,int e){
    int j;
    if(i<1||i>L.length+1) return ERROR;
    if(L.length==LIST_INIT_SIZE){
        L.elem=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!L.elem) exit(OVERFLOW);
        L.listsize+=LISTINCREMENT;
    }
    L.length++;
    for(j=L.length-1;j>=i;j--) L.elem[j]=L.elem[j-1];
    L.elem[j]=e;    //执行插入
    return OK;
}

status insert(SqList &L,int x){
    int i=1;
    while(x>L.elem[i-1]&&i<=L.length) i++;
    if(!ListInsert(L,i,x)) return ERROR;    //在L中第i个位置之前插入新的数据元素e，L的长度加1。
    return OK;
}

void main(){
    SqList va;
    int x;
    if(!InitList_Sq(va)) printf("\n构造一个空的线性表失败！\n");
    if(!build_Sq(va)) printf("\n输入顺序线性表数据失败！\n");
    printf("\n原线性表数据为：");
    show_Sq(va);

    printf("请输入待插入数据x:");
    scanf("%d",&x);
    insert(va,x);
    show_Sq(va);
}

在插入之前查找插入位置的时候，为了提高效率，若是顺序存储，可以采用折半查找，但时间复杂度还是不变的，是O(n)，链式存储好像没更好的方法，顺序找吧，或者建个索引表，进行二级搜索