佛山科学技术学院实 验 报 告课程名称 数据结构 实验项目 实现典型的排序算法 专业班级 10网络工程2 姓 名 张珂卿 学 号 指导教师 成 绩 日 期 2023.11.27 一、 实验目的 1．掌握排序的基本概念；2．熟悉排序中使用的存储结构，掌握多种排序算法，如堆排序、希尔排序、快速排序算法等二、实验内容1．几种典型的排序算法；2．计算不同的排序算法的时间复杂度；3．鉴定某种排序算法是否稳定的标准三、实验原理排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列分内部排序和外部排序若整个排序过程不需要访问外存便能完毕，则称此类排序问题为内部排序反之，若参与排序的记录数量很大，整个序列的排序过程不也许在内存中完毕，则称此类排序问题为外部排序内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
四、实验环节 1．输入记录的基本结点与信息，选用相关的存储结构，完毕记录的存储、输入的初始化工作2．选择“直接插入排序”，“希尔排序”，“快速排序”，“简朴选择排序”和“堆排序”几种排序中的任意三种排序，编程实现排序算法用菜单形式选择排序方法，并显示排序过程和排序结果3．计算排序算法的时间复杂度并进行稳定性分析五、 程序源代码及注释#include"iostream"using namespace std;#define MAX_NO_OF_KEY 8#define RADIX 10 //关键字基数#define MAX_SPACE 1000typedef 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]0&&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<<"请输入增量数组元素个数："<>t; int *dlta=new int[t]; cout<<"请依次输入增量数组元素："<>dlta[i]; for(int k=0;k=pivotkey) --j; Elem_Arr[i]=Elem_Arr[j]; while(iElem_Arr[j]) min=j; return min;}void SelectSort(int Elem_Arr[]){ int t,j; for(int i=1;iElem_Arr[j]) break; Elem_Arr[i]=Elem_Arr[j]; i=j; } Elem_Arr[i]=Elem_Arr[0];}void HeapSort(int Elem_Arr[]){ for(int i=(len-1)/2;i>0;--i) HeapAdjust(Elem_Arr,i,len-1); for(i=len-1;i>1;--i) { Elem_Arr[0]=Elem_Arr[i]; Elem_Arr[i]=Elem_Arr[1]; Elem_Arr[1]=Elem_Arr[0]; HeapAdjust(Elem_Arr,1,i-1); }}//归并排序void Merge(int Elem_Arr1[],int Elem_Arr[],int i,int m,int n) //将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]{ int j,k; for(j=m+1,k=i;i<=m&&j<=n;++k) { //将SR中记录由小到大地并入TR if(Elem_Arr1[i]
{ int *Elem_Arr1=new int [len]; for(int i=0;i>L.r[i].data; L.r[i].keys[0]=L.r[i].data%10; L.r[i].keys[1]=(L.r[i].data%100-L.r[i].keys[0])/10; L.r[i].keys[2]=L.r[i].data/100; }} void Distribute(SLList &L,int i,ArrType &f,ArrType &e){ // 算法10.15 // 静态链表L的r域中记录已按(keys[0],...,keys[i-1])有序， // 本算法按第i个关键字keys[i]建立RADIX个子表， // 使同一子表中记录的keys[i]相同。
f[0..RADIX-1]和e[0..RADIX-1] // 分别指向各子表中第一个和最后一个记录 int j,p; for(j=0;j
对L作基数排序，使得L成为按关键字自小到大的有序静态链表，L.r[0]为头结点 int i; ArrType f,e; L.keynum=3; cout<<"请输入所需排序元素个数(当前记录关键字个数<=3)："<>L.recnum; CreateL(L); for(i=1;i<=L.recnum;++i) L.r[i-1].next=i; L.r[L.recnum].next=0; // 将L改造为静态链表 for(i=0;i>Elem_Arr[i];}void ShowElem_Arr(int Elem_Arr[]){ for(int i=1;i>a; if(a==1) { int NO; cout<<"请输入需要排序元素个数："<>NO; len=NO+1; Elem_Arr=new int [len]; CreatElem_Arr(Elem_Arr); DirectInsertSort(Elem_Arr); cout<<"直接排序结果为："<>NO; len=NO+1; Elem_Arr=new int [len]; CreatElem_Arr(Elem_Arr); ShellSort(Elem_Arr); cout<<"希尔排序结果为："<>NO; len=NO+1; Elem_Arr=new int [len]; CreatElem_Arr(Elem_Arr); QuickSort(Elem_Arr); cout<<"快速排序结果为："<>NO; len=NO+1; Elem_Arr=new int [len]; CreatElem_Arr(Elem_Arr); SelectSort(Elem_Arr); cout<<"简朴选择排序结果为："<>NO; len=NO+1; Elem_Arr=new int [len]; CreatElem_Arr(Elem_Arr); HeapSort(Elem_Arr); cout<<"堆排序结果为："<>NO; len=NO+1; Elem_Arr=new int [len]; CreatElem_Arr(Elem_Arr); MergeSort(Elem_Arr); cout<<"归并排序结果为："<>c; if(c==1) operate(Elem_Arr);}void main(){ int *Elem_Arr; operate(Elem_Arr);}程序结果截图:六、实验结果分析及实验体会通过这次数据结构我感觉自己收获还是挺多的，这次实验课做的课题是实现典型的排序算法，我最大的收获是感受到了计算机的真正运营原理，用这些代码来代替人为地工作，很久以前我觉得这是不可思议的事情，但是我今天居然也做到了。
这次数据结构实验课，激发了我对学习的积极性，从程序编写，整理资料到完整运营，最后做调试的过程中，感觉到自己所学习的专业课也并不是那么枯燥乏味，并且明白了之前学不太好的因素，这门课的确需要以后不断的思考和实践，才可以逐渐提高自己专业课汲取知识的能力。