各种内排序算法的实现及性能的比较.docx

实验报告
（2015/2016学年第2学期）

课程名称数据结构A实验名称各种内排序算法的实现及性能的比较实验时间2016年6月20日指导单位计算机科学与技术系指导教师骆健

学生姓名班级学号学院(系)管理学院专业信息管理与信息系统

问题陈述
验证教材的各种内排序算法
分析各种内排序算法的时间复杂度
改进教材中的快速排序法，使得当子集和小于10个元素时改用直接插入排序
使用随机数发生器产生大数据集合，运行上述各排序算法，使系统时钟测量个算法所需的实际时间，并进行比较。系统时钟包含在头文件“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趟排序后使得初始序列有序。
程序流程图：
开始
i=0
i<n-1
Small=i
j=i+1
j<n
A[j]<A[small]
Small=j
Swap(A[i],A[small])
j++
结束
N
N
N
Y
Y
i++

②直接插入排序：一个元素插入到有序表中，首先将其存入临时变量temp，然后从后往前查找插入位置。当temp小于表中元素时，就将该元素后移一个位置，继续比较、移动，直到temp大于等于表中元素或者到了有序表的第一个元素结束，这时就可将temp存入刚后移的元素的位置了。
程序流程图：

开始
i<n
intj=i
Ttemp=A[i]
j>0&&temp<A[j-1]
A[j]=A[j-1];j--
A[j]=temp
i++
结束
N
Y
Y
N

③冒泡排序：第一趟在序列（A[0]~A[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到A[n-1]中（即沉底）下一趟排序只需在子序列（A[0]~A[n-2]）中进行；如果在某一趟排序中未进行交换元素，说明子序列已经有序，则不再进行下一趟排序。
程序流程图：
开始
i=n-1
i>0
last=0;j=0
j<i
A[j+1]<A[j]
Swap(A[j],A[j+1])
Last=j
i=last
结束
N
N
Y
Y

④快速排序：取第一个元素作为分割元素，初始化i=left,j=right+1,i从左往右寻找第一个大于等于分割元素的元素，j从右往左找第一个小于等于分割元素的元素并交换，i和j继续移动，重复上述步骤，直到当i>=j时将j与第一个元素交换。
程序流程图：
开始
left<right
i=left;j=right
i++
A[i]<A[left]
j--
A[j]>A[left]
i<j
Swap(A[i],A[j])
i<j
Swap(A[left],A[j])
Qsort(A,left,j-1)
Qsort(A,j+1,right)
结束
N
Y
Y
N
Y
N
N
Y
Y
N
⑤两路合并排序：将有n个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到[n/2]个长度为2或1的有序子序列，再两两合并…直到得到一个长度为n的有序序列时结束。
程序流程图：
开始
intsize=1
Size<n
i1=1
i1+size<n
i2=i1+size
j1=i2-1
i2+size-1>n-1
j2=n-1
Merge(A,i1,j1,i2,j2)
i1=j2+1
size*=2
结束
j2=i2+size-1
N
Y
Y
N
N
Y

四、程序代码
selectsort.h
#include<iostream.h>//简单选择排序
template<classT>
voidSelectSort(TA[],intn)
{
intsmall;
for(inti=0;i<n-1;i++){
small=i;
for(intj=i+1;j<n;j++)
if(A[j]<A[small])small=j;
Swap(A[i],A[small]);
}
}
Insertsort.h
#include<iostream.h>//直接插入排序
template<classT>
voidInsertSort(TA[],intn)
{
for(inti=1;i<n;i++){
intj=i;