数据结构之排序算法性能研究比较.docx
《数据结构之排序算法性能研究比较.docx》由会员分享,可在线阅读,更多相关《数据结构之排序算法性能研究比较.docx(11页珍藏版)》请在冰点文库上搜索。
数据结构之排序算法性能研究比较
2.1直接插入排序
假设待排序的n个记录{R0,R1,…,Rn}顺序存放在数组中,直接插入法在插入记录Ri(i=1,2,…,n-1)时,记录被划分为两个区间[R0,Ri-1]和[Ri+1,Rn-1],其中,前一个子区间已经排好序,后一个子区间是当前未排序的部分,将关键码Ki与Ki-1Ki-2,…,K0依次比较,找出应该插入的位置,将记录Ri插,然后将剩下的i-1个元素按关键词大小依次插入该有序序列,没插入一个元素后依然保持该序列有序,经过i-1趟排序后即成为有序序列。
每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。
2.1.2排序过程
初始数据:
10325208
第一趟:
[310]25208(将前两个数据排序)
第二趟:
[31025]208(将25放入前面数据中的适当位置)
第三趟:
[3102025]8(将20放入适当的位置)
第四趟:
[38102025](将8放入适当的位置)
2.1.3时间复杂度分析
直接插入排序算法必须进行n-1趟。
最好情况下,即初始序列有序,执行n-1趟,但每一趟只比较一次,移动元素两次,总的比较次数是(n-1),移动元素次数是2(n-1)。
因此最好情况下的时间复杂度就是O(n)。
最坏情况(非递增)下,最多比较i次,因此需要的比较次数是:
所以,时间复杂度为O(n2)。
2.2直接选择排序
待排序的一组数据元素中,选出最小的一个数据元素与第一个位置的数据元素交换;然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换,循环到只剩下最后一个数据元素为止,依次类推直到所有记录。
第一趟第n个记录中找出关键码最小的记录与第n个记录交换;第二趟,从第二个记录开始的,2-1个记录中再选出关键码最小的记录与第二个记录交换;如此,第i趟,则从第i个记录开始的n-i+l个记录中选出关键码最小的记录与第i个记录交换,直到所有记录排好序。
2.2.2排序过程
初始数据[4938659776132749]
第一趟排序后13[38659776492749]
第二趟排序后1327[659776493849]
第三趟排序后132738[9776496549]
第四趟排序后13273849[49976576]
第五趟排序后1327384949[979776]
第六趟排序后132738494976[7697]
第七趟排序后13273849497676[97]
最后排序结果1327384949767697
2.2.3时间复杂度分析
该算法运行时间与元素的初始排列无关。
不论初始排列如何,该算法都必须执行n-1趟,每趟执行n-i-1次关键字的比较,这样总的比较次数为:
所以,简单选择排序的最好、最坏和平均情况的时间复杂度都为O(n2)。
2.3冒泡排序
在每一趟冒泡排序中,依次比较相邻的两个关键字大小,若为反序咋交换。
经过一趟起泡后,关键词大的必须移到最后。
按照这种方式进行第一趟在序列(I[0]~I[n-1])中从前往后进行两个相邻元素的比较,若后者小,则交换,比较n-1次;第一趟排序结束,最大元素被交换到I[n-1]中,下一趟只需在子序列(I[0]~I[n-2])中进行;如果在某一趟排序中未交换元素,则不再进行下一趟排序。
将被排序的记录数组J[1..n]垂直排列,每个记录J[i]看作是重量为J[i].key的气泡。
根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:
凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。
如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止,最后可完成。
2.3.2排序过程
将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。
根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:
凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。
如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
(1)初始
R[1..n]为无序区。
(2)第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。
即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key 第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。
(3)第二趟扫描
扫描R[2,…,n]。
扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……,最后,经过n-1 趟扫描可得到有序区R[1…n]。
第i趟扫描时,R[1…i-1]和R[i…n]分别为当前的有序区和无序区。
扫描仍是从底部向上直至该区顶部。
扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1…i]变为新的有序区。
初始数据763246805546*
第一趟排序后327646805546*
第二趟排序后324676805546*
第三趟排序后324676805546*
第四趟排序后324676558046*
第五趟排序后3246765546*80
32465546*7680第二趟排序结果
324646557680第三趟排序结果
324646*557680第四趟排序结果
324646*557680第五趟排序结果
2.3.3时间复杂度分析
当原始数据正向有序时,冒泡排序出现最好情况。
此时,只需进行一趟排序,作n-1次关键字比较,因此最好情况下的时间复杂度是O(n)。
当原始数据反向有序时,冒泡排序出现最坏情况。
此时,需进行n-1趟排序,第i趟作(n-i)次关键字间的比较,并且需执行(n-i)次元素交换,所以,比较次数为:
因此,最坏情况下的时间复杂度为O(n2)。
2.4Shell排序
Shell排序又称缩小增量排序,Shell排序法是以创建者DonaldShell的名字命名的.Shell排序法是对相邻指定距离(称为间隔)的元素进行比较,已知到使用当前间隔进行比较的元素都按顺序排序为止.Shell把间隔缩小一半,然后继续处理,当间隔最终变为1,并且不再出现变化时,Shell排序也就完成了其处理过程.先取一个整数d12.4.2排序过程
先取一个正整数d1 初始数据:
49386597761327485504
一趟结果(d=5):
13274855044938659776
二趟结果(d=3):
13044838274955659776
三趟结果(d=1):
04132738484955657697
2.4.3时间复杂度分析
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。
所以,希尔排序的时间复杂度会比o(n2)好一些。
由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
所以希尔排序是不稳定的,其时间复杂度为o(n2)。
2.5堆排序
堆排序思想很简单,就是每次把关键词调整为堆,取出堆顶元素与堆中最后一个元素交换,同时令堆得大小减一,把剩余的一些元素重新调整为堆,重复此过程,直到堆中只剩一个元素,n个关键字序列kl,k2,…,kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):
(l)ki<=k2i且ki<=k2i+1或
(2)ki>=k2i且ki>=k2i+1。
若将此序列所存储的向量R[1…n]看作是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:
树中非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。
注意:
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆,类似地可定义k叉堆。
2.5.2排序过程
堆排序是一树形选择排序。
堆排序的特点是:
在排序过程中,将R[1…n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之问的内在关系,在当前无序中选抒关键字最大(或最小)的记录。
下面将从实际数据中演示其排序中的各个操作。
原始数组:
22537211344411152831065
第一步,从树顶到树叶把数填充进入,建立堆。
红色为下一次交换的两个数(序列)。
使记录递增有序,进一步排序。
第一次交换:
第二次交换:
第三次交换:
第四次交换:
第五次交换:
第六次交换:
第七次交换:
第八次交换:
第九次交换:
全程交换完成,得到最小值为3并且输出它。
从序列中删除3,重新建立堆。
以次循环,直到全部输出完成为止。
2.5.3时间复杂度分析
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlogn)。
堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
堆排序是不稳定的,算法时间复杂度O(nlogn)。
2.6快速排序
首先我们选择一个中间值middle(程序中我们可使用数组中间值),把比中问值小的放在其左边,比中问值大的放在其右边。
由于这个排序算法较复杂,我们先给出其进行一次排序的程序框架。
在待排序的个记录中任意取一个记录(通常取第一个记录)为区分标准,把所有小于该排序的记录移到左边,把所有大于该排序码的记录移到右边,中级放所选记录,为一趟快速排序。
然后对前后两个子序列分别重新上述过程,直到所有记录都排好序。
对任意给定的序列中某个元素,经过一趟排序后,将原序列分割成两个子序列(Rp(0),Rp
(1),…,Rp(s-1))和(Rp(s+1),Rp(s+2),…,Rp(n-1)),其中前一个子序列中的所有元素的关键词均小于或等于该元素的关键词值Kp(s),后一个子序列中元素的关键词均大于或等于Kp(s)。
称该元素Rp(s)为分割元素,子序列(Rp(0),Rp
(1),…,Rp(s-1))为其低端序列,(Rp(0),Rp
(1),…,Rp(s-1))为其高端序列。
很明显,以后只需对低端和高端序列分别进行快速排序,直到子序列为空或只有一个元素时结束,最后得到有序序列。
总之,每趟使表的第一个元素放在适当位置,将表两分,再对子表进行同样的递归划分,直至划分的子表长度为1。
2.6.2排序过程
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。
一躺快速排序的算法是:
1)设置两个变量I、J,排序开始的时候I=1,J=N;
2)以第一个数组元素作为关键数据,赋值给X,即X=A[1];
3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,两者交换;
4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,两者交换;
5)重复第3、4步,直到I=J;
例如:
待排序的数组A的值分别是:
A[1]A[2]A[3]A[4]A[5]A[6]A[7]:
49386597761327
进行第一次交换后:
27386597761349
进行第二次交换后:
27384997761365
进行第三次交换后:
27381397764965
进行第四次交换后:
27381349769765
此时再执行第三步的时候就发现I=J,从而结束一躺快速排序,那么经过一躺快速排序之后的结果是:
27381349769765,即所以大于49的数全在49的后面,所以小于49的数全部在49的前面。
快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如下所示:
初始状态:
{49386597761327}
进行一次快速排序之后划分为:
{273813}49{769765}
分别对前后两部分进行快速排序:
{13}27{38};{97}76{65}
2.6.3时间复杂度分析
如果每一次分划操作后,左、右两个子序列的长度基本相等,则快速排序的效率最高,其最好情况时间复杂度为O(nlog2n);反之,如果每次分划操作所产生的两个子序列,其中之一为空序列,此时,快速排序效率最低,其最坏情况时间复杂度为O(n2)。
如果选择左边第一个元素为主元,则快速排序的最坏情况发生在原始序列正向有序或反向有序时。
快速排序的平均情况时间复杂度为O(nlog2n)。
排序方法
平均情况
最好情况
最坏情况
稳定性
辅助空间
直接插入排序
O(n2)
O(n)
O(n2)
稳定
O
(1)
希尔排序
O(nlog2n)~O(n2)
O(n1.3)
O(n2)
不稳定
O
(1)
起泡排序
O(n2)
O(n)
O(n2)
稳定
O
(1)
快速排序
O(nlog2n)
O(nlog2n)
O(n2)
不稳定
O(log2n)~O(n)
简单选择排序
O(n2)
O(n2)
O(n2)
稳定
O
(1)
堆排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
不稳定
O
(1)
归并排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
稳定
O(n)