北京邮电大学 数据结构 实验三简单数组排序的设计.docx

北京邮电大学 数据结构 实验三简单数组排序的设计.docx

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

北京邮电大学数据结构实验三简单数组排序的设计

数据结构实验报告

实验名称：

实验3——简单数组实现排序

学生姓名：

XXXXNB

班级：

XXXXXXXX

班内序号：

学号：

XXXXXXXX

日期：

2016年XXXXXXX

1．实验要求

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

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：

正序、逆序、随机数据

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

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

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

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

2.程序分析

在题目中要求测试不同的数据，可以手动输入待排序元素。

我在编程时为了界面的简洁易于监控，便选择了在主程序中把数组写好放入主程序里。

同时为了方便每种算法的比较，我将所有的函数包装为一个类，方便运行并监控。

比较遗憾的是，我没有做算法运行时间的相关程序，为了弥补这种缺陷，我选择了将界面做的更人性化一些。

2.1存储结构

采用数组进行顺序存储结构 

示意图如下:

2.2关键算法分析

核心算法思想：

1. 利用教材讲述的基本算法思想，实现其中五种排序算法，统计其运行相关数据。

2. 将五种排序函数封装到一个类中，使得程序代码可读性、结构更加优化。

排序算法分析 ：

 1.插入排序算法 

插入排序的思想是：

每次从无序区取一元素将其添加到有序区中。

a.直接插入排序

 C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数

同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数

voidSort:

:

DirectInsertSort（inta[],intn）//直接插入排序

{

intk;

intmove=0;

intcompare=0;

for（inti=2;i<=n;i++）//第一个定然为有序，出现两个数据时开始进行排序

{

if（a[i]

{

a[0]=a[i];

move++;//元素赋值移动+1

for（intj=i-1;j>0&&a[0]

{

a[j+1]=a[j];

move++;//移动+1

compare++;//for条件中比较+1

k=j;//记录查找出的位置

}

a[k]=a[0];

move++;//元素赋值移动+1

}

compare++;//if比较n大小+1

}

cout<<"移动次数"<

cout<<"比较次数"<

}

b.希尔排序

希尔排序，设待排序对象序列有n个元素，先取d

例如取d=d/2，重复子序列的划分和排序工作，直到取d=1，仅有一个子序列为止（ps：

本质上仍为直接插入排序的改进）

 C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数

同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数

voidSort:

:

ShellInsert（inta[],intn）//希尔排序，本质上为直接插入排序的改进

{

intk;

intmove=0;

intcompare=0;

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

{

for（inti=d+1;i<=n;i++）//前d个元素是每个子序列头部，为初始有序区，从d+1开始循环

{

if（a[i]

{

a[0]=a[i];

move++;//赋值移动+1

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

{

a[j+d]=a[j];

move++;//元素后移+1

compare++;//for循环中条件比较+1

k=j;

}

a[k]=a[0];

move++;//元素赋值移动+1

}

compare++;//if中比较+1

}

}

cout<<"移动次数"<

cout<<"比较次数"<

}

//希尔排序利用了直接排序的两个特点：

1.基本有序直接插入最快2.记录个数很少的无序序列，直接插入也很快。

//希尔排序是不稳定的排序算法，时间复杂度是实验测得的

2.交换排序

a.冒泡排序

在基本的冒泡排序上进行改进：

简单的冒泡排序每一趟只添加一个进入有序区，若无序区存在有序的元素仍需比较，效率低，改进后的冒泡排序将每一趟最后一次交换的位置作为下一次起泡无序区的末尾，这样会减少开销

C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数

同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数

voidSort:

:

ImprovedBubbleSort（inta[],intn）//改进的冒泡排序

{

intmove=0;

intcompare=0;

intpos=n;//初始时起泡的范围

while（pos!

=0）

{

intbound=pos;

pos=0;//若不存在交换时，则pos为0，排序结束

for（inti=1;i

{

if（a[i]>a[i+1]）//相邻元素比较

{

a[0]=a[i];//交换元素

a[i]=a[i+1];

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

pos=i;

move=move+3;//一次交换移动+3

}

compare++;//if条件中比较+1

}

}

cout<<"移动次数"<

cout<<"比较次数"<

}

b.快速排序

快速排序是起泡排序的改进，起泡排序是相邻元素的操作，快速排序是从两端向中间进行，由于每次元素移动，都非常接近元素最后排好序的位置，故而效率很高！

！

每次总拟定每个分区第一个元素为轴值，进行分区，每次分区后，轴值左侧均小于等于轴值，轴值右侧均大于等于轴值，然后不断分区，最终排好序

C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数

同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数

intSort:

:

FirstQsort（inta[],intfirst,intend,int&move,int&compare）//一趟快速排序的描述//每一趟可以将一个元素即轴值移动到最终的位置

{

inti=first;

intj=end;

intpivot=a[i];//选分区首元素为轴值

while（i

{

while（（i=pivot））

j--;

compare=compare+2;//一次while循环中条件比较+2

a[i]=a[j];

move++;//移动+1

while（（i

i++;

compare=compare+2;//一次while循环中条件比较+2

a[j]=a[i];

move++;//元素移动+1

compare++;//外围while循环+1

}

a[i]=pivot;//将轴值移至i=j的位置

returni;//返回分界值i

}

voidSort:

:

QuickSort（inta[],inti,intj,int&compare,int&move）//快速排序//当分区不断缩小至只有一个元素时，快速排序结束

{

if（i

{

intPartion=FirstQsort（a,i,j,compare,move）;

QuickSort（a,i,Partion-1,compare,move）;//左分区快速排序

QuickSort（a,Partion+1,j,compare,move）;//右分区快速排序//递归的复杂性！

此递归构造的很好

compare++;//if条件比较+1

}

}

3.选择排序

简单选择排序，通过元素间的比较，每一趟选出无序区最小的元素

C++描述如下，其中形参a[]为待排序数组，n为待排序元素个数

同时添加两个变量move,compare用于记录整个排序过程中的比较次数以及移动次数

voidSort:

:

SelectSort（inta[],intn）

{

intcompare=0;

intmove=0;

for（inti=1;i

{

intMinimum=i;//先将第一个元素最为最小值并进行比较

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

{

if（a[j]

{

Minimum=j;

compare++;//if比较+1

}

if（Minimum!

=i）

{

a[0]=a[i];

a[i]=a[Minimum];//将目前最小值赋给应为最小值的

a[Minimum]=a[0];

move=move+3;//一次交换移动+3

}

compare++;//if条件比较+1

}

compare++;

}

cout<<"移动次数"<

cout<<"比较次数"<

}

对于上面的算法，进行简单的归纳：

3.程序运行结果

主函数流程图：

是

否

是否退出

测试截图：

初始化测试数组，菜单创建

执行功能：

4.总结

1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现五种排序的基本功能，并且测试无误。

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

如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。

因而采用了内部设计好数组的形式，不过仍有改进的余地，这也是这次设计比较遗憾的一处。

此外还添加了一些人性化的交互，菜单的界面设计，版面风格也变得好看，可读性增强。

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

这次做优化的过程中，遇到不少阻力。

由因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。

完整源代码：

//插入排序交换排序选择排序

//采用的存储结构均为0号位置置空的整形一维数组

#include

usingnamespacestd;

classSort

{

public:

//插入排序

voidDirectInsertSort（inta[],intn）;//直接插入排序，目的最后呈现升序排序，此时为一组数据存储于一维数组中，但无序

//目的是最终呈现出有序序列

voidShellInsert（inta[],intn）;//希尔排序，设待排序对象序列有n个元素，先取d

//子序列，对每一个子序列分别进行直接插入排序，然后缩小间隔d，即减少子序列个数

//例如取d=d/2，重复子序列的划分和排序工作，直到取d=1，仅有一个子序列为止

//交换排序

voidImprovedBubbleSort（inta[],intn）;//改进后的冒泡排序

//将每一趟最后一次交换的位置作为下一次起泡无序区的末尾，这样会减少开销

intFirstQsort（inta[],intfirst,intend,int&move,int&compare）;//快速排序一趟的函数描述

voidQuickSort（inta[],inti,intj,int&move,int&compare）;//快速排序是起泡排序的改进，起泡排序是相邻元素的操作，快速排序是从两端向中间进行

//由于每次元素移动，都非常接近元素最后排好序的位置，故而效率很高！

！

//每次总拟定每个分区第一个元素为轴值，进行分区，每次分区后，轴值左侧均小于等于轴值

//轴值右侧均大于等于轴值，然后不断分区，最终排好序

//选择排序

voidSelectSort（inta[],intn）;//简单选择排序，每一趟选出无序区最小的元素

voidPrint（inta[],intn）;//打印出排序后的数组

};

voidSort:

:

Print（inta[],intn）//打印数组

{

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

cout<

cout<

}

voidSort:

:

DirectInsertSort（inta[],intn）//直接插入排序

{

intk;

intmove=0;

intcompare=0;

for（inti=2;i<=n;i++）//第一个定然为有序，出现两个数据时开始进行排序

{

if（a[i]

{

a[0]=a[i];

move++;//元素赋值移动+1

for（intj=i-1;j>0&&a[0]

{

a[j+1]=a[j];

move++;//移动+1

compare++;//for条件中比较+1

k=j;//记录查找出的位置

}

a[k]=a[0];

move++;//元素赋值移动+1

}

compare++;//if比较n大小+1

}

cout<<"移动次数"<

cout<<"比较次数"<

}

voidSort:

:

ShellInsert（inta[],intn）//希尔排序，本质上为直接插入排序的改进

{

intk;

intmove=0;

intcompare=0;

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

{

for（inti=d+1;i<=n;i++）//前d个元素是每个子序列头部，为初始有序区，从d+1开始循环

{

if（a[i]

{

a[0]=a[i];

move++;//赋值移动+1

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

{

a[j+d]=a[j];

move++;//元素后移+1

compare++;//for循环中条件比较+1

k=j;

}

a[k]=a[0];

move++;//元素赋值移动+1

}

compare++;//if中比较+1

}

}

cout<<"移动次数"<

cout<<"比较次数"<

}

//希尔排序利用了直接排序的两个特点：

1.基本有序直接插入最快2.记录个数很少的无序序列，直接插入也很快。

虽然算法冗余，但效率高

//希尔排序是不稳定的排序算法，时间复杂度是实验测得的

voidSort:

:

ImprovedBubbleSort（inta[],intn）//改进的冒泡排序

{

intmove=0;

intcompare=0;

intpos=n;//初始时起泡的范围

while（pos!

=0）

{

intbound=pos;

pos=0;//若不存在交换时，则pos为0，排序结束

for（inti=1;i

{

if（a[i]>a[i+1]）//相邻元素比较

{

a[0]=a[i];//交换元素

a[i]=a[i+1];

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

pos=i;

move=move+3;//一次交换移动+3

}

compare++;//if条件中比较+1

}

}

cout<<"移动次数"<

cout<<"比较次数"<

}

intSort:

:

FirstQsort（inta[],intfirst,intend,int&move,int&compare）//一趟快速排序的描述//每一趟可以将一个元素即轴值移动到最终的位置

{

inti=first;

intj=end;

intpivot=a[i];//选分区首元素为轴值

while（i

{

while（（i=pivot））

j--;

compare=compare+2;//一次while循环中条件比较+2

a[i]=a[j];

move++;//移动+1

while（（i

i++;

compare=compare+2;//一次while循环中条件比较+2

a[j]=a[i];

move++;//元素移动+1

compare++;//外围while循环+1

}

a[i]=pivot;//将轴值移至i=j的位置

returni;//返回分界值i

}

voidSort:

:

QuickSort（inta[],inti,intj,int&compare,int&move）//快速排序//当分区不断缩小至只有一个元素时，快速排序结束

{

if（i

{

intPartion=FirstQsort（a,i,j,compare,move）;

QuickSort（a,i,Partion-1,compare,move）;//左分区快速排序

QuickSort（a,Partion+1,j,compare,move）;//右分区快速排序//递归的复杂性！

此递归构造的很好

compare++;//if条件比较+1

}

}

voidSort:

:

SelectSort（inta[],intn）

{

intcompare=0;

intmove=0;

for（inti=1;i

{

intMinimum=i;//先将第一个元素最为最小值并进行比较

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

{

if（a[j]

{

Minimum=j;

compare++;//if比较+1

}

if（Minimum!

=i）

{

a[0]=a[i];

a[i]=a[Minimum];//将目前最小值赋给应为最小值的

a[Minimum]=a[0];

move=move+3;//一次交换移动+3

}

compare++;//if条件比较+1

}

compare++;

}

cout<<"移动次数"<

cout<<"比较次数"<

}

voidmain（）

{

Sorts;

intm=1;

cout<<"\t\t**************************************************"<

<<"\t\t※※"<

<<"\t\t※请选择你想要的排序方式※"<

<<"\t\t※※"<

<<"\t\t※1.直接插入排序※"<

<<"\t\t※※"<

<<"\t\t※2.希尔插入排序※"<

<<"\t\t※※"<

<<"\t\t※3.冒泡排序※"<

<<"\t\t※※"<

<<"\t\t※4.快速排序※"<

<<"\t\t※※"<

<<"\t\t※5.简单选择排序※"<

<<