实验课程：算法分析与设计
实验名称：几种排序算法的平均性能比较（验证型实验）
实验目标：
（1）几种排序算法在平均情况下哪一个更快。

（2）加深对时间复杂度概念的理解。

实验任务：
（1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。

对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。

（2）随机产生20组数据（比如n=5000i，1≤i≤20）。

数据均属于范围（0，105）内的整数。

对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。

（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。

实验设备及环境：
PC；C/C++等编程语言。

实验主要步骤：
(1)明确实验目标和具体任务；
(2)理解实验所涉及的几个分类算法；
(3)编写程序实现上述分类算法；
(4)设计实验数据并运行程序、记录运行的结果；
(5)根据实验数据及其结果得出结论；
(6)实验后的心得体会。

一:问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：1:随机生成n个0到100000的随机数用来排序的算法如下.
for(int n=1000;n<20000;n+=1000)
{
int a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=(int) (Math.random()*100000);
}
2.计算时间的类Date通过它的对象d1的getTime()得到当前时间,再得到排序完成时的时间,相减得到排序所花的时间.
Date d1=new Date();
T=d2.getTime()-d1.getTime()
3:排序算法:其它count均表示排序中比较的次数.
插入排序主要算法如下
int count=0;
int c[]=new int[b.length];
c[0]=b[0];int j;
for(int i=1;i<c.length;i++)
{
for(j=i-1;j>=0&&b[i]<c[j];j--)
{ count++;
c[j+1]=c[j];
}
count++;
c[j+1]=b[i];
}
选择排序主要算法:
int count=0;
for(int i=0;i<b.length;i++)
{ int k=i;
for(int j=i+1;j<b.length;j++)
{count++;if (b[j]<b[k]) k=j;}
if(k!=i)
{int l;l=b[i];b[i]=b[k];b[k]=l;}
}
合并排序:
static int merge(int a[],int st,int ce,int fi)
{int count=0;
//a表示数组,st表示要排序的数据的起点,ce表示第一部分的终点也是第二部分的起点,fi表示第二部份的终点
int i=st;
int j=ce;
int cp=0; //由于数组c从0开始,而a是从st开始,并不一定是0.故要通过cp来表示c 的第cp个值.
int c[]=new int[fi-st];
for(;i<ce;i++){
for(;j<fi;j++){
if(a[i]>a[j]) {
count++;
c[cp]=a[j];
cp++;
}
else break;
}
c[cp]=a[i];
cp++;
}
//若j的值还小于fi则继续把j到fi的值复制给c.此处也与书上的不同,主要由自己的理解来实现
for(;j<fi;j++)
{
c[cp]=a[j];
cp++;
}
//把得到的值复制到a数组上
for(int k=0;k<c.length;k++)
{
a[st]=c[k];
st++;
}
return count;
}
快速排序:用的方法与书上略有不同,主要通过spilt直接进行递归.
static int spilt(int a[],int low,int high){
int count=0;
int i=low;
int x=a[low];
for(int j=low+1;j<=high;j++){
if(a[j]<=x){
count++;
i=i+1;
if(i!=j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
int temp= a[low];
a[low]=a[i];
a[i]=temp;
int w=i;
if(low<high){
if(w-1>low)count=count+spilt(a,low,w-1); //此处的if语句可以减少很多不必要的排序,例如只剩下一个数字时就不必再用spilt来排序了.
if(w+1<high)count=count+spilt(a,w+1,high);
}
return count;
}
二:实验数据及其结果（可用图表形式给出）：
排序个
插入排序选择排序合并排序快速排序堆排序
数
比较次数时间比较次数时间比较次数时间比较次数时间比较次数时间1000 246415 3毫秒499500 2毫秒4292 1毫秒6042 0毫秒5336 1毫秒
2000 987905 4毫秒1999000 5毫秒13895 0毫秒12502 1毫秒17251 1毫秒3000 2221253 7毫秒4498500 9毫秒28911 1毫秒18072 1毫秒35738 1毫秒4000 3974807 12毫秒7998000 16毫秒50087 1毫秒27763 0毫秒61389 1毫秒5000 6330740 17毫秒12497500 24毫秒76719 2毫秒31673 0毫秒94119 0毫秒6000 9000822 26毫秒17997000 33毫秒109515 1毫秒38876 1毫秒134365 1毫秒7000 12361649 34毫秒24496500 44毫秒148792 1毫秒52786 1毫秒182049 1毫秒8000 16195701 46毫秒31996000 59毫秒195261 2毫秒54716 0毫秒237456 1毫秒9000 20312730 58毫秒40495500 75毫秒247395 2毫秒78117 1毫秒300444 1毫秒10000 24720510 70毫秒49995000 91毫秒305728 1毫秒80273 1毫秒370843 1毫秒11000 29937848 84毫秒60494500 113毫秒370517 4毫秒89960 1毫秒448841 1毫秒12000 36256786 104毫秒71994000 133毫秒442232 2毫秒107707 1毫秒535030 2毫秒13000 42587471 120毫秒84493500 155毫秒520492 2毫秒102860 1毫秒629174 1毫秒14000 49063373 139毫秒97993000 177毫秒605806 2毫秒125364 1毫秒731191 1毫秒15000 56280216 161毫秒112492500 201毫秒698546 3毫秒134152 2毫秒841492 3毫秒16000 64205137 185毫秒127992000 228毫秒799410 2毫秒135362 1毫秒960400 1毫秒17000 72750562 206毫秒144491500 258毫秒906838 3毫秒144717 1毫秒1087013 2毫秒18000 80846587 231毫秒161991000 288毫秒1020136 3毫秒164631 2毫秒1221699 2毫秒19000 90537142 264毫秒180490500 321毫秒1139757 5毫秒168298 2毫秒1364230 2毫秒
三:实验结果分析及结论：
实验结果表明,选择排序用时普遍比其它算法大,自顶向上合并排序时间普遍较少,尤其是当数据量变得很大的时候,选择排序的速度变得远远不及自顶向上合并排序算法,大出好几百倍.另外,插入排序在当数据量变大时花费的时间也变得很长.快速排序和堆排序处于不确定的情况,不稳定性比较明显.但是是一种比较快的算法.
四:实验自我评价及心得体会：
通过本实验,我发现以前经常使用的冒泡排序,选择排序等排序方法在遇到大量的数据的时候显示出来的严重的不足,而自底向上合并排序却显示出了其优越性,尽管合并排序的算法比较难,但它在时间上节省让人发现一切都是值得的.
另外,我发现书上的伪代码只能供参考,并不能直接按着它的完全翻译成C++或java代码,而且用到数组的时候,伪代码的1表示第一个数据,而数组中的第一个数据是a[0].所以直接翻译会出现排序的错误.
五:主要参考文献：
<<算法设计技巧与分析>>。