北京邮电大学数据结构实验第三次实验排序.docx

北京邮电大学数据结构实验第三次实验排序.docx

《北京邮电大学数据结构实验第三次实验排序.docx》由会员分享，可在线阅读，更多相关《北京邮电大学数据结构实验第三次实验排序.docx（17页珍藏版）》请在冰点文库上搜索。

北京邮电大学数据结构实验第三次实验排序

数据结构试验报告

实验名称：

实验四排序

学生姓名：

班级：

班内序号：

学号：

日期：

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存储结构

顺序存储结构——数组

A0

A1

A2

A3

A4

A5

A6

3.2关键算法分析

1.插入排序：

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

voidInsertsort（intr[],intn,int*compare,int*move）//插入排序

{

*compare=0;

*move=0;

inti;

intj;

for（i=1;i

{intx=r[i];

for（j=i-1;x=0;j--）

{

（*compare）++;

（*move）++;

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

}

if（j>=0）

（*compare）++;

r[j+1]=x;

}

}

2.希尔排序：

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

voidShellInsert（intr[],intn,int*compare,int*move）//希尔排序

{

*compare=0;

*move=0;

intj;

for（intd=n/2;d>=1;d=d/2）//间距越来越小

{

for（inti=d;i<=n-1;i++）//从a[d]往后逐个元素确定是否需要前移{if（r[i]

{intx=r[i];

for（j=i-d;（j>=0）&&（x

（*move）++;

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

}

if（j>=0）

（*compare）++;

r[j+d]=x;

}

else（*compare）++;

}

}

}

3.冒泡排序：

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

voidBubblesort（intr[],intn,int*compare,int*move）//交换（冒泡）排序{*compare=0;

*move=0;

intx;

for（intj=0;j

{

for（inti=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.快速排序：

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

intPartion（intr[],intfirst,intend,int*compare,int*move）//快速排序中的轴定位

{inti=first;

intj=end;

intzhou=r[i];//默认第一个元素为轴

while（i

{

while（（i=zhou））//查看右侧元素与轴的大小关系

{

（*compare）++;

j--;

}

if（i

{（*compare）++;

（*move）++;

r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置

}while（（i

if（i

{（*compare）++;

（*move）++;

r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置

}

}

r[i]=zhou;//最后确定轴的位置returni;

}

voidQsort（intr[],inti,intj,int*compare,int*move）//快速排序

{if（i

{intcentre=Partion（r,i,j,compare,move）;

Qsort（r,i,centre-1,compare,move）;

Qsort（r,centre+1,j,compare,move）;

}

}

5.选择排序：

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

voidSelectsort（intr[],intn,int*compare,int*move）//选择排序

{*compare=0;

*move=0;

for（inti=0;i

{

Intmin=i;

for（intj=i+1;j

{（*compare）++;

if（r[j]

min=j;//记录下当前找到的最小值的位置

}

if（min!

=i）

{

（*move）+=3;

intMin;

Min=r[min];

r[min]=r[i];

r[i]=Min;

}

}

}

时间复杂度，空间复杂度

排序方法

平均情况

最好情况

最坏情况

辅助空间

直接插入排序

O（n²）

O（n）

O（n²）

O

（1）

希尔排序

O（nlog2n）~O（n）

O（n的1.3次幂）

O（n²）

O

（1）

起泡排序

O（n²）

O（n）

O（n²）

O

（1）

快速排序

O（nlog2n）

O（nlog2n）

O（n²）

O（log2n）~O（n）

简单选择排序

O（n²）

O（n²）

O（n²）

O

（1）

原始代码：

#include

usingnamespacestd;

voidInsertSort（intr[],intn）

{

intnum1=0;

intnum2=0;

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

{

if（r[i]

{

r[0]=r[i];

r[i]=r[i-1];

for（intj=i-1;r[0]

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

num2=num2+3;

}

num1++;

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

}

}

cout<<"直接插入排序后的数组为：

";

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

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

}

voidShellSort（intr[],intn）

{

intnum1=0;

intnum2=0;

for（intd=n/2;d>=1;d=d/2）

{

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

{

if（r[i]

{

r[0]=r[i];

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

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

num2=num2+3;

}

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

}

}

num1++;

}

cout<<"希尔排序后的数组为：

";

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

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

}

voidBubbleSort（intr[],intn）

{

intpos=n;

intnum1=0;

intnum2=0;

while（pos!

=0）

{

intbound=pos;

pos=0;

for（inti=1;i

{

if（r[i]>r[i+1]）

{

r[0]=r[i];

r[i]=r[i+1];

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

pos=i+1;

num2+=3;

}num1++;

}

}

cout<<"冒泡排序后的数组为：

";

for（intk=1;k

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

}

intPartion（intr[],intfirst,intend,int&num1,int&num2）

{

inti=first;

intj=end;

intpivot=r[i];

while（i

{

while（（i=pivot））

{

j--;

num1++;

}

r[i]=r[j];

if（i!

=j）

num2=num2+3;

while（（i

i++;

r[j]=r[i];

if（i!

=j）

num2=num2+3;

}

r[i]=pivot;

returni;

}

voidQsort（intr[],inti,intj,int&num1,int&num2）

{

if（i

{

intpivotloc=Partion（r,i,j,num1,num2）;

Qsort（r,i,pivotloc-1,num1,num2）;

Qsort（r,pivotloc+1,j,num1,num2）;

}

}

voidSelectSort（intr[],intn）

{

intnum1=0,num2=0;

for（inti=1;i

{

intindex=i;

for（intj=i+1;j<=n-1;j++,num1++）

if（r[j]

index=j;

if（index!

=i）

{

num2=num2+3;

r[0]=r[i];

r[i]=r[index];

r[index]=r[0];

}

}

cout<<"简单选择排序后的数组为：

";

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

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

}

voidRand（inta[],intr）

{

for（into=1;o<=10;o++）

{

a[o]=rand（）;

}

}

voidmain（）

{

cout<<"正反序排序结果为：

"<

intr[10]={0,1,3,5,7,9,11,13,15,17};

InsertSort（r,10）;

intR[10]={0,17,15,13,11,9,7,5,3,1};

InsertSort（R,10）;

inta[10]={0,2,4,6,8,10,12,14,16,18};

BubbleSort（a,10）;

intA[10]={0,18,16,14,12,10,8,6,4,2};

BubbleSort（A,10）;

intb[10]={0,3,6,9,12,15,18,21,24,27};

ShellSort（b,10）;

intB[10]={0,27,24,21,18,15,12,9,6,3};

ShellSort（B,10）;

intc[10]={0,1,2,3,4,5,6,7,8,9};

intnum1=0;

intnum2=0;

Qsort（c,1,10,num1,num2）;

cout<<"快速排序后的数组为：

";

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

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

intC[10]={0,9,8,7,6,5,4,3,2,1};

Qsort（C,1,10,num1,num2）;

cout<<"快速排序后的数组为：

";

for（intq=1;q<=9;q++）

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

intd[10]={0,1,3,8,99,444,456,568,888,997};

SelectSort（d,10）;

intD[10]={0,997,888,568,456,444,99,8,3,1};

SelectSort（D,10）;

intn[10]={0,0,0,0,0,0,0,0,0,0};

cout<<"随机数组排序结果：

"<

Rand（n,10）;

InsertSort（n,10）;

Rand（n,10）;

BubbleSort（n,10）;

Rand（n,10）;

ShellSort（n,10）;

Rand（n,10）;

Qsort（n,1,10,num1,num2）;

cout<<"快速排序后的数组为：

";

for（intK=1;K<=9;K++）

cout<

cout<

cout<<"比较次数为：

"<

cout<<"移动次数为：

"<

Rand（n,10）;

SelectSort（n,10）;

}

总结：

这次排序总体比较简单，所以调试程序所用时间不长。

但是对结构还是不够熟练，对比较次数和移动次数的计数还存在一定问题。

流程图