北邮数据结构实验报告排序_北邮数据结构实验报告
北邮数据结构实验报告排序由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“北邮数据结构实验报告”。
北京邮电大学 数据结构试验报告
实验名称： 实验四
排序 学生姓名：
班
级：
班内序号：
学
号：
日
期： 2014年1月4日
实验目的学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容
2.1 题目1 使用简单数组实现下面各种排序算法，并进行比较。排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。程序分析
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=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 31 for(int d=n/2;d>=1;d=d/2)//间距越来越小 { for(int i=d;i
{
int x=r[i];
for(j=i-d;(j>=0)&&(x
{
(*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
for(int i=n-1;i>j;i--)
{
if(r[i]
{
(*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=zhou))//查看右侧元素与轴的大小关系
{
(*compare)++;
j--;} if(i
r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置
} while((i
(*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
int min=i;
for(int j=i+1;j
{
(*compare)++;
if(r[j]
min=j;//记录下当前找到的最小值的位置
}
if(min!=i)
{(*move)+=3;
int Min;
Min=r[min];
r[min]=r[i];
r[i]=Min;
}
} }程序运行结果
4.1主函数流程图
4.2程序运行框图实验心得
1.调试时出现的问题及解决的方法
在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。
之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计（算法移动次数和比较次数的精确统计）。2.心得体会
程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。3.改进
本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。另外还可以进一步考虑算法时间的精确统计，以便从时间角度比较这几种排序算法的优劣。
完整源代码
#include 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;
{
} }
void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 { int x=r[i];for(j=i-1;x=0;j--){
} if(j>=0)(*compare)++;r[j+1]=x;(*move)++;r[j+1]=r[j];*move=0;int i;int j;for(i=1;i
(*compare)++;
*compare=0;
{ for(int i=d;i
} } }
void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 {
{
for(int i=n-1;i>j;i--)
{
if(r[i]
{
(*compare)++;
(*move)+=3;*compare=0;*move=0;int x;if(r[i]
int x=r[i];
for(j=i-d;(j>=0)&&(x
}(*compare)++;(*compare)++;(*move)++;r[j+d]=r[j];*move=0;int j;for(int d=n/2;d>=1;d=d/2)//间距越来越小
if(j>=0)
r[j+d]=x;} else(*compare)++;for(int j=0;j
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
{ }
if(i=zhou))//查看右侧元素与轴的大小关系 {
} if(i
r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置
(*move)++;
r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置
} } r[i]=zhou;//最后确定轴的位置 return i;}
void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i
void Selectsort(int r[],int n,int* compare,int* move)//选择排序 {
{
int min=i;
for(int j=i+1;j
{
(*compare)++;
if(r[j]
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>n;int *r=new int[n];cout>r[i];int *a=new int[n];for(i=0;i
cout>n;cout>r[i];for(i=0;i
cout>n;cout>r[i];for(i=0;i
