北邮数据结构实验报告.docx

资源描述

北邮数据结构实验报告.docx

《北邮数据结构实验报告.docx》由会员分享，可在线阅读，更多相关《北邮数据结构实验报告.docx（28页珍藏版）》请在冰点文库上搜索。

北邮数据结构实验报告.docx

北邮数据结构实验报告

数据结构实验报告

实验名称：

实验4-1

姓名：

班级：

班内序号：

学号：

日期：

1实验目的

通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

2实验内容

2.1题目1

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

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：

正序、逆序、随机数据

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

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

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

编写测试main（）函数测试线性表的正确性。

2.程序分析

2.1存储结构

使用最简单的一维数组存储待排序的数据。

共使用两个数组，一个用来存储原始数据，一个用来存储待排序数据。

每次排序完毕，用原始数据更新一次待排序数据，保证每一次都对同一组数据排序。

下面举几个例子

1直接插入排序

2快速排序

3简单选择排序

2.2关键算法分析

1、插入排序：

依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。

voidInsertSort（intr[],intn）

{intj;

for（inti=2;i

{

r[0]=r[i];//设置哨兵

Ma++;

for（j=i-1;（++Cp）&&r[0]

{r[j+1]=r[j];//记录后移

Ma++;

}

r[j+1]=r[0];

Ma++;

}

2、希尔排序：

先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。

voidShellSort（intr[],intn）

{

inti;

intd;

intj;

for（d=n/2;d>=1;d=d/2）//以增量为d进行直接插入排序

{

for（i=d+1;i

{

r[0]=r[i];//暂存被插入记录

Ma++;

for（j=i-d;j>0&&r[0]

{r[j+d]=r[j];

Ma++;}//记录后移d个位置

r[j+d]=r[0];

Ma++;

}

3、冒泡排序：

两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。

voidBubbleSort（intr[],intn）

{

inttemp;

intexchange;

intbound;

exchange=n-1;//第一趟起泡排序的范围是r[0]到r[n-1]

while（exchange）//仅当上一趟排序有记录交换才进行本趟排序

{

bound=exchange;

exchange=0;

for（intj=0;j

if（（++Cp）&&r[j]>r[j+1]）

{

temp=r[j];

r[j]=r[j+1];

r[j+1]=temp;

Ma++;

exchange=j;//记录每一次发生记录交换的位置

}

4、快速排序：

首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。

intPartition（intr[],intfirst,intend）

{

inti=first;//初始化

intj=end;

inttemp;

while（i

{

while（i

j--;//右侧扫描

if（i

{

temp=r[i];//将较小记录交换到前面

r[i]=r[j];

r[j]=temp;

Ma++;

i++;

}

while（i

i++;//左侧扫描

if（i

{

temp=r[j];

r[j]=r[i];

r[i]=temp;//将较大记录交换到后面

Ma++;

j--;

}

returni;//i为轴值记录的最终位置

}

voidQuickSort（intr[],intfirst,intend）

{

if（first

{//递归结束

intpivot=Partition（r,first,end）;//一次划分

QuickSort（r,first,pivot-1）;//递归地对左侧子序列进行快速排序

QuickSort（r,pivot+1,end）;//递归地对右侧子序列进行快速排序

}

5、选择排序：

从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。

voidSelectSort（intr[],intn）

{

inti;

intj;

intindex;

inttemp;

for（i=0;i

{

index=i;

for（j=i+1;j

if（（++Cp）&&r[j]

index=j;

if（index!

=i）

{

temp=r[i];

r[i]=r[index];

r[index]=temp;

Ma++;

}

6、堆排序：

通过建立大根堆或者小根堆，取出根节点，反复调整堆使之保持大根堆或者小根堆，直至最后序列有序。

voidSift（intr[],intk,intm）//筛选法调整堆

{

inti;

intj;

inttemp;

i=k;

j=2*i+1;

while（j<=m）

{

if（j

{

j++;

Cp++;

}

Cp++;

if（r[i]>r[j]）

{

Cp++;

break;

}

else

{

Cp++;

temp=r[i];

r[i]=r[j];

r[j]=temp;

i=j;

j=2*i+1;

Ma+=3;

}

voidHeapSort（intr[],intn）//堆排序

{

inti;

inttemp;

for（i=n/2;i>=0;i--）

Sift（r,i,n）;

for（i=n-1;i>0;i--）

{

temp=r[i];

r[i]=r[0];

r[0]=temp;

Ma+=3;

Sift（r,0,i-1）;

}

7、归并排序：

将若干个有序序列两两归并，直至所有待排序的记录都在一个有序序列为止。

voidMerge（intr[],intr1[],ints,intm,intt）//归并两相邻序列

{

inti=s;

intj=m+1;

intk=s;

while（i<=m&&j<=t）

{

if（r[i]

{

r1[k++]=r[i++];

Cp++;

Ma++;

}

else

{

r1[k++]=r[j++];

Cp++;

Ma++;

}

if（i<=m）

while（i<=m）

{

r1[k++]=r[i++];

Ma++;

}

if（j<=t）

while（j<=t）

{

r1[k++]=r[j++];

Ma++;

}

voidMergeSort（intr[],intr1[],ints,intt）//二路归并排序

{

intr2[MAXSIZE];

if（s==t）

{

r1[s]=r[s];

Ma++;

}

else

{

intm=（s+t）/2;

MergeSort（r,r2,s,m）;

MergeSort（r,r2,m+1,t）;

Merge（r2,r1,s,m,t）;

}

3.程序运行结果

主函数流程：

4.总结

本次实验中遇到的问题主要还是对循环条件的控制，比如说有r[0]和没有r[0]是函数的参数就会相应变化。

在输出的过程中有几个我就没有把数据输出完全。

还有就是算法的理解。

真正编写程序是比较简单的，难就难在排序的理解上，比如说堆排序，它的每一步的实际操作都是很复杂的。

需要理解清楚。

还有就是不同的排序方法，有不同的用处。

在处理排序问题时要注意程序的时间复杂度和空间复杂度，在本实验中，Cp为比较次数，来表征程序的时间性能;Ma表示移动次数，来表征程序所占用的附加空间。

一个程序的好坏取决于一个程序的时间复杂度和空间复杂度。

#include

usingnamespacestd;

intMa=0;

intCp=0;

constintMAXSIZE=10000;

voidInsertSort（intr[],intn）;//直接顺序排序

voidShellSort（intr[],intn）;//希尔排序

voidBubbleSort（intr[],intn）;//起泡排序

intPartition（intr[],intfirst,intend）;//快速排序一次划分

voidQuickSort（intr[],intfirst,intend）;//快速排序

voidSelectSort（intr[],intn）;//简单选择排序

voidSift（intr[],intk,intm）;//筛选法调整堆

voidHeapSort（intr[],intn）;//堆排序

voidMerge（intr[],intr1[],ints,intm,intt）;//归并两相邻序列

voidMergeSort（intr[],intr1[],ints,intt）;//二路归并排序

intmain（）

{

intn;

cout<<"输入数组的长度:

cin>>n;

int*num;//用指针指向一个数组

num=newint[n];//动态内存分配

cout<<"输入数组的数据:

for（inti=0;i

{cin>>num[i];}

int*a;

a=newint[n+1];

a[0]=0;

for（inti=0;i

{a[i+1]=num[i];}

int*b;

b=newint[n+1];

b[0]=0;

for（inti=0;i

{b[i+1]=num[i];}

int*c;

c=newint[n];

for（inti=0;i

{c[i]=num[i];}

int*d;

d=newint[n];

for（inti=0;i

{d[i]=num[i];}

int*e;

e=newint[n];

for（inti=0;i

{e[i]=num[i];}

int*f;

f=newint[n];

for（inti=0;i

{f[i]=num[i];}

int*g;

g=newint[n];

for（inti=0;i

{g[i]=num[i];}

cout<<"\n排序前：

"<<"\n";

for（inty=0;y

cout<

cout<<"\n直接顺序排序结果为：

"<<"\n";

InsertSort（a,n+1）;

for（intk=1;k<=n;k++）

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<<"\n希尔排序结果为：

"<<"\n";

ShellSort（b,n+1）;

for（inti=1;i<=n;i++）

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<<"\n起泡排序结果为：

"<<"\n";

BubbleSort（c,n）;

for（inti=0;i

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<<"\n快速排序结果为：

"<<"\n";

QuickSort（d,0,n-1）;

for（inti=0;i

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<<"\n简单选择排序结果为：

"<<"\n";

SelectSort（e,n）;

for（inti=0;i

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<<"\n堆排序结果为：

\n";

HeapSort（f,n）;//堆排序

for（inti=0;i

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<<"\n二路归并排序结果为：

\n";

MergeSort（g,g,0,n-1）;//二路归并排序

for（inti=0;i

cout<

cout<<"\n移动次数为：

Ma=0;

Cp=0;

cout<

_LARGE_INTEGERtime_start;

_LARGE_INTEGERtime_over;

doubledqFreq;

LARGE_INTEGERh;

QueryPerformanceFrequency（&h）;

dqFreq=（double）h.QuadPart;