实验课程：算法分析与设计
实验名称：几种排序算法的平均性能比较 （验证型实验）
实验目标：
（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); 序,例如只剩下一个数字时就不必再用spilt来排序了. if(w+1<high)count=count+spilt(a,w+1,high); }
return count;
}
二:实验数据及其结果（可用图表形式给出）： 排序个
插入排序 选择排序 合并排序 数
比较次数 时间 比较次数 时间 比较次数 时间
1000 246415 3毫秒 499500 2毫秒 4292 1毫秒 //此处的if语句可以减少很多不必要的排快速排序 堆排序 比较次数 时间 比较次数 时间 6042 0毫秒 5336 1毫秒
2000 3000 4000 5000 6000 7000 8000 9000 10000 11000 12000 13000 14000 15000 16000 17000 18000 19000
987905 4毫秒 2221253 7毫秒 3974807 12毫秒 6330740 17毫秒 9000822 26毫秒 12361649 34毫秒 16195701 46毫秒 20312730 58毫秒 24720510 70毫秒 29937848 84毫秒 36256786 104毫秒 42587471 120毫秒 49063373 139毫秒 56280216 161毫秒 64205137 185毫秒 72750562 206毫秒 80846587 231毫秒 90537142 264毫秒
1999000 5毫秒 4498500 9毫秒 7998000 16毫秒 12497500 24毫秒 17997000 33毫秒 24496500 44毫秒 31996000 59毫秒 40495500 75毫秒 49995000 91毫秒 60494500 113毫秒 71994000 133毫秒 84493500 155毫秒 97993000 177毫秒 112492500 201毫秒 127992000 228毫秒 144491500 258毫秒 161991000 288毫秒 180490500 321毫秒
13895 0毫秒 28911 1毫秒 50087 1毫秒 76719 2毫秒 109515 1毫秒 148792 1毫秒 195261 2毫秒 247395 2毫秒 305728 1毫秒 370517 4毫秒 442232 2毫秒 520492 2毫秒 605806 2毫秒 698546 3毫秒 799410 2毫秒 906838 3毫秒 1020136 3毫秒 1139757 5毫秒
12502 1毫秒 18072 1毫秒 27763 0毫秒 31673 0毫秒 38876 1毫秒 52786 1毫秒 54716 0毫秒 78117 1毫秒 80273 1毫秒 89960 1毫秒 107707 1毫秒 102860 1毫秒 125364 1毫秒 134152 2毫秒 135362 1毫秒 144717 1毫秒 164631 2毫秒 168298 2毫秒
17251 1毫秒 35738 1毫秒 61389 1毫秒 94119 0毫秒 134365 1毫秒 182049 1毫秒 237456 1毫秒 300444 1毫秒 370843 1毫秒 448841 1毫秒 535030 2毫秒 629174 1毫秒 731191 1毫秒 841492 3毫秒 960400 1毫秒 1087013 2毫秒 1221699 2毫秒 1364230 2毫秒
三:实验结果分析及结论：
实验结果表明,选择排序用时普遍比其它算法大,自顶向上合并排序时间普遍较少,尤其是当数据量变得很大的时候,选择排序的速度变得远远不及自顶向上合并排序算法,大出好几百倍.另外,插入排序在当数据量变大时花费的时间也变得很长.快速排序和堆排序处于不确定的情况,不稳定性比较明显.但是是一种比较快的算法. 四:实验自我评价及心得体会：
通过本实验,我发现以前经常使用的冒泡排序,选择排序等排序方法在遇到大量的数据的时候显示出来的严重的不足,而自底向上合并排序却显示出了其优越性,尽管合并排序的算法比较难,但它在时间上节省让人发现一切都是值得的.
另外,我发现书上的伪代码只能供参考,并不能直接按着它的完全翻译成C++或java代码,而且用到数组的时候,伪代码的1表示第一个数据,而数组中的第一个数据是a[0].所以直接翻译会出现排序的错误. 五:主要参考文献：
<<算法设计技巧与分析>>
第二篇：C++ 八种排序算法总结及实现
八种排序算法总结之C++版本
五种简单排序算法
一、 冒泡排序 【稳定的】
void BubbleSort( int* a,int Count ) //实现从小到大的最终结果
{
int temp;
for(int i=1; i<Count; i++) //外层每循环一次，将最小的一个移动到最前面 for(int j=Count-1; j>=i; j--)
if( a[j] < a[j-1] )
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。（呵呵，不要说没学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
二、 交换排序 【稳定的】
void ExchangeSort( int *a,int Count)
{
int temp;
for(int i=0; i<Count-1; i++)
for(int j=i+1; j<Count; j++)
if( a[j] < a[i] )
{
temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
时间复杂度为O(n*n)。
三、 选择法 【不稳定的】
void SelectSort( int *a,int Count)
{
int temp; //一个存储值
int pos; //一个存储下标
for(int i=0; i<Count; i++)
{
temp = a[i];
pos = i;
for(int j=i+1; j<Count; j++)
if( a[j] < temp ) //选择排序法就是用第一个元素与最小的元素交换 {
temp = a[j];
pos = j; //下标的交换赋值，记录当前最小元素的下标位置 }
a[pos] = a[i];
a[i] = temp;
}
}
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n 所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。
四、 插入法 【稳定的】
void InsertSort( int *a,int Count)
{
int temp; //一个存储值
int pos; //一个存储下标
for(int i=1; i<Count; i++) //最多做n-1趟插入
{
temp = a[i]; //当前要插入的元素
pos = i-1;
while( pos>=0 && temp<a[pos] )
{
a[pos+1] = a[pos]; //将前一个元素后移一位
pos--;
}
a[pos+1] = temp;
}
}
其复杂度仍为O(n*n)。
最终，我个人认为，在简单排序算法中，直接插入排序是最好的。
五、 希尔排序法 【不稳定的】
/*
* 希尔排序，n为数组的个数
*/
void ShellSort( int arr[], int n )
{
int temp,pos;
int d = n; //增量初值
do{
d = d/3 + 1 ;
for(int i= d; i<n; i++ )
{
temp = arr[i];
pos = i-d;
while( pos>=0 && temp < arr[pos] ) {
arr[ pos + d ] = arr[pos];
pos -= d;
}
arr[ pos + d ] = temp;
}
} while( d > 1 );
}
//实现增量为d的插入排序
三种高级排序算法
一、 快速排序 辅助空间复杂度为O（1） 【不稳定的】 void QuickSort( int *a,int left, int right)
{
int i,j,middle,temp;
i = left;
j = right;
middle = a[ (left+right)/2 ];
do
{
while( a[i]<middle && i<right ) //从左扫描大于中值的数 i++;
while( a[j]>middle && j>left ) //从右扫描小于中值的数 j--;
if( i<=j ) //找到了一对值
{
temp = a[i];
a[i] = a[j];
}
a[j] = temp; i++; j--; } } while ( i<j ); //如果两边的下标交错，就停止(完成一次) //当左半边有值（left<j）,递归左半边 if( left < j ) QuickSort( a, left, j); //当右半边有值（right>i）,递归右半边 if( i < right ) QuickSort( a, i, right);
它的工作看起来象一个二叉树。首先我们选择一个中间值middle，程序中我们使用数组中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（最容易的方法——递归）。注意，由于数据的随机性，对middle的选择并不会影响该算法的效率。
注意，在扫描过程中，对于给定参考值，对于向右(左)扫描，如果扫描值大(小)于或等于参考值，就需要进行交换。最终得到的结果是，j左边的值都小于参考值，而i右边的值都大于参考值，j和i之间的值都等于参考值。对j左边和i右边的分别使用递归，就可以完成最终的排序。
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟），但是糟糕的情况只会持续一个流程，到下一个流程的时候就很可能已经避开了该中间的最大和最小值，因为数组下标变化了，于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大？？呵呵，你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢
于快速排序（因为要重组堆）。
二、 归并排序（两种实现方法均要掌握） 【稳定的】
归并排序是一种极好的外部排序方法，即针对数据保存在磁盘上而不是高速内存中的问题。
//以下程序参考数据结构课本P286页的模板,为使用指针链表实现的
#include <iostream>
using namespace std;
struct node{ //链表的节点数据
int value;
node *next;
};
node * divide_from( node * head )
{
node * position, * midpoint, * second_half;
if( (midpoint=head) == NULL ) //List is empty
return NULL;
position = midpoint->next;
while( position != NULL ) //Move position twice for midpoint's one move {
position = position->next;
if( position != NULL )
{
midpoint = midpoint->next;
position = position->next;
}
}
second_half = midpoint->next;
midpoint->next = NULL; //在这里将原链拆断，分为两段
return second_half;
}
node * merge( node * first, node * second)
{
node * last_sorted; //当前已经链接好的有序链中的最后一个节点
node combined; //哑节点
last_sorted = &combined;
while( first!=NULL && second!=NULL )
{
if( first->value < second->value ) {
last_sorted->next = first;
last_sorted = first;
first = first->next;
}else {
last_sorted->next = second;
last_sorted = second;
second = second->next;
}
}
if( first==NULL )
last_sorted->next = second;
else
last_sorted->next = first;
return combined.next; //返回哑节点的后继指针，即为合并后的链表的头指针 }
//这里的参数必须是引用调用，需要这个指引去允许函数修改调用自变量
void MergeSort( node * &head)
{
if( head != NULL && head->next != NULL ) //如果只有一个元素，则不需排序 {
node * second_half = divide_from( head );
MergeSort( head );
MergeSort( second_half );
head = merge( head, second_half );
}
}
int main()
{
node a,b,c,d;
node *p1, *p2, *p3, *p4,*head;
p1 = &a;
p2 = &b;
p3 = &c;
p4 = &d;
a.value = 2;
b.value = 4;
c.value = 3;
d.value = 1;
a.next = p2;
b.next = p3;
c.next = p4;
d.next = NULL;
//调用归并排序前的结果
head = p1;
while( head != NULL )
{
cout<<head->value<<" ";
head = head->next;
}
cout<<endl;
MergeSort( p1 );
//调用归并排序后的结果
head = p1;
while( head != NULL )
{
cout<<head->value<<" ";
head = head->next;
}
cout<<endl;
}
//以下程序为使用数组实现的归并排序,辅助空间复杂度为O（n）
#include <iostream>
using namespace std;
void Merge( int data[], int left, int mid, int right ) {
int n1,n2,k,i,j;
n1 = mid - left + 1;
n2 = right - mid;
int *L = new int[n1]; //两个指针指向两个动态数组的首地址 int *R = new int[n2];
for( i=0,k=left; i<n1; i++,k++)
L[i] = data[k];
for( i=0,k=mid+1; i<n2; i++,k++)
R[i] = data[k];
for( k=left,i=0,j=0; i<n1 && j<n2; k++) {
if( L[i] < R[j] ) { //取小者放前面
data[k] = L[i];
i++;
} else {
data[k] = R[j];
j++;
}
}
if( i<n1 ) //左边的数组尚未取尽
for( j=i; j < n1; j++,k++)
}
/*
* left:数组的开始下标，一般为0；right：数组的结束下标，一般为 （n-1） */
void MergeSort( int data[], int left, int right )
{
if( left < right )
{
int mid = left + ( right-left ) / 2; //mid=(right+left)/2，防止溢出 MergeSort( data, left, mid );
MergeSort( data , mid+1, right );
Merge( data , left, mid , right );
}
}
int main()
{
int data[] = {9,8,7,2,5,6,3,55,1};
//排序前的输出
for(int i=0; i<9; i++)
cout<<data[i]<<" ";
cout<<endl;
MergeSort( data, 0, 8);
//排序后的输出
for(int i=0; i<9; i++)
cout<<data[i]<<" ";
cout<<endl;
}
三、 堆排序 【不稳定的】
/*
* 向堆中插入current元素的函数
*/
void insert_heap( int data[], const int ¤t, int low, int high ) data[k] = L[j]; else //if( j<n2 ) //右边的数组尚未取尽 ,这句话可要可不要 for( i=j; i<n2; i++,k++) data[k] = R[i]; delete []L; //回收内存 delete []R;
{
int large; //元素data[low]左右儿子中，大者的位置
large = 2*low + 1;
while( large <= high ) {
if( large < high && data[large] < data[ large+1] )
large++;
if( current > data[ large ] ) //待插入元素的值比它的两个儿子都大 break;
else {
data[ low ] = data[ large ]; //将其左右儿子的大者上移
low = large;
large = 2 * large + 1;
}
}
data[ low ] = current;
}
/*
* 建立堆函数，num为数组data的元素个数
* 只有一个结点的<2-树>自动满足堆的属性，因此不必担心树中的任何树叶，即 * 不必担心表的后一半中的元素。如果从表的中间点开始并从后向前工作，就 * 能够使用函数insert_heap去将每个元素插入到包含了所有后面元素的部分堆 * 中，从而创建完整的堆。
*/
void build_heap( int data[], int num )
{
int current;
for( int low = num/2 - 1; low>=0; low-- ) {
current = data[ low ];
insert_heap( data, current, low, num-1 );
}
}
/*
* 堆排序主函数,num为数组data的元素个数
*/
void heap_sort( int data[], int num )
{
int current, last_sorted;
build_heap( data, num ); //建立堆
for( last_sorted = num-1; last_sorted>0; last_sorted-- ) { //逐个元素处理 current = data[ last_sorted ];
//data[0]在整个数组排序结束前，存储的是待排序元素中最大的元素
data[last_sorted] = data[0];
insert_heap( data, current, 0, last_sorted-1 );
}
}
int main()
{
//用于排序算法的输入输出
int a[8] = {5,7,1,2,9,4,6,3,};
for(int i=0; i< sizeof(a)/sizeof(int); i++) cout<<a[i]<<" ";
cout<<endl;
heap_sort( a, 8 ); //调用堆排序
for(int i=0; i< sizeof(a)/sizeof(int); i++) cout<<a[i]<<" ";
cout<<endl;
return 0;
}