专业班级：姓 名：学 号：设计时间：指导教师：
排序算法比较分析
08软件工程2班 汪伟 08010xxxxx
2010-9-15—-2010-9-27 杨薇薇
课程设计报告的内容
一、题目：排序算法比较
1、 设计目的
1． 掌握各种排序的基本思想。 2． 掌握各种排序方法的算法实现。
3． 掌握各种排序方法的优劣分析及花费的时间的计算。 4． 掌握各种排序方法所适应的不同场合。 2、 设计内容和要求
利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间
二、 运行环境（软、硬件环境）
软件环境：Vc6.0编程软件 运行平台： Win32 硬 件： 普通个人pc机
三、 算法设计的思想
1、冒泡排序：bubbleSort()
基本思想: 设待排序的文件为r[1..n]
第1趟(遍)：从r[1]开始,依次比较两个相邻记录的关键字 r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录 r[i]和r[i+1]的位置；否则,不交换。 (i=1,2,...n-1)
第1趟之后,n个关键字中最大的记录移到了r[n]的位置上。 第2趟：从r[1]开始,依次比较两个相邻记录的关键字 r[i].key和r[i+1].key,若r[i].key>r[i+1].key，则交换记录 r[i]和r[i+1]的位置；否则,不交换。 (i=1,2,...n-2)
第2趟之后,前n-1个关键字中最大的记录移到了r[n-1]的位 置上，作完n-1趟,或者不需再交换记录时为止。
2、选择排序：selSort()
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。 如此反复进行第二轮、第三轮…直到循环至最后一元素
3、直接插入排序 ：insSort()
在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。
将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。
排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。
4、快序排序：QuickSort()
基本思想：首先在r[1..n]中，确定一个r[i]，经过比较和 移动，将r[i]放到
用同样的方法分别对这两个子文件进行划分, 得到4个更小 的子文件。继续进行下去,使得每个子文件只有一个记录为止, 便得到原文件的有序文件。
例. 给定文件(20,05,37,08,63,12,59,15,44,08)，选 用第1个元素20进行划分:
5、归并排序：MegeSort()
假定文件(r[1],r[2],...,r[n])中记录是随机排列的,进行
2-路归并排序，首先把它划分为长度均为1的n个有序子文件， 然后对它们逐步进行2－路归并排序。其步骤如下：
第1趟：从r[1..n]中的第1个和第2个有序子文件开始,调用 算法merge,每次归并两个相邻子文件,归并结果放到y[1..n]中。 在y中形成 n/2 个长度为2的有序子文件。若n为奇数,则y中最 后一个子文件的长度为1。
第2趟：把y[1..n]看作输入文件,将 n/2 个有序子文件两 两归并,归并结果回送到r[1..n]中,在r中形成 n/2/2个长度为4的有序子文件。若y中有奇数个子文件，则r中最后一个子文 件的长度为2。
共计经过 log2n 趟归并,最后得到n个记录的有序文件。
6、堆排序：HeapSort()
堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
1、N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。2、且对于编号 i（1N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。3、这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。
堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节
从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需
对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的
将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。
四、 算法的流程图
五、 算法设计分析
1、冒泡排序：bubbleSort()
冒泡排序算法分析：
(1)最好情况, 待排序的文件已是有序文件: 只需要进行1趟排序,
共计比较关键字的次数为n－1 不交换记录。
(2)最坏情况, 要经过n-1趟排序， 所需总的比较关键字的次数为
(n-1)+(n-2)+...+1＝n(n-1)/2 交换记录的次数最多为
(n-1)+(n-2)+...+1＝n(n-1)/2 移动记录次数最多为
3n(n-1)/2 。
(3)只需要少量中间变量作为辅助空间。 算法是稳定的。
2、选择排序：selSort()
选择排序算法分析：
(1)比较次数，在任何情况下,均为
(2)交换记录的次数
在最好情况下,原n个记录递增有序：不移动记录。
在最坏情况下共交换记录n-1对,移动记录数3(n-1)次。 故,时间复杂度为O(n2)。
(3)只需少量中间变量作为辅助空间。 (4)算法是不稳定的。
3、直接插入排序 ：insSort()
直接插入排序算法分析：
故,时间复杂度为O(n2)。
(4) 只需少量中间变量作为辅助空间。 (5) 算法是稳定的。
4、快序排序：QuickSort(d)
快速排序算法分析： (1)就平均速度而言，
快速排序是已知内部排序方法中最好的一种排序方法, 其时间复杂度为
O(nlog(n))。
(2)在最坏情况下，
快速排序所需的比较次数和冒泡排序的比较次数相同, 其时间复杂度为
O(n2)。
(3)快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。 在最坏情况下,递归深度为n， 所需栈的空间大小为
O(n)。
(4)快速排序是不稳定的。
5、归并排序：MegerSort()
归并排序算法分析：
(1)对n个记录的文件进行归并排序,共需 log2n 趟,
(2)每趟所需比较关键字的次数不超过n, 共比较
O(nlog2n) 次。
(3)每趟移动n个记录, 共移动记录 O(nlog2n) 个
(4)归并排序需要一个大小为n的辅助空间 y[1..n]。
(5)归并排序是稳定的。
6、堆排序：HeapSort()
堆排序算法分析：
(1)堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成， 它们均是通过调用Heapify实现的。 (2)堆排序的最坏时间复杂度为 O(nlgn)。
(3)堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 (4)堆排序是就地排序，辅助空间为 O(1)。
(5)它是不稳定的排序方法
六、 源代码
#include #include #include #include #include //外部变量定义
int count1=0,bj1=0,yd1=0; int count2=0,bj2=0,yd2=0; int count3=0,bj3=0,yd3=0; int count4=0,bj4=0,yd4=0; int count5=0,bj5=0,yd5=0; int count6=0,bj6=0,yd6=0; clock_t start1,finish1; clock_t start2,finish2; clock_t start3,finish3; clock_t start4,finish4; clock_t start5,finish5; clock_t start6,finish6;
int b[6]={finish1-start1,finish2-start2,finish3-start3,finish4-start4,finish5-start5,finish6-start6};
template class an { public:
void selectsort(T A[],int n);//简单选择排序 void insertsort(T A[],int n);//直接插入排序 void shellsort(T A[],int n); //希尔排序 void bubblesort(T A[],int n);//冒泡排序 void quicksort(T A[],int n);//快速排序 void mergesort(T A[],int n);//两路合并排序 private:
void merge(T A[],int i1,int j1,int i2,int j2); void qsort(T A[],int left,int right); };
template
void an::selectsort(T A[],int n) //简单选择排序 {
int small; start3=clock();
for(int i=0;i
for(int j=i+1;j
if(A[j]
swap(A[i],A[small]); count3++; yd3+=3; } }
cout
template //直接插入排序
void an::insertsort(T A[],int n)
{
start1=clock();
for(int i=1;i
{
int j=i;
T temp=A[i];
while(j>0 && temp
{
bj1++;
A[j]=A[j-1];
j--;
yd1++;
}
A[j]=temp;
}
cout
for(i=0;i
cout
cout
finish1=clock();
}
template //希尔排序
void an::shellsort(T A[],int n)
{
start2=clock();
int j,tmp,jmp;
jmp=n/2;
while(jmp!=0)
{
for(int i=jmp;i
{
tmp=A[i];
j=i-jmp;
while(tmp=0)
{
bj2++;
A[j+jmp]=A[j];
yd2++;
j=j-tmp;
}
bj2++;
A[jmp+j]=tmp;
yd2++;
}
jmp=jmp/2;
}
cout
for(int i=0;i
cout
cout
finish2=clock();
}
template //冒泡排序
void an::bubblesort(T A[],int n)
{
start4=clock();
int i=n-1,j,last;
while(i>0)
{
last=0;
for(j=0;j
{
if(A[j+1]
{
bj4++;
swap(A[j],A[j+1]);
count4++;
yd4+=3;
last=j;
}
bj4++;
}
i=last;
}
cout
for(i=0;i
cout
cout
finish4=clock();
}
template //快速排序
void an::quicksort(T A[],int n)
{
start5=clock();
qsort(A,0,n-1);
cout
for(int i=0;i
cout
cout
finish5=clock();
}
template
void an::qsort(T A[],int left,int right)
{
int i,j;
if(left
{
i=left;
j=right+1;
do{
do{
i++;
bj5++;
}while(A[i]
do {
j--;
bj5++;
}while(A[j]>A[left]);
if(i
{
swap(A[i],A[j]);count5++;yd5+=3;
}
}while(i
swap(A[left],A[j]);
yd5+=3;
count5++;
qsort(A,left,j-1);
qsort(A,j+1,right);
}
}
template //两路合并排序
void an::merge(T A[],int i1,int j1,int i2,int j2)
{
T *temp=new T[j2-i1+1];
int i=i1,j=i2,k=0;
while(i
if(A[i]
{
temp[k++]=A[i++];bj6++;yd6++;
}
else
{
temp[k++]=A[j++];bj6++;yd6++;
}
while(i
{
temp[k++]=A[i++];bj6++;yd6++;
}
while(j
{
temp[k++]=A[j++];yd6++;
}
for(i=0;i
{
A[i1++]=temp[i];yd6++;
}
delete []temp;
}
template
void an::mergesort(T A[],int n)
{
start6=clock();
int i1,j1,i2,j2;
int size=1;
while(size
{
i1=0;
while(i1+size
{
i2=i1+size;
j1=i2-1;
if(i2+size-1>n-1)
j2=n-1;
else j2=i2+size-1;
merge(A,i1,j1,i2,j2);
i1=j2+1;
}
size*=2;
}
cout
for(int i=0;i
cout
cout
finish6=clock();
}
template
void swap(T &a,T &b)
{
int c;
c=a;
a=b;
b=c;
}
void main()
{
an p;
int rand( void ); //生成函数rand 播种子的srand
int n,ch,x=78;
int *array;
cout
cout
cout
cout
cout
cin>>n;
array=new int[n];
for(int i=0;i
cout
for(i=0;i
cout
do{
cout
cout
cout
cout
cout
cout
cout
cout
cout
cin>>ch;
switch(ch){
case 1:
p.insertsort(array,n);
cout
cout
cout
cout
cout
cout
cout
break;
case 2:
p.shellsort(array,n);
cout
cout
cout
cout
cout
cout
cout
break;
case 3:
p.selectsort(array,n);
cout
cout
cout
cout
cout
cout
cout
break;
case 4:
p.bubblesort(array,n);
cout
cout
cout
cout
cout
cout
cout
break;
case 5:
p.quicksort(array,n);
cout
cout
cout
cout
cout
cout
cout
break;
case 6:
p.mergesort(array,n);
cout
cout
cout
cout
cout
cout
cout
break;
case 7:
p.insertsort(array,n);
p.shellsort(array,n);
p.selectsort(array,n);
p.bubblesort(array,n);
p.quicksort(array,n);
p.mergesort(array,n);
cout
cout
cout
h1-start1
cout
etw(8)
cout
sh3-start3
cout
sh4-start4
cout
w(9)
cout
(8)
cout
break;
case 0:
x=0;
break;
}
}while(x);
}
两路合并排序:
七、 运行结果分析
1、截图显示：
2、结果分析：
排序方法的选用应该根据具体情况而定，一般应该从以下几个方面综合考虑：
1. 时间复杂性
2. 空间复杂性
从空间复杂性看，所有排序方法分为三类：
归并排序单独属于一类，其空间复杂性为O(n)；
快速排序单独属于一类，其空涓丛有晕?em>O(log2n) ~ O(n)；
其它排序方法归为一类，其空间复杂性为O(1)。
3. 稳定性
所有排序方法可分为两类，一类是稳定的，包括直接插入排序、起泡排序、简单选择排序和归并排序； 另一类是不稳定的，包括希尔排序、快速排序和堆排序。
4. 算法简单性
从算法简单性看，一类是简单算法，包括直接插入排序、简单选择排序和起泡排序； 另一类是改进算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。
5. 记录本身信息量的大小
记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。 排序方法
最好情况
最坏情况
平均情况
直接插入排序： O(n)、 O(n2) 、O(n2)
起泡排序： 0、 O(n2)、 O(n2)
简单选择排序 0、 O(n) 、O(n)
6. 关键码的分布情况
当待排序记录序列为正序时，直接插入排序和起泡排序能达到O(n)的时间复杂度； 对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键码的分布而改变。
八、 收获及体会
还有一个收获是知道了什么是面向对象的程序设计方法。选择陌生的C++作为实现语言而不是自己学过的也熟悉的C，是想多掌握一门语言，都说C++面向对象，跟C完全不一样，而我刚开始看C++时就觉得它跟C是一回事，只不过把换成了，把printf()换成了cout，换汤不换药，即使引进了类，也只不过把函数移进C的结构体，换了个关键字而已，现在真正要用它编程了，想要设计一个合理的类，却发现无从下手，然后就看书上的例子，看有关知识点的讲解，然后想如果是C，该怎么写，在尝试了C++的运算符重载、函数重载、类模板、函数模板、错误处理机制后，才发现C++真的跟C有本质的不同，以前把C++当C来学是彻底的错了，C++的这些机制对C来说是质的飞跃，类是数据更安全，数据与对应数据的特定的操作关系更紧密、多态性是编译器为程序员分担了很多工作，程序员再不必仅为不同的数据类型浪费精力写冗余的代码、错误处理机制使程序在出错时得到更适当的处理，而不是程序崩溃甚至是粗暴地结束程序……C++对现实的模拟比C进了一大步，对象很像现实世界的物体，代码易理解、易维护、易使用，而且安全性更好，一个没有错误和警告的C程序用C++编译器编译，可能会发现很多隐蔽的错误，这些错误在一定条件下可能会有灾难性后果，从这点就可以看出C++对C的提升。C++相比C的诸多优越之处，真的只有写过程序才会有体会，用了一年多的C，现在觉得还没有才接触不到一个月的C++习惯，可见C++的易用性。
? 其他：
摸索着用C++做完课程设计，增强了自己的自学能力，这应该是最有用的吧，语言会过时，学习的能力却不会过时。
提交文件清单：
? Main.cpp：程序主文件；
? SortList.h：排序表类模板声明及定义；
? Sort.h：排序类模板声明及定义；
? test文件夹：内含data1.txt，data2.txt，……，data15.txt，是15组测试数据。data1.txt至data10.txt用以测试算法性能随数据量的变化规律，data11.txt至data14.txt用以测试各算法在特殊数据下的表现，data15.txt测试排序表元素大小变化时各算法的耗时特性。Sorted.txt存放排序结果。