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

《数据结构实验报告(四)：实现典型的排序算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、佛山科学技术学院实验报告课程名称数据结构实验项目实现典型的排序算法专业班级10网络工程2姓名张珂卿学号指导教师成绩日期2011.11.27一、实验目的1．掌握排序的基本概念；2．熟悉排序中使用的存储结构，掌握多种排序算法，如堆排序、希尔排序、快速排序算法等。二、实验内容1．几种典型的排序算法；2．计算不同的排序算法的时间复杂度；3．判定某种排序算法是否稳定的标准。三、实验原理排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部

2、排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。四、实验步骤1．输入记录的基本结点与信息，选用相关的存储结构，完成记录的存储、输入的初始化工作。2．选择“直接插入排序”，“希尔排序”，“快速排序”，“简单选择排序”和“堆排序”几种排序中的任意三种排序，编程实现排序算法。用菜单形式选择排序方法，并显示排序过程和排序结果。3．计算排序算法的时间复杂度并进行稳定性分析。五、程序源代码及注释#include"iostream"usingnames

3、pacestd;#defineMAX_NO_OF_KEY8#defineRADIX10//关键字基数#defineMAX_SPACE1000typedefstruct{intkeys[MAX_NO_OF_KEY];//关键字intdata;//其他数据项intnext;}SLCell;typedefstruct{SLCellr[MAX_SPACE];//静态链表可利用空间intkeynum;//记录的当前关键字个数intrecnum;//静态链表的当前长度}SLList;typedefintArrType[RADIX];//指针数组类型intle

4、n;//数组长度//插入排序voidDirectInsertSort(intElem_Arr[]){inti,j;for(i=2;i=1;j--)if(Elem_Arr[0]

5、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];}}voidShellSort(intElem_Arr[]){intt;cout<<"请输入增量数组元素个数："<>t;int*dlta=newint[t];cout<<"请依次输入增量数组元素："<

6、0;i>dlta[i];for(intk=0;k=pivotkey)--j;Elem_Arr[i]=Elem_Arr[j];while(i

7、em_Arr[i]<=pivotkey)++i;Elem_Arr[j]=Elem_Arr[i];}Elem_Arr[i]=pivotkey;returni;}//PartitionvoidQSort(intElem_Arr[],intlow,inthigh){intpivotloc;if(low

8、lem_Arr[]){QSort(Elem_Arr,1,len-1);}//简单选择排序intSelectMin(intElem_Arr