数据结构实验报告记录(四)：实现典型的排序算法

数据结构实验报告记录(四)：实现典型的排序算法

———————————————————————————————— 作者： ———————————————————————————————— 日期：

2

佛山科学技术学院 实 验 报 告 课程名称 数据结构 实验项目 实现典型的排序算法 专业班级 10网络工程2 姓 名 张珂卿 学 号 2010394212 指导教师 成 绩 日 期 2011.11.27 一、实验目的 1．掌握排序的基本概念； 2．熟悉排序中使用的存储结构，掌握多种排序算法，如堆排序、希尔排序、快速排序算法等。 二、实验内容 1．几种典型的排序算法； 2．计算不同的排序算法的时间复杂度； 3．判定某种排序算法是否稳定的标准。 三、实验原理 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 四、实验步骤 1．输入记录的基本结点与信息，选用相关的存储结构，完成记录的存储、输入的初始化工作。 2．选择“直接插入排序”，“希尔排序”，“快速排序”，“简单选择排序”和“堆排序”几种排序中的任意三种排序，编程实现排序算法。用菜单形式选择排序方法，并显示排序过程和排序结果。 3．计算排序算法的时间复杂度并进行稳定性分析。 3

五、程序源代码及注释 #include%using namespace std; #define MAX_NO_OF_KEY 8 #define RADIX 10 //关键字基数 #define MAX_SPACE 1000 typedef struct { int keys[MAX_NO_OF_KEY];//关键字 int data;//其他数据项 int next; }SLCell; typedef struct { SLCell r[MAX_SPACE];//静态链表可利用空间 int keynum;//记录的当前关键字个数 int recnum;//静态链表的当前长度 }SLList; typedef int ArrType[RADIX];//指针数组类型 int len;//数组长度 //插入排序 void DirectInsertSort(int Elem_Arr[]) { int i,j; for(i=2;i=1;j--) if(Elem_Arr[0]

for(i=add+1;i0&&Elem_Arr[j]>Elem_Arr[0]; j-=add) Elem_Arr[j+add]=Elem_Arr[j]; Elem_Arr[j+add]=Elem_Arr[0]; } } void ShellSort(int Elem_Arr[]) { int t; cout<<\请输入增量数组元素个数：\ cin>>t; int *dlta=new int[t]; cout<<\请依次输入增量数组元素：\ for(int i=0;i>dlta[i]; for(int k=0;k=pivotkey) --j; Elem_Arr[i]=Elem_Arr[j]; while(i