数据结构试验报告---排序(直接插入和希尔排序)

排序:

1. 直接插入排序

代码：

#include<stdio.h>

#include<malloc.h>

#define MAXSIZE 20

typedef int keytype;

typedef struct{

keytype key;

}redtype;

typedef struct{

redtype r[MAXSIZE+1];

int length;

}sqlist;

void insertsort(sqlist &L)

{

int i,j;

for(i=2;i<=L.length;i++)

if(L.r[i].key<L.r[i-1].key)

{

L.r[0]=L.r[i];

L.r[i]=L.r[i-1];

for(j=i-2;(L.r[0].key<L.r[j].key);--j)

L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0];

}

}

void main()

{

int i;

sqlist L;

printf("请输入数据的长度:\n");

scanf("%d",&L.length);

printf("请输入待排序的元素值:\n");

for(i=1;i<=L.length;i++)

scanf("%d",&L.r[i].key);

insertsort(L);

printf("排序后的元素为:\n");

for(i=1;i<=L.length;i++)

{

printf(" %d ",L.r[i].key);

}

}

运行结果：

希尔排序：

代码：#include<stdio.h>

#include<malloc.h>

#define MAXSIZE 20

typedef int keytype;

typedef struct{

keytype key;

}redtype;

typedef struct{

redtype r[MAXSIZE+1];

int length;

}sqlist;

void shellinsert(sqlist &L)

{

int i,j,k,t,dlta[10];

} printf("请输入排序的趟数:\n"); scanf("%d",&t); printf("请输入每趟排序的增量:\n"); for(i=1;i<=t;i++) scanf("%d",&dlta[i]); for(k=1;k<=t;k++) { for(i=dlta[k]+1;i<=L.length;++i) if(L.r[i].key<L.r[i-dlta[k]].key) { L.r[0]=L.r[i]; for(j=i-dlta[k];j>0&&(L.r[0].key<L.r[j].key);j-=dlta[k]) L.r[j+dlta[k]]=L.r[j]; L.r[j+dlta[k]]=L.r[0]; } }

void main()

{

int i;

sqlist L;

}

运printf("请输入数据的长度:\n"); scanf("%d",&L.length); printf("请输入元素值:\n"); for(i=1;i<=L.length;i++) scanf("%d",&L.r[i].key); shellinsert(L); for(i=1;i<=L.length;i++) { printf(" %d ",L.r[i].key); } 行结果：

本文来源：https://www.bwwdw.com/article/77wi.html