数据结构-实验六.doc
文本预览下载声明
实验六 排序
一、实验目的
1、掌握内部排序的基本算法；
2、分析比较内部排序算法的效率。
二、实验预习
说明以下概念
简单排序：将一组记录按某关键字递增或递减的顺序排序。
希尔排序：又称“缩小增量排序”属于插入排序类的方法。
快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
4、堆排序：只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
三、实验内容和要求
1、编程实现直接插入排序算法。
程序代码：
#includestdio.h
#includestdlib.h
#define ERROR 0
#define OK 1
#define LT(a,b) ((a)(b))
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType r[MAXSIZE+1];
int length;
}Sqlist;
int InitList_Sq(Sqlist L){
int i=1;
//printf(请输入待排序的记录的个数：);
//scanf(%d,L.length);
printf(请输入待排序的记录的关键字（整型数）：);
while(scanf(%d,L.r[i]))
{i++ ; }
L.length=i-1;
return OK;
}/*InitList*/
void Print_Sq(Sqlist L) /*输出顺序表*/
{ int i;
for(i=1;i=L.length;i++)
printf( %d,L.r[i]);
}
void InsertSort(Sqlist L){
int i,j;
for(i=2;i=L.length;++i)
if(LT(L.r[i],L.r[i-1]))//“”，需将L.r[i]插入有序子表
{
L.r[0]=L.r[i];//复制为哨兵
L.r[i]=L.r[i-1];
for(j=i-2;LT(L.r[0],L.r[j]);--j)
L.r[j+1]=L.r[j];//记录后移
L.r[j+1]=L.r[0];//插入到正确位置
}
}
void main()
{
Sqlist S;
InitList_Sq(S);
Print_Sq(S);
printf( \n1.简单插入排序\n);
InsertSort(S);
Print_Sq(S);
/*printf( 3.快速排序\n);
QuickSort(S);
Print_Sq(S);
printf( 5.堆排序\n);
HeapSort(S);
Print_Sq(S);*/
}
2、输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束）
1）直接插入排序运行结果（写出每一趟的状态）：
38 49 65 97 13 27 49
13 38 49 65 97 27 49
13 27 38 49 65 97 49
13 27 38 49 49 65 97
2）堆排序运行结果（写出每一趟的状态）：
3、编程实现快速排序算法。
程序代码：
#includestdio.h
#includestdlib.h
#define ERROR 0
#define OK 1
#define LT(a,b) ((a)(b))
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType r[MAXSIZE+1];
int length;
}Sqlist;
int InitList_Sq(Sqlist L)
{
int i=1;
//printf(请输入待排序的记录的个数：);
//scanf(%d,L.length);
printf(请输入待排序的记录的关键字（整型数）：);
while(scanf(%d,L.r[i]))
{i++ ; }
L.length=i-1;
return OK;
}/*InitList*/
void Print_Sq(Sqlist L) /*输出顺序表*/
{ int i;
for(i=1;i=L.length;i++)
printf( %d,L.r[i]);
}
void InsertSort(Sqlist L){
int i,j;
for(i=2;i=L.length;++i)
if(LT(L.r[i],L.r[i-1]))//“”，需将L.r[i]插入有序子表
{ L.r
显示全部