. .
. . .
实验课程：算法分析与设计
实验名称：几种排序算法的平均性能比较 （验证型实验）
实验目标：
（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++等编程语言。
实验主要步骤：
明确实验目标和具体任务；
理解实验所涉及的几个分类算法；
编写程序实现上述分类算法；
设计实验数据并运行程序、记录运行的结果；
根据实验数据及其结果得出结论；
实验后的心得体会。
问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：
选择排序：令A[1…n]为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序，即对啊[A…n]排序。对某个j,1<=j<=n,设A[j]是最小值。首先，如果就！=1，我们交换A[1]和A[j]。然后由假设，已知如何对A[2..n]排序，因此可对在A[2…n]中的元素递归地排序。可把递归改为迭代。算法程序实现如下：
void SelectionSort(int *Array,int n,int &c)
{
int i,j,k;
int aa;
c=0;
for(i=0;i<n;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
c++;
if(Array[j]<Array[k])k=j;
}
if(k!=i)
{
aa=Array[i];
Array[i]=Array[k];
Array[k]=aa;
}
}
}
插入排序：将n个元素的数列分为已有序和无序两个部分， 每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将 该元素插入到有序数列的合适位置中。算法程序实现如下：
void InsertionSort(int *Array,int n,int &c)
{
int i,j;
int aa;
c=0;
for(i=0;i<n;i++)
{
aa=Array[i];
j=i-1;
while(j>=0 && Array[j]>aa)
{
c++;
Array[j+1]=Array[j];
j=j-1;
}
Array[j+1]=aa;
}
}
自底向上合并排序：利用分治法思想，将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序 序列。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。算法程序实现如下：
void Merge(int *A,int p,int q,int r,int &c)
{
int *B=new int[r-p+1];
int s=p;
int t=q+1;
int k=0;
while(s<=q && t<=r)
{
c++;
if(A[s]<=A[t])
{
B[k]=A[s];
s=s+1;
}
else
{
B[k]=A[t];
t=t+1;
}
k=k+1;
}
if(s==q+1)
{
while(t<=r)
{
B[k]=A[t];
k=k+1;
t=t+1;
}
}
else
{
while(s<=q)
{
B[k]=A[s];
k=k+1;
s=s+1;
}
}
k=0;
while(p<=r)
{
A[p]=B[k];
k++;
p++;
}
delete B;
}
void BottomupSort(int *Array,int n,int &c)
{
int s,i, t=1;
c=0;
while(t<n)
{
s=t;
t=2*s;
i=0;
while(i+t<n)
{
Merge(Array,i,i+s-1,i+t-1,c);
i=i+t;
}
if(i+s<n)
Merge(Array,i,i+s-1,n-1,c);
}
}
快速排序：设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的 数都放到它后面，这个过程称为一趟快速排序。快速排序就是递归调用此过程。算法程序实现如下：
void Split(int *A,int low,int high,int &w,int &c)
{
int aa,x;
int j,i=low;
int mid=(low+high)/2;
if(A[low]<A[high])
{
if(A[mid]<A[low])w=low;
else if(A[mid]<A[high])w=mid;
else w=high;
}
else
{
if(A[mid]<A[high])w=high;
else if(A[mid]<A[low])w=mid;
else w=low;
}
c++;
x=A[w];
aa=A[low];
A[low]=A[w];
A[w]=aa;
for(j=low+1;j<=high;j++)
{
c++;
if(A[j]<=x)
{
i=i+1;
if(i!=j)
{
aa=A[i];
A[i]=A[j];
A[j]=aa;
}
}
}
aa=A[low];
A[low]=A[i];
A[i]=aa;
w=i;
}
void Quick(int *A,int low,int high,int &c)
{
int w;
if(low<high)
{
Split(A,low,high,w,c);
Quick(A,low,w-1,c);
Quick(A,w+1,high,c);
}
}
void QuickSort(int *Array,int n,int &c)
{
c=0;
Quick(Array,0,n-1,c);
}
堆排序：堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区，再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足 R[1..n-1].keys≤R[n].key,由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然 后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n- 1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
…… 直到无序区只有一个元素为止。
void Siftdown(int *H,int n,int i,int &c)
{
bool done=false;
int j,a;
if(2*i+1>n)return;
while(2*i+1<=n && !done)
{
j=i;
i=2*i+1;
c=c+2;
if(i+1<=n && H[i+1]>H[i])i=i+1;
if(H[j]<H[i])
{
a=H[i];
H[i]=H[j];
H[j]=a;
}
else done=true;
}
}
void MakeHeap(int *A,int n,int &c)
{
int i;
for(i=(n-2)/2;i>=0;i--)
Siftdown(A,n-1,i,c);
}
void HeapSort(int *A,int n,int &c)
{
c=0;
MakeHeap(A,n,c);
int j;
int x;
for(j=n-1;j>=1;j--)
{
x=A[0];
A[0]=A[j];
A[j]=x;
Siftdown(A,j-1,0,c);
}
}
实验数据及其结果（可用图表形式给出）：
输入规模n
selection
insertion
bottomup
quick
Heap
5000
运行时间（毫秒）
78
78
0
0
0
数组元素比较次数6200198
56813
63183
107744
10000
运行时间（毫秒）
312
281
16
0
0
数组元素比较次数25208475
123658
138111
235424
20000
运行时间（毫秒）
1263
1123
16
0
16
数组元素比较次数
199990000267476
302923
510812
30000
运行时间（毫秒）
2870
2527
16
16
15
数组元素比较次数
449985000
224979041
410268
460289
800366
40000
运行时间（毫秒）
5210
4509
47
15
16
数组元素比较次数
799980000
402537541
574791
663812
1101172
50000
运行时间（毫秒）
8174
7004
47
16
31
数组元素比较次数
1249975000
626068874
733390
866351
1409734
实验结果分析及结论：
选择排序算法最稳定，算法的效率只跟输入规模有关，与元素序列无关，但也是效率最差。插入排序的效率跟元素的序列有关，最好情况（已排序）时间复杂度为0，最坏情况（逆序）时间复杂度为Θ(n 2).自底向上合并排序、快速排序、堆排序的效率差不多，最坏情况和最好情况时间复杂度都为o(n㏒n),对于绝大部分元素有序的数组，这三种排序算法的效率不如插入排序。
实验自我评价及心得体会：
通过这次实验，我对这五种排序的原理和执行过程有了更清楚地了解，由于本次实验是在VC++2008平台下利用MFC实现，在学习算法的过程中同时也让我更加熟悉了windows的界面编程方法。
主要参考文献：
《算法设计技巧与分析》[沙特]M.H.Alsuwaiyel 著
相关热词搜索： 几种 算法 排序 平均 性能