数据结构课程设计报告---几种排序算法的演示(附源代第四次实验码)
- 格式：doc
- 大小：248.50 KB
- 文档页数：26
本周的实验主要做快速排序，自己随机生成10000个数据，用快速排序算法，输出排序完成所需时间，再用其他排序方法做比较，至少完成两个算法的效率比较
数据结构课程设计报告
—几种排序算法的演示
时间：2010-1-14
一 需求分析
运行环境
Microsoft Visual Studio 2005
程序所实现的功能
对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序算法的演示，并且输出每一趟的排序情况。
程序的输入（包含输入的数据格式和说明）
<1>排序种类三输入
<2>排序数的个数的输入
<3>所需排序的所有数的输入
程序的输出（程序输出的形式）
<1>主菜单的输出
<2>每一趟排序的输出，即排序过程的输出
二 设计说明
算法设计思想
<1>交换排序（冒泡排序、快速排序）
交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。
<2>插入排序（直接插入排序、折半插入排序）
插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。
<3>选择排序（简单选择排序、堆排序）
选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。
<4>归并排序（两路归并排序）
两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。
程序的主要流程图
程序的主要模块(要求对主要流程图中出现的模块进行说明)
程序的主要模块主要分为主菜单模块和排序算法演示模块。 开始
进入主菜单
选择排序方法
输出排序结果 直插 折半 冒泡 选择 快排 堆排 归并
退出系统
<1>主菜单
主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。
<2>排序方法及输出
根据运行者对排序的不同选择，进入排序过程
a.直接插入排序：根据直接排序的算法，输出排序过程
b.折半插入排序：根据折半插入的算法，输出排序过程
c.冒泡排序：根据冒泡排序算法，输出排序过程
d.简单选择排序：根据简单选择排序的算法，输出排序过程
e.快速排序：根据快速排序的算法，输出排序过程
f.堆排序：根据堆排序的算法，输出排序过程
g.归并排序：根据归并排序的算法，输出排序过程
程序的主要函数及其伪代码说明
<1>模板类
主要说明程序中用到的类的定义
templateclass sortlist
{
private:
int currentsize;//数据表中数据元素的个数
public:
type *arr;//存储数据元素的向量（排序表）
sortlist():currentsize(0){arr=new type[maxsize];}//构造函数
sortlist(int n){arr=new type[maxsize];currentsize=n;}
void insert(int i,type x){arr[i]=x;}
~sortlist(){delete []arr;}//析构函数
void swap(type &x,type &y)//数据元素x和y交换位置
{type temp=x;x=y;y=temp;}
void bubblesort();//冒泡排序
void quicksort(int low,int high);//快速排序
void insertionsort();//直接插入排序
void binaryinsertsort();//折半插入排序
void selectsort();//简单选择排序
void heapsort();//堆排序
void mergesort(sortlist &table);//归并排序
void filterdown(const int start);//建立最大堆
void mergepass(sortlist&sourcetable,sortlist&mergedtable,const
int len);//一趟归并
void merge(sortlist&sourcetable,sortlist&mergedtable,const int
left,const int mid,const int right);//两路归并算法
};
<2>直接插入排序
直接插入排序的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1
以下是在顺序表上实现的直接插入排序
在顺序表上进行直接插入排序时，当插入第i(1
伪代码如下
template //直接插入排序
void sortlist::insertionsort()
{
type temp;
int j;
for(int i=1;i<=currentsize-1;i++)
{
temp=arr[i];j=i-1;
while(j>=0&&temp
{arr[j+1]=arr[j];j--;}
arr[j+1]=temp;
cout<<"第"<<++num<<"趟排序结果为:";
for(int t=0;t
cout<
cout<
}
num=0;
}
<3>折半插入排序
折半插入排序的基本思想：设在排序表中有n个数据元素arr[0],arr[1],…,arr[n-1]。其中，arr[0],arr[1],…,arr[n-1]是已经排好序的部分数据元素序列，在插入arr[i]时，利用折半查找方法寻找arr[i]的插入位置。折半插入排序方法只能在顺序表存储结构实现。
伪代码如下：
template //折半插入排序
void sortlist::binaryinsertsort()
{
type temp;
int left,right;
for(int i=1;i
left=0;right=i-1;temp=arr[i];
while(left<=right)//找插入位置
{
int mid=(left+right)/2;
if(temp
else left=mid+1;
}
for(int k=i-1;k>=left;k--)//向后移动
arr[k+1]=arr[k];
arr[left]=temp;
cout<<"第"<<++num<<"趟排序结果为:";
for(int t=0;t
cout<
cout<
}
num=0;
}
<4>冒泡排序
冒泡排序的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字arr[0]和arr[1]进行比较。如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到arr[n-2]的位置。如此最多做n-1趟冒泡就能把所有数据元素排好序。
伪代码如下：
template //冒泡排序
void sortlist:: bubblesort()
{
int i=1;
int finish=0;//0表示还没有排好序
while(i
{
finish=1;//排序结束标志置为,假定已经排好序
for(int j=0;j
if(arr[j]>arr[j+1])//逆序
{
swap(arr[j],arr[j+1]);//相邻元素交换位置
finish=0;
}//排序结束标志置为,表示本趟发生了交换，说明还没有排好序
i++;
cout<<"第"<<++num<<"趟排序结果为:";
