各种内排序算法的实现和性能的比较.docx
《各种内排序算法的实现和性能的比较.docx》由会员分享，可在线阅读，更多相关《各种内排序算法的实现和性能的比较.docx（26页珍藏版）》请在冰点文库上搜索。
各种内排序算法的实现和性能的比较
实验报告
（2015/2016学年第2学期）
课程名称
数据结构A
实验名称
各种内排序算法的实现及性能的比较
实验时间
2016
年
6
月
20
日
指导单位
计算机科学与技术系
指导教师
骆健
学生姓名
班级学号
学院（系）
管理学院
专业
信息管理与信息系统
一、问题陈述
（1）验证教材的各种内排序算法
（2）分析各种内排序算法的时间复杂度
（3）改进教材中的快速排序法，使得当子集和小于10个元素时改用直接插入排序
（4）使用随机数发生器产生大数据集合，运行上述各排序算法，使系统时钟测量个算法所需的实际时间，并进行比较。
系统时钟包含在头文件“time.h”中。
二、概要设计
Main.cpp调用Menu.h，为主程序。
Menu.h主菜单
Selectsort.h简单选择排序
Insertsort.h直接插入排序
Bubblesort.h冒泡排序
Quicksort.h快速排序
Mergesort.h合并排序
三、详细设计
①简单选择排序：
将初始序列（A[0]~A[n-1]）作为待排序序列，第一趟在待排序序列（A[0]~A[n-1]）中找最小元素，与该序列中第一个元素A[0]交换，这样子序列（A[0]）有序，下一趟排序在带牌子序列（A[1]~A[n-1]）中进行。
第i趟排序子序列（A[i-1]~A[n-1]）中进行。
经过n-1趟排序后使得初始序列有序。
程序流程图：
②直接插入排序：
一个元素插入到有序表中，首先将其存入临时变量temp，然后从后往前查找插入位置。
当temp小于表中元素时，就将该元素后移一个位置，继续比较、移动，直到temp大于等于表中元素或者到了有序表的第一个元素结束，这时就可将temp存入刚后移的元素的位置了。
程序流程图：
③冒泡排序：
第一趟在序列（A[0]~A[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到A[n-1]中（即沉底）下一趟排序只需在子序列（A[0]~A[n-2]）中进行；如果在某一趟排序中未进行交换元素，说明子序列已经有序，则不再进行下一趟排序。
程序流程图：
④快速排序：
取第一个元素作为分割元素，初始化i=left,j=right+1,i从左往右寻找第一个大于等于分割元素的元素，j从右往左找第一个小于等于分割元素的元素并交换，i和j继续移动，重复上述步骤，直到当i>=j时将j与第一个元素交换。
程序流程图：
⑤两路合并排序：
将有n个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到[n/2]个长度为2或1的有序子序列，再两两合并…直到得到一个长度为n的有序序列时结束。
程序流程图：
四、程序代码
selectsort.h
#include//简单选择排序
template
voidSelectSort（TA[],intn）
{
intsmall;
for（inti=0;ismall=i;
for（intj=i+1;jif（A[j]Swap（A[i],A[small]）;
}
}
Insertsort.h
#include//直接插入排序
template
voidInsertSort（TA[],intn）
{
for（inti=1;iintj=i;
Ttemp=A[i];
while（j>0&&tempA[j]=A[j-1];j--;
}
A[j]=temp;
}
}/*ok!
*/
Bubblesort.h
#include
template
voidBubbleSort（TA[],intn）
{
inti,j,last;
i=n-1;
while（i>0）{
last=0;
for（j=0;jif（A[j+1]Swap（A[j],A[j+1]）;
last=j;
}
i=last;
}
}
Quicksort.h
#include
//改进的快速排序
template
voidquick（TA[],intn）
{
int*a;
inttop=0,right,left,j;
a=newint[n];
if（a==NULL）return;
a[top++]=0;
a[top++]=n-1;
//lc
for（j=0;a[j]!
=NULL;j++）
{
left=a[j++];
right=a[j];
if（left>right）
Swap（left,right）;
if（right-left<15）
InsertSortExt（A,left,right）;
else
{
a[top++]=left;
a[top++]=QuickSort（A,left,right）-1;
a[top++]=a[top-2]+2;
a[top++]=right;
}
}
}
template
intQuickSort（TA[],intleft,intright）
{
inti,j;
if（lefti=left;j=right+1;
do{
doi++;while（A[i]doj--;while（A[j]>A[left]）;
if（i}while（iSwap（A[left],A[j]）;
returnj;
}
return0;
}
template
voidInsertSortExt（TA[],intleft,intright）
{
for（inti=left+1;iintj=i;
Ttemp=A[i];
while（j>0&&tempA[j]=A[j-1];j--;
}
A[j]=temp;
}
}
Mergesort.h
#include
//两路合并的C++程序
template
voidMerge（TA[],inti1,intj1,inti2,intj2）
{
T*Temp=newT[j2-i1+1];
inti=i1,j=i2,k=0;
while（i<=j1&&j<=j2）
if（A[i]<=A[j]）Temp[k++]=A[i++];
elseTemp[k++]=A[j++];
while（i<=j1）Temp[k++]=A[i++];
while（j<=j2）Temp[k++]=A[j++];
for（i=0;idelete[]Temp;
}
//合并排序的C++程序
template
voidMergeSort（TA[],intn）
{
inti1,j1,i2,j2;
intsize=1;
while（sizei1=0;
while（i1+sizei2=i1+size;
j1=i2-1;
if（i2+size-1>n-1）
j2=n-1;
elsej2=i2+size-1;
Merge（A,i1,j1,i2,j2）;
i1=j2+1;
}
size*=2;
}
}
Meau.h
#include
#include
#include
#include
#include"selectsort.h"
#include"insertsort.h"
#include"bubblesort.h"
#include"quicksort.h"
#include"mergesort.h"
#defineSIZE400
#defineTIMES1000
template
classMenu
{
public:
voidprintmenu（）;
voidselectsort（）;//简单选择排序
voidinsertSort（）;//直接插入排序
voidbubbleSort（）;//冒泡排序
voidquickSort（）;//快速排序
voidmergeSort（）;//两路合并排序
voidchildmenu（）;//子菜单1
voidchildmenu2（）;//子菜单2
voidswitcha（）;
private:
inta,b,c;
};
template
voidMenu:
:
printmenu（）
{
cout<<"-------------------------------内排序测试系统-------------------------------"<cout<<""<cout<<"1.简单选择排序"<cout<<"2.直接插入排序"<cout<<"3.冒泡排序"<cout<<"4.快速排序"<cout<<"5.两路合并排序"<cout<<"6.退出"<this->switcha（）;
}
template
voidMenu:
:
childmenu（）
{
cout<<"--------------------------------------------------------"<cout<<"1.最好情况"<cout<<"2.最坏情况"<cout<<"3.平均情况"<cout<<"4.返回主菜单"<cin>>b;
if（b==4）this->printmenu（）;
}
template
voidMenu:
:
childmenu2（）
{
cout<<"--------------------------------------------------------"<cout<<"1.原始算法"<cout<<"2.改进算法"<cout<<"3.返回主菜单"<cin>>c;
if（c==3）this->printmenu（）;
}
template
voidMenu:
:
switcha（）
{
//cout<<"ok"<cin>>a;
switch（a）
{
case1:
this->selectsort（）;break;//ok
case2:
this->insertSort（）;break;//ok
case3:
this->bubbleSort（）;break;//ok
case4:
this->quickSort（）;break;//ok
case5:
this->mergeSort（）;break;//ok
case6:
exit
（1）;break;
default:
cout<<"error"<printmenu（）;break;
}
};
template
voidprintout（TA[],intn）//打印数组，测试时用
{
for（inti=0;icout<cout<}
template
T*producedate（intx）//产生顺序，逆序，随机的数组
{
inti;
T*A=newT[SIZE];
switch（x）
{
case1:
for（i=0;ibreak;
case2:
for（i=SIZE;i>0;i--）A[i-1]=SIZE-i;returnA;//逆序
break;
case3:
srand（time（NULL））;
for（i=0;ibreak;
default:
cout<<"error"<}
}
template
voidSwap（T&a,T&b）//交换2个元素
{
Ttemp=a;
a=b;
b=temp;
}
template
voidMenu:
:
bubbleSort（）
{
cout<<"冒泡排序"<this->childmenu（）;
T*A;
doubleduration;
clock_tstart,finish;
start=clock（）;
cout<<"ok"<for（inti=0;i{
A=producedate（b）;
BubbleSort（A,SIZE）;
delete[]A;
}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
//printout（A,SIZE）;
cout<<"用时：
"<system（"pause"）;
//delete[]A;
this->bubbleSort（）;
}/*ok*/
template
voidMenu:
:
insertSort（）
{
cout<<"直接插入排序"<this->childmenu（）;
T*A;
doubleduration;
//A=producedate（b）;
//if（A==NULL）{cout<<"error";delete[]A;this->insertSort（）;}
//printout（A,SIZE）;
clock_tstart,finish;
start=clock（）;
cout<<"ok"<for（inti=0;i{
A=producedate（b）;
InsertSort（A,SIZE）;
delete[]A;
}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
//printout（A,SIZE）;
cout<<"用时：
"<system（"pause"）;
//delete[]A;
this->insertSort（）;
}
template
voidMenu:
:
mergeSort（）
{
//this->childmenu（）;
cout<<"合并排序"<cout<<"直接用随机数据测试"<T*A;
doubleduration;
clock_tstart,finish;
start=clock（）;
cout<<"ok"<for（inti=0;i{
A=producedate（3）;
MergeSort（A,SIZE）;
delete[]A;
}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
//printout（A,SIZE）;
cout<<"用时：
"<system（"pause"）;
//delete[]A;
this->printmenu（）;
}/*ok*/
template
voidMenu:
:
quickSort（）
{
this->childmenu2（）;
T*A;
doubleduration;
clock_tstart,finish;
if（c==1）
{
cout<<"原始快速排序"<cout<<"直接用随机数据测试"<start=clock（）;
cout<<"ok"<for（inti=0;i{
A=producedate（3）;
quick（A,SIZE）;
delete[]A;
}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"用时：
"<system（"pause"）;this->quickSort（）;
}
elseif（c==2）
{
cout<<"改进的快速排序"<cout<<"直接用随机数据测试"</*A=producedate（3）;
printout（A,SIZE）;
quick（A,SIZE）;
printout（A,SIZE）;
delete[]A;
this->printmenu（）;
*/
//T*A;
start=clock（）;
cout<<"ok"<for（inti=0;i{
A=producedate（3）;
quick（A,SIZE）;
delete[]A;
}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"用时：
"<system（"pause"）;
this->quickSort（）;
}
else{cout<<"error"<printmenu（）;}
}
template
voidMenu:
:
selectsort（）
{
//this->childmenu（）;
cout<<"简单选择排序"<cout<<"直接用随机数据测试"<T*A;
doubleduration;
clock_tstart,finish;
start=clock（）;
cout<<"ok"<for（inti=0;i{
A=producedate（3）;
SelectSort（A,SIZE）;
delete[]A;
}
finish=clock（）;
duration=（double）（finish-start）/CLOCKS_PER_SEC;
//printout（A,SIZE）;
cout<<"用时：
"<system（"pause"）;
//delete[]A;
this->printmenu（）;
}
Mymain.cpp
#include"Menu.h"
intmain（）
{
MenuMenuObj;
MenuObj.printmenu（）;
cout<<"okend."<return0;
}
五、实验结果
六、实验小结
（1）在编写此次程序时要熟练运用函数的递归套用
（2）在进行输入时，一定要细心，少犯没有分号，括号数目不对等低级错误，这会大大增加调试的时间。
（3）采用模块化思想，主函数尽量只放函数调用
升级会员 