文档介绍：南昌航空大学
数学与信息科学学院
实验报告
课程名称: 数据结构
实验名称: 内部排序
实验类型: 验证性□综合性□设计性□
实验室名称: 数学实验室D208
班级学号: 05071113
学生姓名: 杨义
任课教师(教师签名):
成绩:
实验日期:
一、实验目的
《数据结构(C语言版)》上的五大类排序算法的思想。
(时间复杂度和空间复杂度)。
,并了解其时间复杂度和空间复杂度。
二、实验用仪器设备、器材或软件环境
Microsoft Word XP、MP3、编译器Win-TC
三、实验原理、方案设计、程序框图、预编程序等
1. 实验原理
(1)在本次实验中,我选择了这五个算法:冒泡排序(BubbleSort)、直接插入排序(InsertSort)、
快速排序(QuickSort)、简单选择排序(SimpleSeletctionSort)、希尔排序(ShellSort),其算法思想如下:
①冒泡排序(BubbleSort):在待排序的记录序列中,从第一个排序记录R1开始,依次比较两个相邻记录的关键字Kj和Kj+1,如果是反序,则这两个记录进行交换。这样,在一趟比较完毕后,关键字最大的记录就被交换到后面。然后,在对前面n-1个记录执行上述过程,如此重复n-1次。
②直接插入排序(InsertSort):将无序记录序列R1, R2 ,…,Rn 分成两部分:前一部分R1, R2 ,…,Ri-1是已排好序的,后一部分Ri, Ri+1 ,…,Rn是未排好序的。这时,用记录Ri的关键字Ki 分别与记录
R1, R2 ,…,Ri-1的关键字K1, K2 ,…,Ki-1进行比较,找出相应的位置j,然后将记录插入位置,重复这个插入过程,直到所有未排序部分的记录都插入到有序序列中。
③快速排序(QuickSort):在待排序的记录序列中任取一个记录R(一般取第一个R1),以它为比较“基准”,将待序列划分为左右两个子序列,使得左边子序列中记录的关键字均小于等于记录R
的关键字,右子序列中记录的关键字均大于等于记录R的关键字。对划分的左右两个子序列分别
重复上述过程,直到各个序列的记录个数为1时为止。
④简单选择排序(SimpleSeletctionSort):第一趟从所有的n个记录中,通过顺序比较各记录的关键字的值,选取关键字值最小的记录,与第一个记录交换;第二趟从剩余的n-1个记录中选取关键字值最小的记录,与第二个记录交换;一般地,第i趟从剩余的n-i+1个记录中选取关键字值最小的记录,与第i个记录交换;经过n-1趟后,整个序列就呈递增趋势。
⑤希尔排序(ShellSort):取定一个整数d1(d1<n),把全部的记录分成d1个组,将所有距离为d1的倍数的记录放在一个组中;在各组内进行直接插入排序;取d2<d1, 重复上述分组和排序,直到所取dt(d1〈d1-1 …〈d2〈d1 )等于1。这样就进行了t趟排序。
2. 预编程序
(1)对于冒泡排序(BubbleSort)其预编C程序如下:
#include<>
#define N 5
int TS;
typedef int keytype;
typedef char othertype;
typedef struct yangyi{
keytype key;
othertype otherinfo;
}RecType;
typedef RecType SeqList[N+1];
void BubbleSort(SeqList R,int n);
main()
{int i,length;
SeqList arry;
printf("请输入顺序表长度length=");
scanf("%d",&length);
for(i=1;i<=length;i++)
scanf("%d",&arry[i].key);
BubbleSort (arry,length);
printf("排序结果:");
for(i=1;i<=length;i++)
printf("%d,",arry[i].key);
getch();
}
void BubbleSort(SeqList R,int length) /*功能函数,冒泡排序*/
{int i,j,k;
printf("请输入要输出第几趟结果,不想输出时按任意键,将输出最后结果TS=");
scanf("%d",&TS);
for(i=1;i<length;i++) /*进行了n-1趟排序*/
{for(j=1;j<