算法设计：直接插入排序

算法设计：直接插入排序

时间： 1ms        内存：128M

描述：

算法设计：实现直接插入排序。void InsertSort(RecType R[],int n)为对R[0..n-1]按递增有序进行直接插入排序。主函数已经给出。

注意：只提交void InsertSort(RecType R[],int n) //对R[0..n-1]部分。

#include <stdio.h>
#define MAXE 20         //线性表中最多元素个数
typedef int KeyType;
typedef char InfoType[10];
typedef struct          //记录类型
{
    KeyType key;        //关键字项
    InfoType data;      //其他数据项,类型为InfoType
} RecType;

int main()
{
    int i,k,n;
    KeyType a[100];
    RecType R[MAXE];
    scanf("%d",&n);
    for (i=0; i<n; i++)
        scanf("%d",&a[i]);
 
    for (i=0; i<n; i++)
        R[i].key=a[i];
    printf("初始关键字: ");      //输出初始关键字序列
    for (k=0; k<n; k++)
        printf("%3d",R[k].key);
    printf("\n");
    InsertSort(R,n);
    printf("最后结果: ");       //输出初始关键字序列
    for (k=0; k<n; k++)
        printf("%3d",R[k].key);
    printf("\n");
    return 0;
}

输入：

输入带排序元素的个数

输入待排序的整数

输出：

输出初识数据

输出排序后的数据

示例输入：

10 
9 2 7 5 6 4 8 3 1 0

示例输出：

初始关键字:   9  2  7  5  6  4  8  3  1  0
最后结果:   0  1  2  3  4  5  6  7  8  9

提示：

参考答案（内存最优[0]）：

#include <stdio.h>
#define MAXE 20         //线性表中最多元素个数
typedef int KeyType;
typedef char InfoType[10];
typedef struct          //记录类型
{
    KeyType key;        //关键字项
    InfoType data;      //其他数据项,类型为InfoType
} RecType;
void InsertSort(RecType R[],int n)
{
  int i,j;
  RecType tem;
  for( i=1;i<n;i++)
  {
     tem=R[i];
     j=i-1;
     while(j>=0&&tem.key<R[j].key)
     {
         R[j+1]=R[j];
         j--;
     }
     R[j+1]=tem;
  }
}
int main()
{
    int i,k,n;
    KeyType a[100];
    RecType R[MAXE];
    scanf("%d",&n);
    for (i=0; i<n; i++)
        scanf("%d",&a[i]);

    for (i=0; i<n; i++)
        R[i].key=a[i];
    printf("初始关键字: ");      //输出初始关键字序列
    for (k=0; k<n; k++)
        printf("%3d",R[k].key);
    printf("\n");
    InsertSort(R,n);
    printf("最后结果: ");       //输出初始关键字序列
    for (k=0; k<n; k++)
        printf("%3d",R[k].key);
    printf("\n");
    return 0;
}

参考答案（时间最优[0]）：

#include <stdio.h>
#include <malloc.h>
typedef char ElemType;
typedef struct LNode	//定义单链表结点类型
{
    ElemType data;
    struct LNode *next;
} LinkList;
void InitList(LinkList *&L)		//初始化线性表
{
    L=(LinkList *)malloc(sizeof(LinkList));  	//创建头结点
    L->next=NULL;
}
void DestroyList(LinkList *&L)	//销毁线性表
{
    LinkList *p=L,*q=p->next;
    while (q!=NULL)
    {
        free(p);
        p=q;
        q=p->next;
    }
    free(p);
}
bool ListEmpty(LinkList *L)	//判线性表是否为空表
{
    return(L->next==NULL);
}
int ListLength(LinkList *L)	//求线性表的长度
{
    LinkList *p=L;
    int i=0;
    while (p->next!=NULL)
    {
        i++;
        p=p->next;
    }
    return(i);
}
void DispList(LinkList *L)	//输出线性表
{
    LinkList *p=L->next;
    while (p!=NULL)
    {
        printf("%c ",p->data);
        p=p->next;
    }
    printf("\n");
}
bool ListInsert(LinkList *&L,int i,ElemType e)	//插入数据元素
{
    int j=0;
    LinkList *p=L,*s;			//p指向头节点,j置为0(即头节点的序号为0)
    while (j<i-1 && p!=NULL)	//查找第i-1个节点
    {
        j++;
        p=p->next;
    }
    if (p==NULL)			//未找到第i-1个节点,返回false
        return false;
    else					//找到第i-1个节点*p,插入新节点并返回1
    {
        s=(LinkList *)malloc(sizeof(LinkList));
        s->data=e;			//创建新节点*s,其data域置为e
        s->next=p->next;	//将*s插入到*p之后
        p->next=s;
        return true;
    }
}

int main()
{
    ElemType a,b,c,d,e,f;
    LinkList *h;
    InitList(h);
    printf("依次采用尾插法插入a,b,c,d,e元素\n");
    scanf("%c %c %c %c %c%*c",&a,&b,&c,&d,&e);
    ListInsert(h,1,a);
    ListInsert(h,2,b);
    ListInsert(h,3,c);
    ListInsert(h,4,d);
    ListInsert(h,5,e);
    DispList(h);
    printf("单链表h长度=%d\n",ListLength(h));
    printf("在第4个元素位置上插入f元素\n");
    scanf("%c",&f);
    ListInsert(h,4,f);
    DispList(h);
    DestroyList(h);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。