当前位置：文档之家 › 北邮数据结构实验报告-排序

北邮数据结构实验报告-排序

  • 格式：doc
  • 大小：208.50 KB
  • 文档页数：15

北京邮电大学数据结构试验报告实验名称：实验四排序学生姓名：班级：班内序号：学号：日期：2014年1月4日1 实验目的学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

2 实验内容2.1 题目1使用简单数组实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。

3 程序分析3.1 存储结构顺序存储结构——数组3.2 关键算法分析1.插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕void Insertsort(int r[],int n,int* compare,int* move)//插入排序{*compare=0;*move=0;int i;int j;for(i=1;i<n;i++)//一共要排序n-1次{int x=r[i];for(j=i-1;x<r[j]&&j>=0;j--){(*compare)++;(*move)++;r[j+1]=r[j];}if(j>=0) (*compare)++;r[j+1]=x;}}2.希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序{*compare=0;*move=0;int j;10 9 12 12 20 20 31for(int d=n/2;d>=1;d=d/2)//间距越来越小{for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移{if(r[i]<r[i-d])//某元素比同组中的前一位小，则需要前移{int x=r[i];for(j=i-d;(j>=0)&&(x<r[j]);j=j-d)//完成所需的所有前移{(*compare)++;(*move)++;r[j+d]=r[j];}if(j>=0) (*compare)++;r[j+d]=x;}else (*compare)++;}}}3.冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序{*compare=0;*move=0;int x;for(int j=0;j<n-1;j++)//冒泡排序n-1次{for(int i=n-1;i>j;i--){if(r[i]<r[i-1]){(*compare)++;(*move)+=3;x=r[i];r[i]=r[i-1];r[i-1]=x;}else (*compare)++;}}}4.快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位{int i=first;int j=end;int zhou=r[i];//默认第一个元素为轴while(i<j){while((i<j)&&(r[j]>=zhou)) //查看右侧元素与轴的大小关系{(*compare)++;j--;}if(i<j){(*compare)++;(*move)++;r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置}while((i<j)&&(r[i]<=zhou))//查看左侧元素与轴的大小关系{(*compare)++;i++;}if(i<j){(*compare)++;(*move)++;r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置}}r[i]=zhou;//最后确定轴的位置return i;}void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序{if(i<j){int centre=Partion(r,i,j,compare,move);Qsort(r,i,centre-1,compare,move);Qsort(r,centre+1,j,compare,move);}}5.选择排序：从待排序的记录序列中选择关键码最小的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止void Selectsort(int r[],int n,int* compare,int* move)//选择排序{*compare=0;*move=0;for(int i=0;i<n-1;i++)//排序n-1次{int min=i;for(int j=i+1;j<n;j++)//通过此层循环，找到真正的第i个最小值{(*compare)++;if(r[j]<r[min]) min=j;//记录下当前找到的最小值的位置}if(min!=i){(*move)+=3;int Min;Min=r[min];r[min]=r[i];r[i]=Min;}}}4 程序运行结果4.1主函数流程图4.2程序运行框图5 实验心得1.调试时出现的问题及解决的方法在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。

之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计（算法移动次数和比较次数的精确统计）。

2.心得体会程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。

3.改进本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。

另外还可以进一步考虑算法时间的精确统计，以便从时间角度比较这几种排序算法的优劣。

完整源代码#include<iostream>using namespace std;void Insertsort(int r[],int n,int* compare,int* move);void ShellInsert(int r[],int n,int* compare,int* move);void Bubblesort(int r[],int n,int* compare,int* move);int Partion(int r[],int first,int end,int* compare,int* move);void Qsort(int r[],int i,int j,int* compare,int* move);void Selectsort(int r[],int n,int* compare,int* move);void Insertsort(int r[],int n,int* compare,int* move)//插入排序{*compare=0;*move=0;int i;int j;for(i=1;i<n;i++)//一共要排序n-1次{int x=r[i];for(j=i-1;x<r[j]&&j>=0;j--){(*compare)++;(*move)++;r[j+1]=r[j];}if(j>=0) (*compare)++;r[j+1]=x;}}void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序{*compare=0;*move=0;int j;for(int d=n/2;d>=1;d=d/2)//间距越来越小{for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移{if(r[i]<r[i-d])//某元素比同组中的前一位小，则需要前移{int x=r[i];for(j=i-d;(j>=0)&&(x<r[j]);j=j-d)//完成所需的所有前移{(*compare)++;(*move)++;r[j+d]=r[j];}if(j>=0) (*compare)++;r[j+d]=x;}else (*compare)++;}}}void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序{*compare=0;*move=0;int x;for(int j=0;j<n-1;j++)//冒泡排序n-1次{for(int i=n-1;i>j;i--){if(r[i]<r[i-1]){(*compare)++;(*move)+=3;x=r[i];r[i]=r[i-1];r[i-1]=x;}else (*compare)++;}}int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位{int i=first;int j=end;int zhou=r[i];//默认第一个元素为轴while(i<j){while((i<j)&&(r[j]>=zhou)) //查看右侧元素与轴的大小关系{(*compare)++;j--;}if(i<j){(*compare)++;(*move)++;r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置}while((i<j)&&(r[i]<=zhou))//查看左侧元素与轴的大小关系{(*compare)++;i++;}if(i<j){(*compare)++;(*move)++;r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置}}r[i]=zhou;//最后确定轴的位置return i;}void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序{if(i<j){int centre=Partion(r,i,j,compare,move);Qsort(r,i,centre-1,compare,move);Qsort(r,centre+1,j,compare,move);}void Selectsort(int r[],int n,int* compare,int* move)//选择排序{*compare=0;*move=0;for(int i=0;i<n-1;i++)//排序n-1次{int min=i;for(int j=i+1;j<n;j++)//通过此层循环，找到真正的第i个最小值{(*compare)++;if(r[j]<r[min]) min=j;//记录下当前找到的最小值的位置}if(min!=i){(*move)+=3;int Min;Min=r[min];r[min]=r[i];r[i]=Min;}}}void main(){int i;int compare=0;int move=0;cout<<"请您先输入一个正序数组哦"<<endl;int n;cout<<"请输入数组中含有的元素数量：";cin>>n;int *r=new int[n];cout<<"请输入数组中的元素：";for(i=0;i<n;i++) cin>>r[i];int *a=new int[n];for(i=0;i<n;i++) {a[i]=r[i];}Insertsort(a,n,&compare,&move);cout<<"\n插入排序结果为：";for(i=0;i<n;i++) cout<<a[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl;int *b=new int[n];for(i=0;i<n;i++) {b[i]=r[i];}ShellInsert(b,n,&compare,&move);cout<<"希尔排序结果为：";for(i=0;i<n;i++) cout<<b[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; int *c=new int[n];for(i=0;i<n;i++) {c[i]=r[i];}Bubblesort(c,n,&compare,&move);cout<<"交换排序结果为：";for(i=0;i<n;i++) cout<<c[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; compare=0;move=0;int *d=new int[n];for(i=0;i<n;i++) {d[i]=r[i];}Qsort(d,0,n-1,&compare,&move);cout<<"快速排序结果为：";for(i=0;i<n;i++) cout<<d[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; int *e=new int[n];for(i=0;i<n;i++) {e[i]=r[i];}Selectsort(e,n,&compare,&move);cout<<"选择排序结果为：";for(i=0;i<n;i++) cout<<e[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl;cout<<"再输入一个逆序数组~~~"<<endl; cout<<"请输入数组中含有的元素数量："; cin>>n;cout<<"请输入数组中的元素：";for(i=0;i<n;i++) cin>>r[i];for(i=0;i<n;i++) {a[i]=r[i];}Insertsort(a,n,&compare,&move);cout<<"\n插入排序结果为：";for(i=0;i<n;i++) cout<<a[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; for(i=0;i<n;i++) {b[i]=r[i];}ShellInsert(b,n,&compare,&move);for(i=0;i<n;i++) cout<<b[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; for(i=0;i<n;i++) {c[i]=r[i];}Bubblesort(c,n,&compare,&move);cout<<"交换排序结果为：";for(i=0;i<n;i++) cout<<c[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; compare=0;move=0;for(i=0;i<n;i++) {d[i]=r[i];}Qsort(d,0,n-1,&compare,&move);cout<<"快速排序结果为：";for(i=0;i<n;i++) cout<<d[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; for(i=0;i<n;i++) {e[i]=r[i];}Selectsort(e,n,&compare,&move);cout<<"选择排序结果为：";for(i=0;i<n;i++) cout<<e[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl;cout<<"最后输入一个乱序数组~~~"<<endl; cout<<"请输入数组中含有的元素数量："; cin>>n;cout<<"请输入数组中的元素：";for(i=0;i<n;i++) cin>>r[i];for(i=0;i<n;i++) {a[i]=r[i];}Insertsort(a,n,&compare,&move);cout<<"\n插入排序结果为：";for(i=0;i<n;i++) cout<<a[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; for(i=0;i<n;i++) {b[i]=r[i];}ShellInsert(b,n,&compare,&move);cout<<"希尔排序结果为：";for(i=0;i<n;i++) cout<<b[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; for(i=0;i<n;i++) {c[i]=r[i];}Bubblesort(c,n,&compare,&move);for(i=0;i<n;i++) cout<<c[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; compare=0;move=0;for(i=0;i<n;i++) {d[i]=r[i];}Qsort(d,0,n-1,&compare,&move);cout<<"快速排序结果为：";for(i=0;i<n;i++) cout<<d[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; for(i=0;i<n;i++) {e[i]=r[i];}Selectsort(e,n,&compare,&move);cout<<"选择排序结果为：";for(i=0;i<n;i++) cout<<e[i]<<' ';cout<<"\n比较次数为"<<compare;cout<<"\n移动次数为"<<move<<'\n'<<endl; }。

合集下载

数据结构实验四题目一排序实验报告

数据结构实验四题目一排序实验报告

数据结构实验报告实验名称：实验四——排序学生：XX班级：班序号：学号：日期：1．实验要求实验目的：通过选择实验容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

题目1：使用简单数组实现下面各种排序算法，并进行比较。

排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；4、快速排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）；9、其他。

具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。

5、编写main（）函数测试各种排序算法的正确性。

2. 程序分析2.1 存储结构存储结构：数组2.2 关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素6、堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]<r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]<r[j];j--){r[j+1]=r[j];a++;} r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(int i=d+1;i<=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]<r[i-d]){ r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j>0&&r[0]<r[j];j=j-d) {r[j+d]=r[j]; }⑤循环进行数组拆分：for(int;d>=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较： for(int i=1;i<bound;i++)if(r[i]>r[i+1])②若比下一个元素大，则与其交换： r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0];③后移，重复：for(int i=1;i<bound;i++)④改变总元素值，并重复上述代码：int bound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(i<j&&r[j]>=flag) {j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(i<j&&r[i]<=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素： for(int j=i+1;j<=n;j++)②{if(r[j]<r[index]) index=j; }③若不为当前元素，则交换：if(index!=i) {r[0]=r[i]; r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(int i=1;i<n;i++)6、堆排序关键代码：①生成小顶堆：while(j<=m) {if(j<m&&r[j]>r[j+1]) {j++;}②if(r[i]<r[j]) {break; }③else{ int x; x=r[i]; r[i]=r[j]; r[j]=x; i=j; j=2*i; }}④将堆的根节点移至数组的最后： x=r[1]; r[1]=r[n-i+1]; r[n-i+1]=x;⑤去掉已做过根节点的元素继续生成小顶堆：sift(r,1,n-i,x,y);⑥数组倒置输出: for(int i=n;i>0;i--)cout<<r[i]<<" ";7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位： mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i<=m&&j<=high)if(L.r[i]<=L.r[j]) t[k++]=L.r[i++];else t[k++]=L.r[j++];while(i<=m) t[k++]=L.r[i++];while(j<=high) t[k++]=L.r[j++];for(i=low,k=0;i<=high;i++,k++) L.r[i]=t[k];三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3. 程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下：2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。

数据结构实验报告-排序

数据结构实验报告-排序

数据结构实验报告-排序一、实验目的本实验旨在探究不同的排序算法在处理大数据量时的效率和性能表现，并对比它们的优缺点。

二、实验内容本次实验共选择了三种常见的排序算法：冒泡排序、快速排序和归并排序。

三个算法将在同一组随机生成的数据集上进行排序，并记录其性能指标，包括排序时间和所占用的内存空间。

三、实验步骤1. 数据的生成在实验开始前，首先生成一组随机数据作为排序的输入。

定义一个具有大数据量的数组，并随机生成一组在指定范围内的整数，用于后续排序算法的比较。

2. 冒泡排序冒泡排序是一种简单直观的排序算法。

其基本思想是从待排序的数据序列中逐个比较相邻元素的大小，并依次交换，从而将最大（或最小）的元素冒泡到序列的末尾。

重复该过程直到所有数据排序完成。

3. 快速排序快速排序是一种分治策略的排序算法，效率较高。

它将待排序的序列划分成两个子序列，其中一个子序列的所有元素都小于等于另一个子序列的所有元素。

然后对两个子序列分别递归地进行快速排序。

4. 归并排序归并排序是一种稳定的排序算法，使用分治策略将序列拆分成较小的子序列，然后递归地对子序列进行排序，最后再将子序列合并成有序的输出序列。

归并排序相对于其他算法的优势在于其稳定性和对大数据量的高效处理。

四、实验结果经过多次实验，我们得到了以下结果：1. 冒泡排序在数据量较小时，冒泡排序表现良好，但随着数据规模的增大，其性能明显下降。

排序时间随数据量的增长呈平方级别增加。

2. 快速排序相比冒泡排序，快速排序在大数据量下的表现更佳。

它的排序时间线性增长，且具有较低的内存占用。

3. 归并排序归并排序在各种数据规模下都有较好的表现。

它的排序时间与数据量呈对数级别增长，且对内存的使用相对较高。

五、实验分析根据实验结果，我们可以得出以下结论：1. 冒泡排序适用于数据较小的排序任务，但面对大数据量时表现较差，不推荐用于处理大规模数据。

2. 快速排序是一种高效的排序算法，适用于各种数据规模。

数据结构排序实践报告(2篇)

数据结构排序实践报告(2篇)

第1篇一、引言随着计算机技术的飞速发展，数据结构在计算机科学中扮演着越来越重要的角色。

排序算法作为数据结构的重要组成部分，对于提高数据处理的效率具有重要意义。

本报告旨在通过实践，探讨几种常见的排序算法，分析其优缺点，并验证其在实际应用中的性能。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 数据集：随机生成的10000个整数，范围在0到10000之间三、实验内容本次实验主要针对以下几种排序算法进行实践：1. 冒泡排序2. 选择排序3. 插入排序4. 快速排序5. 归并排序四、实验步骤1. 定义排序算法（1）冒泡排序```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j] return arr```（2）选择排序```pythondef selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i] return arr```（3）插入排序```pythondef insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i-1while j >=0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr```（4）快速排序```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right) ```（5）归并排序```pythondef merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result```2. 生成随机数据集```pythonimport randomdata = [random.randint(0, 10000) for _ in range(10000)] ```3. 测试排序算法```pythondef test_sort(sort_func):start_time = time.time()sorted_data = sort_func(data.copy())end_time = time.time()print(f"{sort_func.__name__} took {end_time - start_time:.6f} seconds")return sorted_datasorted_data_bubble = test_sort(bubble_sort)sorted_data_selection = test_sort(selection_sort)sorted_data_insertion = test_sort(insertion_sort)sorted_data_quick = test_sort(quick_sort)sorted_data_merge = test_sort(merge_sort)```五、实验结果与分析1. 冒泡排序冒泡排序是一种简单的排序算法，其时间复杂度为O(n^2)。

北邮数据结构实验四-链表排序

北邮数据结构实验四-链表排序

数据结构实验报告实验名称：实验四——链表的排序学生姓名：班级：班内序号：学号：日期：1．实验要求[内容要求]使用链表实现下面各种排序算法，并进行比较。

排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性代码要求1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2. 程序分析2.1 存储结构[内容要求]存储结构：双链表2.2 关键算法分析[内容要求]定义类：template <class T>class LinkList{public:LinkList(){front = new Node <T>;front->next=rear;front->prior=NULL;rear=newNode<T>;rear->next=NULL;rear->prior=front;}LinkList(T a[],int n);void BackLinkList(T a[]);//恢复原链表~LinkList();//析构函数void PrintList();//打印数列void InsertSort();//插入排序void BubbleSort();//冒泡排序Node <T>* Partion(Node <T> *i,Node <T> *j);//快速排序中寻找轴值的函数void Qsort(Node <T> *i,Node <T> *j);//快速排序void SelectSort();//选择排序Node<T>*front;Node<T>*rear;};成员函数包括：构造函数：单链表，打印单链表，插入排序，快速排序，冒泡排序，选择排序，析构函数公有成员：头指针和尾指针1、构造函数：LinkList<T>::LinkList(T a[],int n){front=new Node<T>;rear=new Node<T>;front->prior=NULL;front->next=rear;rear->next=NULL;rear->prior=front;Node <T>*s;for (int i=n-1;i>=0;i--){s=new Node<T>;s->data=a[i];s->next=front->next;front->next=s;s->prior=front;s->next->prior=s;}}2、析构函数LinkList<T>::~LinkList(){Node<T> *p=front->next;while(p->next!=NULL){delete p->prior;p=p->next;}delete rear;front=NULL;rear=NULL;}3、打印函数template <class T>void LinkList<T>::PrintList(){Node<T> *p=front->next;while(p->next!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;}4、插入排序template <class T>void LinkList<T>::InsertSort(){Node<T> *p=front->next->next;Node<T> *q;T temp;while (p->next!=NULL){if (p->data<p->prior->data){temp=p->data;MoveCount++;q=p->prior;while (temp<q->data){q->next->data=q->data;q=q->prior;CompareCount++;MoveCount++;}q->next->data=temp;MoveCount++;}CompareCount++;p=p->next;}}将链表分为有序区和无序区，分别将无序区的每一个元素插入到有序区的相应位置。