内部排序算法比较
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了内部排序算法比较，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10661字，纯文字阅读大概需要16分钟。
内容图文
一、题目描述
通过随机数据比较各排序算法的关键字比较次数和关键字移动次数，以 及执行时间，取得直观感受。
二、设计要求
一、需求分析
实现各排序算法，分别进行以下各组比较，并进行总结。
一、各算法在不同规模下的比较。
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;
//关键次数初始化staticlonglong move1=0;
staticlonglong move2=0;
staticlonglong move3=0;
staticlonglong move4=0;
staticlonglong move5=0;
staticlonglong 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(constvoid*a,constvoid*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];longlong *start=newlonglong[100];
longlong *end=newlonglong[100];
double *dfMinus=newdouble[100];
double *dfTim=newdouble[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=newint[z];
int *c=newint[z];
int *d=newint[z];
int *e=newint[z];
int *f=newint[z];
int *g=newint[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];
}
}
elseif(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=newint[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;}
elseif(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");
return0;
}
六、结果截图 
七、结果分析:
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，这个精度非常好，学到的好东西。
原文：http://blog.csdn.net/u011446963/article/details/46490271
内容总结
以上是互联网集市为您收集整理的内部排序算法比较全部内容，希望文章能够帮你解决内部排序算法比较所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。