住房公积金贷款额度计算公式数据结构各种排序算法的时

2020年10月15日发(作者：纪贞)

数据结构各种排序算法的时间
性能.






HUNAN UNIVERSITY


课程实习报告






题 目： 排序算法的时间性能



学生姓名


学生学号




专业班级





指导老师
李晓鸿



完 成 日 期





设计一组实验来比较下列排序算法的时间性能
快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为
比较的对象）
要求
(1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时
间性能等。
(2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100
到10000）；数据 的初始特性类型要多，因而需要具有随机性；实验数据的组数
要多，即同一规模的数组要多选几种不同类 型的数据来实验。实验结果要能以
清晰的形式给出，如图、表等。
(3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。
(4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。
(5)要给出实验的方案及其分析。
说明
本题重点在以下几个方面： < br>理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；
理解并实现测试数据的产 生方法；掌握实验数据的分析和结论提炼；实验结果
汇报等。


一、需求分析
(1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能 的比
较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。
用户输入随机数 的个数n，然后调用随机事件函数产生n个随机数，对这些
随机数进行排序。于是数据为整数
(2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和
比较次数。
(3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机
数，然后对随机数进行各种 排序，根据排序进行时间和次数的比较。
（4）测试数据：略

二、概要设计

1.抽象数据类型
ADT List
数据对象 D＝{ ai | ai ∈ElemSet,
i=1,2,...,n, n≥0 }
数据关
{ |ai-1 ,ai∈D,
基本操作
0;

Elem&) = 0;

Elem&) = 0;

= 0;




= 0;

系 R1＝
i=2,...,n }
virtual void clear() =
bool insert(const
bool append(const
lbool remove(Elem&)
void setStart() = 0;
void setEnd() = 0;
void prev() = 0;
void next() = 0;
int leftLength() const
int rightLength()










const = 0;
bool setPos(int pos) =
0;
bool getValue(Elem&)
const = 0;
void print() const = 0;



2.程序的流程

（1） 输入模块：输入要排序的数的数量n
（2） 处理模块：系统产生n个随机数，对随机数进行排序
（3） 输出模块：将排序的结果输出



3.算法的基本思想
1、 随机数的产生：利用srand()产生随机数。
2、 快速排序：选定一记录R，将所有其他记录关键字k’与记录R的关键字
k比较, 若 k’k 则将记录换至R之
后，继续对R前后两部分记录进行快速排序，直至排序范围为1
3、 插入 排序：逐个处理待排序的记录，每个新记录与前面已排序的子序列
进行比较，将它插入到子序列中正确的 位置
4、 冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地
方为止。
5、 归并排序：将两个或者多个有序表归并成一个有序表
6、 堆排序：首先将数组转化为 一个满足堆定义的序列，然后将堆顶的最大
元素取出，再将剩下的数排成堆，再取堆顶数值，…。如此下 去，直到
堆为空。到最后结束时，就排出了一个由小到大排列的数组。







三、详细设计
（1）产生随机数：直接调用函数 srand(),以时间作为随机种子进行选择，并把
随机数装入数组中

unsigned long int *Sort::setRan(unsigned long
int num){
unsigned long int *ra;
ra=(unsigned
srand(time(NULL));
for(unsigned long int m=0;m ra[m]=rand();
}
cout< return ra;

}

long
int*)malloc(num*sizeof(unsigned long int));

（2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴
值。 定义两个标识low,high。high标识最后一个元素的位置，从后向前，将关键
字与轴值比较， 直至遇到小于轴值的关键字，前移，low标识在第二个元素的位
置，从前向后，将关键字与轴值比较， 直至遇到大于轴值的关键字，后移。当
low,high相遇后第一趟排序结束。调整数列，轴值左边的 为比轴值小的，右边为
比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列 （pivotkey+1
到high的数）分别进行上述递归快速排序，直到范围为1结束。

int partition(int a[],int low,int high){快速排序
中的一趟
int pivotkey;
作为枢轴来使用
pivotkey=a[low];
while(low while(low=pivotkey)
--high;
a[low]=a[high];
while(low ++low;
a[high]=a[low];
}
a[low]=pivotkey;
return low;
}
void qsort(int a[],int low,int high){快速排序的
递归形式

int pivotloc;
if(low pivotloc=partition(a,low,high);一趟排序结果
的调用
qsort(a,low,pivotloc-1);
qsort(a,pivotloc+1,high);
}
}
（3）插入排序 ：插入排序的思想是将一组无序的元素分别插入一个已经有序的
的数组里，并保证插入后的数组也是有序 的。当所有无序组的元素都插入完毕
时，一个有序数组构造完成。数组n[1…r]为初始的一个无序数 组（为了直观起
见，我们这里设定数组从1开始，而不是0），则n[1]默认为只有一个元素的有序数组，n[2]插入只有n[1]构成的有序数组中，则此时有序数组的元素数量变为
2。以此类 推，到第i个元素时，前i-1个元素已经是有序的，此时只需将第i个
元素插入到有序数组中并使之保 持有序。如此直至最后一个元素插入完毕，整
个插入排序完成。
void Sort::insertSort(unsigned long int *s){
this->setNum();
LARGE_INTEGER Freg;
LARGE_INTEGER Count1,Count2;
QueryPerformanceFrequency(&Freg);
QueryPerformanceCounter(&Count1);获取
时间Count1
double d;
int temp,j;

for
{
j=i;
(unsigned long int
i=0;igetRanNum();i++)
temp=s[i];
while (j>=1 && temp {s[j]=s[j-1];
j--;
this->SortNum++;
}
if(j>1)
this->SortNum++;
s[j]=temp;
}
QueryPerformanceCounter(&Count2);获取
时间Count2
d=(double)(
art)(double)rt*1000.0;计算时间
差，d的单位为ms.
cout<<插入排序算法对
个随机数排序时间为为


cout<<插入排序算法对
个随机数交换次数为
次。

}

(4) 冒泡排序（bubble sort）：将被排序的记录数组R[1..n]垂直排列，每个记 录
R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下
往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反
复进行，直到最后任何两个气 泡都是轻者在上，重者在下为止。从无序区底部
向上依次比较相邻的两个气泡的重量，若发现轻者在下、 重者在上，则交换二
者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2 ])，…，(R[2]，R[1])；
对于每对气泡(R[j+1]，R[j])，若R[j+1].k ey容。第一趟扫描完毕时，最轻的气泡就飘 浮到该区间的顶部，即关键字最小
的记录被放在最高位置R[1]上。扫描R[2..n]。扫描完毕时 ，次轻的气泡飘浮
到R[2]的位置上……最后，经过n-1 趟扫描可得到有序区R[1..n]
void Sort::bubbleSort(unsigned long int *s){
this->setNum();
LARGE_INTEGER Freg;
LARGE_INTEGER Count1,Count2;
QueryPerformanceFrequency(&Freg);
QueryPerformanceCounter(&Count1);获取
时间Count1
double d;
unsigned long int temp;
for(unsigned long int

i=0;i<(this->RanNum);i++){
for(int j=i+1;j<(this->RanNum);j++){
if(s[i]>s[j]){
temp = s[i];
s[i]=s[j];
s[j]=temp;
this->SortNum++;
}
}
}
QueryPerformanceCounter(&Count2);获取
时间Count2
d=(double)(
art)(double)rt*1000.0;计算时间
差，d的单位为ms.
cout<<冒泡排序算法对
个随机数排序时间为

cout<<冒泡排序算法对
个随机数交换次数为
次。
}


(5) 堆排序：堆排序与其他排序算法最大的区别是它依靠一种特殊的数据结
构——堆 来进行排序。堆是一种完全二叉树，并且根节点不大于左右子树中的
所有节点，n[i]<=n[2*i ]&&n[i]<=n[2*i+1]。因此堆排序算法首先要将给出的无序
数组构造成一个堆，然后输 出根节点（最小元素），将剩余元素重新恢复成堆，
再次输出根节点。依次类推，直至最后一个节点输出 ，此时堆排序完成。
void Sort::heapRestor(unsigned long int *s,int
i,int m) {
int ma;
if((i<=m2)&&(s[i]>min(s[2*i],s[2*i+1])))
{
if(s[2*i] {
ma=s[i];
s[i]=s[2*i];
s[2*i]=ma;
this->heapRestor(s,2*i,m);
}
else
{
ma=s[i];
s[i]=s[2*i+1];
s[2*i+1]=ma;
this->heapRestor(s,2*i+1,m);

}
this->SortNum=this->SortNum+2;
}
else if(i<=m2)
this->SortNum++;
}

void Sort::heapCreat(unsigned long int *s,int m)
{
int num;
for(num=m2;num>=1;num--)
this->heapRestor(s,num,m);
}
void Sort::heapSort(unsigned long int
*s1,unsigned long int *s2)
{
this->setNum();
int i,num;
num=this->RanNum;
LARGE_INTEGER Freg;
LARGE_INTEGER Count1,Count2;
QueryPerformanceFrequency(&Freg);

QueryPerformanceCounter(&Count1);获取
时间Count1
double d;
this->heapCreat(s1,this->RanNum);
for(i=0;iRanNum;i++)
{
s2[i]=s1[1];
s1[1]=s1[num];
this->heapRestor(s1,1,--num);
}
QueryPerformanceCounter(&Count2);获取
时间Count2
d=(double)(
art)(double)rt*1000.0;计算时间
差，d的单位为ms.
cout<<堆排序算法对
个随机数排序时间为为
cout<<堆排序算法对
个随机数交换次数为次。

}

(6) 合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之

的思想，但两 者仍然有很大差异。合并排序是将一个无序数组n[1…r]分成两个
数组n[1…r2]与n[r2+ 1…r]，分别对这两个小数组进行合并排序，然后再将这
两个数组合并成一个大数组。由此我们看出合 并排序时一个递归过程（非递归
合并排序这里不做讨论）。合并排序的主要工作便是“合并”，两个小规 模数组
合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行
的。
void Sort::mergeSort(unsigned long int *s,int
left,int right){
int i;
if(left < right){
i=(left + right)2;
mergeSort(s,left, i);
mergeSort(s, i + 1, right);
Merge(s, left, i, right);
}
}

int Sort::partition(unsigned long int *s,int
low,int high){
int key,i,p,r;
p=low;
r=high;
key=s[p];
while(p
{
for(i=r;i>p;i--)
{
if(s[i]<=key)
{
s[p]=s[r];
p++;
this->SortNum++;
break;
}
r--;
this->SortNum++;
}
for(i=p;i {
if(s[i]>key)
{
s[r]=s[p];
r--;
this->SortNum++;
break;
}

p++;
this->SortNum++;
}

}
s[p]=key;

return p;
}



(
7)基本操作

AList(int size=DefaultListSize) {
maxSize = size;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
~AList() { delete [] listArray; }
<1>清空。释放数组，将数组大小和栅栏置0.
void clear() {
delete [] listArray;
listSize = fence = 0;

listArray = new Elem[maxSize];
}
<2>将栅栏赋初值0，放在开头。
void setStart() { fence = 0; }
<3>将栅栏指向数组最后。
void setEnd() { fence = listSize; }
<4>获得当前的位置。用栅栏的指向即可直接获
得。
void prev() { if (fence != 0) fence--; }
<5>获得最大值的大小，由栅栏可直接获得。
void next() { if (fence <= listSize)
fence++; }
<6>返回当前位置左边的长度。直接返回栅栏的
值获得。
int leftLength() const { return fence; }
<7>返回当前位置右边的长度。用最大长度减去
当前栅栏的值。
int rightLength() const
{ return listSize - fence; }
<8>设置当前位置，将值直接赋予栅栏。
bool setPos(int pos) {
if ((pos >= 0) && (pos <= listSize))

fence = pos;
return (pos >= 0) && (pos <= listSize);
}
<9>返回当前的值。
bool getValue(Elem& it) const {
if (rightLength() == 0) return false;
else {
it = listArray[fence];
return true;
}
}


（4）算法的时空分析
<1>插入排序：直接插入排序算 法必须进行n-1趟。最好情况下，即初始序
列有序，执行n-1趟，但每一趟只比较一次，移动元素两 次，总的比较次数是
(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O( n)。最
坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂
度为O (n
2
)。
<2>冒泡排序：
当原始数据正向有序时，冒泡排序出现最好情
况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间
复杂度是O(n )。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进
行n-1趟排序，第i趟作(n-i) 次关键字间的比较，并且需执行(n-i)次元素交
换，所以，比较次数为：因此,最坏情况下的时间复 杂度为O(n
2
)


<3>快速排序：如果每一次分划操作后， 左、右两个子序列的长度基本相等，
则快速排序的效率最高，其最好情况时间复杂度为O(nlog2
n)；反之，如果每次
分划操作所产生的两个子序列，其中之一为空序列，此时，快速排 序效率最低，
其最坏情况时间复杂度为O(n
2
)。如果选择左边第一个元素为主元， 则快速排序
的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间
复杂度 为O(nlog
2
n)。
<4>堆排序：堆排序的时间，主要由建立初始堆和反复重 建堆这两部分的时
间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为< br>O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次
数较多，所 以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时
间复杂度O(nlogn)。

<5>归并排序：在最佳、平均、最差情况下，时间复杂度为?(n log n)，不足的就是需要两倍的空间代价，当输入的待排序数据存储在链表中时，归并排
序是一个很好的选择.





（5）函数的调用关系图



主程序



用户输入排序的元素
产生n个随机数
对随机数进行排序
输出



（6）输入和输出的格式
输入 请输入排序规模：提示输入
等待输入



输出 插入排序算法对n个随机数排序时间为
插入排序算法对n个随机数交换次数为

冒泡排序算法对n个随机数排序时间为
冒泡排序算法对n个随机数交换次数为

堆排序算法对n个随机数排序时间为
堆排序算法对n个随机数交换次数为

合并排序算法对n个随机数排序时间为
合并排序算法对n个随机数交换次数为

快速排序算法对n个随机数排序时间为
快速排序算法对n个随机数交换次数为

排序后，前50个有序元素为：






四、用户使用说明（可选）
1、本程序的运行环境为DOS操作系统，执行文件为
2、运行程序时
输入 请输入排序规模：提示输入
等待输入




输出 插入排序算法对n个随机数排序时间为
插入排序算法对n个随机数交换次数为

冒泡排序算法对n个随机数排序时间为
冒泡排序算法对n个随机数交换次数为

堆排序算法对n个随机数排序时间为
堆排序算法对n个随机数交换次数为

合并排序算法对n个随机数排序时间为
合并排序算法对n个随机数交换次数为

快速排序算法对n个随机数排序时间为
快速排序算法对n个随机数交换次数为

排序后，前50个有序元素为：


五：实现

图1 控制台程序


实验结果：
实验分别实现插入排序、冒泡排序、堆排序、 合并排序、快速排序，以不同
规模（100，1000，2000，5000，10000，10000 0个数据）的随机数作为测试数
据集，实验结果截图如下：

排序规模为100



排序规模为：1000

排序规模为：2000



排序规模为：5000



排序规模为：10000


排序规模为：100000
（六）算法性能分析
在程序中我们根据数据规模的不同产生不同的随机整型数组，然后分别让 不
同的排序算法来进行从小到大的排序。这里需要注意的是：每种排序算法在相
同的输入规模中 原始无序数据都是一样的。例如五种排序算法要对长度为100
的无序数组进行排序，它们所要排序的无 序数组都是一样的，我们以此来保证
实验的公正性。在这里我们认为比较次数是排序算法的主要操作，因 此我们在
每个排序算法中加入计数器来记录排序过程中的比较次数，以此来作为对算法
性能分析 的主要参数（排序时间作为辅助参数）。表1为在输入规模分别为100，
1000，2000，500 0，10000，100000时各个算法的元素交换次数。表2为在输入
规模分别为100，1000 ，2000，5000，10000，100000时各个算法的排序时间。

100 1000 2000 5000 10000 100000

排序
规模
（n）
算法
插入2782 246255 983211 6266052 24870816 2509250617
排序
冒泡2684 242011 963158 5956790 22452014 1127169842
排序
堆排1000 16480 37063 106026 231903
序
合并555 8719
排序
快速599 10377 23702 71431
排序
表1 排序算法比较次数性能比较


100
排序
规模
（n）
算法
1000 2000 5000 10000 100000
152879 1946925
19432 55301 120409 1536596
2985016

插入0.0452 3.0583
排序
12.1263 58.2854 177.54 16694
冒泡0.1007 9.46976 21.3535 133.777 526.971 42698.7
排序
堆排0.0737 0.579467 1.28444 3.59577 8.03182 102.961
序
合并0.3709 2.19143 4.11925 11.6794 20.8016 192.61
排序
快速0.0335 0.202953 0.428768 1.3171 2.69531 29.9569
排序
表2 排序算法排序时间比较（单位ms）

为了 直观起见，根据实验数据画出各种排序算法在不同输入规模下交换次数的
变化趋势图如图2所示：

图2排序算法交换次数趋势图


由上图我们基本上看出插入排 序和冒泡排序的比较次数随输入规模的呈非线性
增长，而后三种排序方法——堆排序，合并排序，快速排 序的比较次数随输入
规模的增长基本呈线性变化趋势。

根据实验数据画出各种排序算法在不同输入规模下交换次数的变化趋势图如图
3所示：

图3排序算法排序时间趋势图（单位：ms）

实验结果与我们对这五种 算法的性能理论
分析基本吻合：插入排序与冒泡排序的时间复杂
度为O(n*n)，而后三种排 序算法的时间复杂度
为O(nlogn)。图4还显示出虽然冒泡排序和插入
排序的时间复杂度 相同，但插入排序的性能仍然
比冒泡排序好，尤其在排序时间方面。
（七）结论

最后得出结论：
时间性能上，
快速排序 > 堆排序 > 合并排序 > 插入排序 > 冒泡排序
交换次数上，
合并排序 > 快速排序 > 堆排序 > 冒泡排序 > 插入排序




(八)心得
作 为拿来复习的一个报告还是蛮有成就感的，但是输入1000000个数据的时
候等得太久，实在等不出 结果，而且放入值太大不方便作图，于是就不参与数
据分析，但是估计结果应该相同。以前不懂排序只会 用冒泡，因为冒泡排序是
接触编程的第一个排序，印象很深刻，而且几乎不会用错，当数据比较大时它< br>的弊端就真的出现了。本以为这个实验还是比较好做的，排序几乎都会，连助
教都说一句你这个选 题太没难度了。但是平心而论，真正实现起来还真是问题
多多，首先是怎么样调用时间的问题，这也是第 一个先想的问题，本来打算就
只比较交换次数和比较次数的，但是这些其实没有比时间更直观的反应排序 的
效率。寻找半天无果本来都打算放弃了，结果竟然有一个回复贴说
QueryPerform anceCounter函数，于是就发现这个问题可以解决了。结果是想象
的有点偏差，没想到堆排序 的速度也能这么快，合并排序的次数会那么少。本
以为快速排序就是万能的了，看来想多了。或许以后在 研究算法方面的确需要
好好分析效率，数据结构的确是一门很有用的学科，以后不能丢弃。