一、题目描述
通过随机数据比较各排序算法的关键字比较次数和关键字移动次数，以 及执行时间，取得直观感受。
二、设计要求
一、需求分析
实现各排序算法，分别进行以下各组比较，并进行总结。
一、各算法在不同规模下的比较。
1）比较范围：直接插入排序、冒泡法排序、简单选择排序、快速排序1（自己实现）、快速排序2（调用STL）、归并排序。
2）比较指标：a）关键字操作次数（比较次数和移动次数之和），b)排序时间。每个指标采用多次重复取平均数记录，重复次数不小于100。注：1次关键字对换按3次移动计算。
3）数据规模：分别为50,100,500,1000,5000,10000；
4）数据类型：随机数据
二、算法在不同数据类型下的比较
1）比较范围：直接插入排序、冒泡法排序、简单选择排序、快速排序1（自己实现）、快速排序2（调用STL）、归并排序。
2）比较指标：a）关键字操作次数（比较次数和移动次数之和），b)排序时间。每个指标采用多次重复取平均数记录，重复次数不小于100。注：1次关键字对换按3次移动计算。
3）数据规模：10000；
4）数据类型：随机数据、正序数据、逆序数据；
三、代码要求
1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格：
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能 、关键代码应说明其功能
3、递归程序注意调用的过程，防止栈溢出
四、算法分析
#include<iostream>
#include<time.h>
#include <algorithm>
#include<stdlib.h>
#include <windows.h>
#include <string>
using namespace std;
//关键次数初始化
static long long move1=0;
static long long move2=0;
static long long move3=0;
static long long move4=0;
static long long move5=0;
static long long move6=0;
//输出结果
void print(int a[], int n){
for(int j= 0; j<n; j++){
cout<<a[j] <<" ";
}
cout<<endl<<endl;
}
/***********归并排序*******************/
void Merge(int r[],int rf[], int i, int m, int n) //归并操作
{
int j,k;
for(j=m+1,k=i; i<=m && j <=n ; ++k){
move1+=1;
if(r[i] < r[j]) {rf[k] = r[i++]; move1+=3; move1+=1;}
else {rf[k] = r[j++]; move1+=3; move1+=1;}
}
while(i <= m) {rf[k++] = r[i++]; move1+=3; move1+=2;}
move1+=1;
while(j <= n) {rf[k++] = r[j++]; move1+=3; move1+=2;}
move1+=1;
}
void MSort(int r[], int rf[], int s, int t) //将r[]归并排序为rf[]
{
move1+=1;
//int *rf2=new int[t];
int rf2[10000+1];
if(s==t) {rf[s] = r[s]; move1+=3;}
else
{
move1+=1;
int m=(s+t)/2; /*平分*p 表*/
MSort(r, rf2, s, m); /*递归地将p[s…m]归并为有序的p2[s…m]*/
MSort(r, rf2, m+1, t); /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
Merge(rf2, rf, s, m,t); /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
}
}
void MergeSort(int r[], int rf[], int n)
{ /*对顺序表*p 作归并排序*/
MSort(r, rf, 0, n-1);
}
/*************归并排序结束*******************/
/***********快速排序1(递归)*******************/
/*
void swap(int* a,int*b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
move2+=3;
}
int Partition(int a[],int low,int high)
{
int pivotkey= a[low];
while(low<high)
{
while (low<high&&a[high]>=pivotkey) { --high;move2+=1;}
swap(&a[low],&a[high]);
while (low<high&&a[low<=pivotkey]){ ++low;move2+=1;}
swap(&a[low],&a[high]);
}
move2+=1
return low;
}
void quickSort(int a[], int low, int high)
{
int pivotloc;
if (low<high)
{
pivotloc = Partition(a,low,high); //将表一分为二
quickSort(a,low,pivotloc-1); //递归对低子表递归排序
quickSort(a,pivotloc+1,high); //递归对高子表递归排序
}
move2+=1;
}*/
/*************快速排序1(递归)结束*******************/
/***********快速排序1(非递归)*******************/
void quicksort(int a[],int n)
{
struct node
{
int low,high;
}st[10000];
int i,j,low,high,temp,top=0;
st[top].low=0;
st[top].high=n-1;
while(top>-1)
{ low=st[top].low;
high=st[top].high;
top--;
i=low;
j=high;
if(low<high)
{
move2+=1;
temp=a[low];
while(i!=j)
{
move2+=1;
while(i<j&&a[j]>temp){ j--; move2+=1;}
if(i<j){a[i]=a[j];i++;move2+=3;}
while(i<j&&a[i]<temp){ i++; move2+=1;}
if(i<j){a[j]=a[i];j--;move2+=3;}
}
a[i]=temp;
top++;
st[top].low=low;
st[top].high=i-1;
top++;
st[top].low=i+1;
st[top].high=high;
}
move2+=1;
}
move2+=1;
}
/*************快速排序1(非递归)结束*******************/
/*************冒泡排序开始*******************/
void bubbleSort(int a[], int n)
{
int temp;
for(int i=0;i<n-1;i++)
for(int j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
move3+=3;
}
move3+=1;
}
}
/*************冒泡排序结束*******************/
/*************简单选择排序开始*******************/
void selectSort(int a[], int n)
{
int key,temp;
for(int i=1;i<n;i++)
{
key=i-1;
for(int j=i;j<n;j++)
{
if(a[j]<a[key])
{
key=j;
move4+=3;
}
move4+=1;
}
if(key!=i-1)
{
temp=a[key];
a[key]=a[i-1];
a[i-1]=temp;
move4+=3;
}
move4+=1;
// print(a,n,i); //打印每趟排序的结果
}
}
/*************简单选择排序结束*******************/
/*************直接插入排序结束*******************/
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
move5+=1;
int j= i-2;
int x = a[i]; //复制为哨兵，即存储待排序元素
move5+=3;
a[i] = a[i-1]; //先后移一个元素
move5+=1;
while(x < a[j]&&j>=0){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
move5+=1;
}
move5+=1;
a[j+1] = x; //插入到正确位置
}
move5+=1;
// print(a,n,i); //打印每趟排序的结果
}
}
/*************直接插入排序结束*******************/
/*************STL快速排序开始************************/
int comp(const void*a,const void*b)
{
move6+=3;
return *(int*)a-*(int*)b;
}
/*************STL快速排序结束************************/
//汇总所有的排序算法
void sort123(int z,int type)
{
/********初始化变量*********************/
//clock_t *start=new clock_t[100];
//clock_t *end=new clock_t[100];
long long *start=new long long[100];
long long *end=new long long[100];
double *dfMinus=new double[100];
double *dfTim=new double[100];
LARGE_INTEGER litmp;
double dfFreq;
QueryPerformanceFrequency(& litmp); //获取CPU时钟频率
dfFreq = (double)litmp.QuadPart;
double times1=0;
double times2=0;
double times3=0;
double times4=0;
double times5=0;
double times6=0;
srand(time(NULL));
//给原数组赋值
for(int i=0;i<=99;i++)
{
//初始化各个数组
int *a=new int[z];
int *c=new int[z];
int *d=new int[z];
int *e=new int[z];
int *f=new int[z];
int *g=new int[z];
if(type==0)
{
for(int j=0;j<z;j++) //下标法
{
a[j]=rand();
c[j]=a[j];
d[j]=a[j];
e[j]=a[j];
f[j]=a[j];
g[j]=a[j];
}
}
else if(type==1)
{
for( int j=0;j<z;j++)
{
a[j]=j+i;
c[j]=a[j];
d[j]=a[j];
e[j]=a[j];
f[j]=a[j];
g[j]=a[j];
}
}
else
{
for(int j=0;j<z;j++)
{
a[j]=z-j+i;
c[j]=a[j];
d[j]=a[j];
e[j]=a[j];
f[j]=a[j];
g[j]=a[j];
}
}
/***归并排序开始*******/
QueryPerformanceCounter(&litmp); //获取开始计数值
start[i] = litmp.QuadPart;
int *b=new int[z]; //b数组用于归并排序
MergeSort(c,b, z);
QueryPerformanceCounter(&litmp); //获取结束计数值
end[i] = litmp.QuadPart;
dfMinus[i] = (double)(end[i]- start[i]);
dfTim[i] = dfMinus[i]/dfFreq; //计算持续时间，单位为秒误差不超过1微妙算持续时间，单位为秒误差不超过1微妙
times1+=dfTim[i];
delete []b;
delete []c;
/*****归并排序结束********/
/***快速排序1开始*******/
QueryPerformanceCounter(&litmp); //获取开始计数值
start[i] = litmp.QuadPart;
quicksort(d,z); //此处用的是非递归快排，非递归需要堆栈不是很大
//quickSort(d,0,z-1); //此处是递归快排算法，算法在上面已经注释掉，因为快排递归需要堆栈太大，一般电脑需要调整堆栈，我改动的为5032768字节（随便，够大就好）
QueryPerformanceCounter(&litmp); //获取结束计数值
end[i] = litmp.QuadPart;
dfMinus[i] = (double)(end[i]- start[i]);
dfTim[i] = dfMinus[i]/dfFreq; //计算持续时间，单位为秒误差不超过1微妙算持续时间，单位为秒误差不超过1微妙
times2+=dfTim[i];
//if(i<=0)
// print(d,z);
delete []d;
/*****快速排序1结束********/
/***冒泡开始*******/
QueryPerformanceCounter(&litmp); //获取开始计数值
start[i] = litmp.QuadPart;
bubbleSort(e,z); //冒泡排序
QueryPerformanceCounter(&litmp); //获取结束计数值
end[i] = litmp.QuadPart;
dfMinus[i] = (double)(end[i]- start[i]);
dfTim[i] = dfMinus[i]/dfFreq; //计算持续时间，单位为秒误差不超过1微妙算持续时间，单位为秒误差不超过1微妙
times3+=dfTim[i];
delete []e;
/*****冒泡结束********/
/***选择法开始*******/
QueryPerformanceCounter(&litmp); //获取开始计数值
start[i] = litmp.QuadPart;
selectSort(f,z); //简单选择排序
QueryPerformanceCounter(&litmp); //获取结束计数值
end[i] = litmp.QuadPart;
dfMinus[i] = (double)(end[i]- start[i]);
dfTim[i] = dfMinus[i]/dfFreq; //计算持续时间，单位为秒误差不超过1微妙算持续时间，单位为秒误差不超过1微妙
times4+=dfTim[i];
delete []f;
/*****选择法结束********/
/***插入法开始*******/
QueryPerformanceCounter(&litmp); //获取开始计数值
start[i] = litmp.QuadPart;
InsertSort(g,z); //直接插入排序
QueryPerformanceCounter(&litmp); //获取结束计数值
end[i] = litmp.QuadPart;
dfMinus[i] = (double)(end[i]- start[i]);
dfTim[i] = dfMinus[i]/dfFreq; //计算持续时间，单位为秒误差不超过1微妙算持续时间，单位为秒误差不超过1微妙
times5+=dfTim[i];
delete []g;
/*****插入法结束********/
/***STL快排法开始*******/
QueryPerformanceCounter(&litmp); //获取开始计数值
start[i] = litmp.QuadPart;
//sort(a, a+z); //STL一种改进型分段算法
qsort(a,z,sizeof(int),comp);
QueryPerformanceCounter(&litmp); //获取结束计数值
end[i] = litmp.QuadPart;
dfMinus[i] = (double)(end[i]- start[i]);
dfTim[i] = dfMinus[i]/dfFreq; //计算持续时间，单位为秒误差不超过1微妙算持续时间，单位为秒误差不超过1微妙
times6+=dfTim[i];
/*****STL快排法结束********/
delete []a;
}
delete []start;
delete []end;
delete []dfMinus;
delete []dfTim;
/***********打印用时**********************/
string s;
if(type==0) { s="随机数据";cout<<s<<endl;}
else if(type==1) { s="正序数据";cout<<s<<endl;}
else { s="逆序数据";cout<<s<<endl;}
cout<<"归并排序： "<<z<<"个"<<s<<"重复实验100次;"<<" 关键字操作次数平均为"<<move1/100<<"次"<<endl<<"平均耗时"<<times1/100*1000<<" 毫秒"<<endl<<endl;
cout<<"快速排序(非递归)： "<<z<<"个"<<s<<"重复实验100次;"<<" 关键字操作次数平均为"<<move2/100<<"次"<<endl<<"平均耗时"<<times2/100*1000<<" 毫秒"<<endl<<endl;
cout<<"冒泡排序： "<<z<<"个"<<s<<"重复实验100次;"<<" 关键字操作次数平均为"<<move3/100<<"次"<<endl<<"平均耗时"<<times3/100*1000<<" 毫秒"<<endl<<endl;
cout<<"简单选择排序： "<<z<<"个"<<s<<"重复实验100次;"<<" 关键字操作次数平均为"<<move4/100<<"次"<<endl<<"平均耗时"<<times4/100*1000<<" 毫秒"<<endl<<endl;
cout<<"直接插入排序： "<<z<<"个"<<s<<"重复实验100次;"<<" 关键字操作次数平均为"<<move5/100<<"次"<<endl<<"平均耗时"<<times5/100*1000<<" 毫秒"<<endl<<endl;
cout<<"STL快速排序： "<<z<<"个"<<s<<"重复实验100次;"<<" 关键字操作次数平均为"<<move6/100<<"次"<<endl<<"平均耗时"<<times6/100*1000<<" 毫秒"<<endl<<endl;
}
//主函数
int main()
{
sort123(50,0);
sort123(100,0);
sort123(500,0);
sort123(1000,0);
sort123(5000,0);
sort123(10000,0);
sort123(10000,1);
sort123(10000,2);
system("pause");
return 0;
} 六、结果截图
七、结果分析:
1、随机数据比较：数据规模分别为50,100,500,1000,5000,10000，我们经过验证可以得出初步结论：
在数据基本无序的状态下且数据较多：排序效率比较如下：
快速排序法>STL快速排序法>归并排序法>直接插入排序法>简单选择法>
冒泡排序法
在数据基本无序的状态下且数据较少：排序效率比较如下：
快速排序法>STL快速排序法>直接插入排序法简单选择法>冒泡排序法>
归并排序法
在数据更少的情况下，直接插入法也有奇效。
2、正序数据比较：数据规模为10000，我们经过验证可以得出初步结论:
在数据基本有序且为正序的状态下：排序效率如下：
直接插入排序>STL快速排序法>归并排序>快速排序>简单选择排序>
冒泡排序法
3、逆序数据比较：数据规模为10000，我们经过验证可以得出初步结论:
在数据基本有序且为正序的状态下：排序效率如下：
STL快速排序法>归并排序>快速排序>直接插入排序>简单选择排序>
冒泡排序法
八、总结
1、涉及递归的有归并排序以及快速排序，这两个都是我编写程序的时候感觉最艰难的。
2、归并排序使用的数组除了中间要合并用的那个rf2用的是静态数组，其他都是动态数组new创建的，堆创建数组本来是挺好的，可是这里却因为数据规模较大的时候，递归太深rf2又无法delete[],只能用数组，创建了一个rf2[10001].
3、快速排序我写了两种方法，一种是递归的，一种是非递归的，递归真的理解是最简单的，可是对堆栈真的要求太高了，递归本来是崩溃的，不过忽然找到了方法：因为快排递归需要堆栈太大，一般电脑需要调整堆栈，我改动的为5032768字节（随便，够大就好）
4、时间精度的问题也好解决，用的是QueryPerformance，这个精度非常好，学到的好东西。