基本排序算法比较与选择 二叉排序算法

基本排序算法比较与选择 二叉排序算法
前几天应一个朋友的要求,帮他完成了数据排序的一个作业。觉得很有给大家参考的价值,所以经过他同意,作了些修改帖了上来。源代码见附件,代码中实现了8种排序算法,各算法名称见下表或见源码。运行程序时,将需要你输入一数值,以确定对多少随机数进行排序。然后将会显示各排序算法的耗时。并且你可选择时否进行正序和反序测试。

由于水平有限,可能存在一些错误,还请各位多多指点!

通过实验我们可将结果列入下表。

以下是VC6.0(Release)+win2000pro+128MDDR+P4(1.6G)

因为在多任务操作系统下,系统将进行进程序调度,影响实验结果。以下是经过稍微修正过的值。如果要取得更准确的值,我们得多次实验求其平均值。

排序算法实验比较(单位:秒)

n

方法

1K

10K

100K

200K

100K

正序

逆序

冒泡排序

0

0.422

44.790

188.462

0

31.459

冒泡排序2

0

0.281

30.335

131.771

0

27.568

快速排序

0

0

0.016

0.047

5.095

7.002

直接选择排序

0

0.141

16.878

79.332

16.785

33.242

堆排序

0

0

0.031

0.109

0.031

0.015

直接插入排序

0

0.047

8.705

57.800

0

24.865

Shell排序

0

0

0.047

0.110

0.015

0.015

归并排序

0

0

0.031

0.094

0.032

0.032

基数排序

0

0

0.47

0.109

0.047

0.046

算法与结果联合分析

冒泡排序:在最优情况下只需要经过n-1次比较即可得出结果,(这个最优情况那就是序列己是正序,从100K的正序结果可以看出结果正是如此),但在最坏情况下,即倒序(或一个较小值在最后),下沉算法将需要n(n-1)/2次比较。所以一般情况下,特别是在逆序时,它很不理想。它是对数据有序性非常敏感的排序算法。

冒泡排序2:它是冒泡排序的改良(一次下沉再一次上浮),最优情况和最坏情况与冒泡排序差不多,但是一般情况下它要好过冒泡排序,它一次下沉,再一次上浮,这样避免了因一个数的逆序,而造成巨大的比较。如(2,3,4,…,n-1,n,1),用冒泡排序需要n(n-1)/2次比较,而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次,第一轮1将上移一位,第二轮1将移到首位,第三轮将发现无数据交换,序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法,只适合于数据基本有序的排序。

快速排序:它同样是冒泡排序的改进,它通过一次交换能消除多个逆序,这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下,它的排序时间复杂度为O(nlog2n)。即每次划分序列时,能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时,一串为空,另一串为m-1(程序中的100K正序和逆序就正是这样,如果程序中采用每次取序列中部数据作为划分点,那将在正序和逆时达到最优)。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢,这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”,在理论上讲,如果每次能均匀划分序列,它将是最快的排序算法,因此称它作快速排序。虽然很难均匀划分序列,但就平均性能而言,它仍是基于关键字比较的内部排序算法中速度最快者。

直接选择排序:简单的选择排序,它的比较次数一定:n(n-1)/2。也因此无论在序列何种情况下,它都不会有优秀的表现(从上100K的正序和反序数据可以发现它耗时相差不多,相差的只是数据移动时间),可见对数据的有序性不敏感。它虽然比较次数多,但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。

堆排序:由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤:-是建堆,二是排序(调整堆)。所以一般在小规模的序列中不合适,但对于较大的序列,将表现出优越的性能。

直接插入排序:简单的插入排序,每次比较后最多移掉一个逆序,因此与冒泡排序的效率相同。但它在速度上还是要高点,这是因为在冒泡排序下是进行值交换,而在插入排序下是值移动,所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较,在最坏情况下,将需要n(n-1)/2次比较。

希尔排序:增量的选择将影响希尔排序的效率。但是无论怎样选择增量,最后一定要使增量为1,进行一次直接插入排序。但它相对于直接插入排序,由于在子表中每进行一次比较,就可能移去整个经性表中的多个逆序,从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法,所以对数据有序敏感。

归并排序:归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。但可改造成索引操作,效果将非常出色。

基数排序:在程序中采用的是以数值的十进制位分解,然后对空间采用一次性分配,因此它需要较多的辅助空间(10*n+10), (但我们可以进行其它分解,如以一个字节分解,空间采用链表将只需辅助空间n+256)。基数排序的时间是线性的(即O(n))。由此可见,基数排序非常吸引人,但它也不是就地排序,若节点数据量大时宜改为索引排序。但基数排序有个前提,要关键字能象整型、字符串这样能分解,若是浮点型那就不行了。

按平均时间将排序分为类:

(1) 平方阶(O(n2))排序

各类简单排序,例如直接插入、直接选择和冒泡排序;

(2) 线性对数阶(O(nlog2n))排序

如快速排序、堆排序和归并排序;

(3) O(n1+§))排序

§是介于0和1之间的常数。希尔排序便是一种;

(4) 线性阶(O(n))排序

本程序中的基数排序,此外还有桶、箱排序。

排序方法的选择

因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法很重要

(1)若n较小,可采用直接插入或直接选择排序。

当记录规模较小时,直接插入排序较好,它会比选择更少的比较次数;

但当记录规模较大时,因为直接选择移动的记录数少于直接插人,所以宜用选直接选择排序。

这两种都是稳定排序算法。

(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机,原因见上的快速排序分析);这里快速排序算法将不稳定。

(3)若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。

归并排序是稳定的排序算法,但它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

(4)特殊的箱排序、基数排序

它们都是一种稳定的排序算法,但有一定的局限性:

1、关键字可分解。

2、记录的关键字位数较少,如果密集更好

3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

前几天应一个朋友的要求,帮他完成了数据排序的一个作业。觉得很有给大家参考的价值,所以经过他同意,作了些修改帖了上来。源代码见附件,代码中实现了8种排序算法,各算法名称见下表或见源码。运行程序时,将需要你输入一数值,以确定对多少随机数进行排序。然后将会显示各排序算法的耗时。并且你可选择时否进行正序和反序测试。

由于水平有限,可能存在一些错误,还请各位多多指点!

通过实验我们可将结果列入下表。

以下是VC6.0(Release)+win2000pro+128MDDR+P4(1.6G)

因为在多任务操作系统下,系统将进行进程序调度,影响实验结果。以下是经过稍微修正过的值。如果要取得更准确的值,我们得多次实验求其平均值。

排序算法实验比较(单位:秒)

n

方法

1K

10K

100K

200K

100K

正序

逆序

冒泡排序

0

0.422

44.790

188.462

0

31.459

冒泡排序2

0

0.281

30.335

131.771

0

27.568

快速排序

0

0

0.016

0.047

5.095

7.002

直接选择排序

0

0.141

16.878

79.332

16.785

33.242

堆排序

0

0

0.031

0.109

0.031

0.015

直接插入排序

0

0.047

8.705

57.800

0

24.865

Shell排序

0

0

0.047

0.110

0.015

0.015

归并排序

0

0

0.031

0.094

0.032

0.032

基数排序

0

0

0.47

0.109

0.047

0.046

算法与结果联合分析

冒泡排序:在最优情况下只需要经过n-1次比较即可得出结果,(这个最优情况那就是序列己是正序,从100K的正序结果可以看出结果正是如此),但在最坏情况下,即倒序(或一个较小值在最后),下沉算法将需要n(n-1)/2次比较。所以一般情况下,特别是在逆序时,它很不理想。它是对数据有序性非常敏感的排序算法。

冒泡排序2:它是冒泡排序的改良(一次下沉再一次上浮),最优情况和最坏情况与冒泡排序差不多,但是一般情况下它要好过冒泡排序,它一次下沉,再一次上浮,这样避免了因一个数的逆序,而造成巨大的比较。如(2,3,4,…,n-1,n,1),用冒泡排序需要n(n-1)/2次比较,而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次,第一轮1将上移一位,第二轮1将移到首位,第三轮将发现无数据交换,序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法,只适合于数据基本有序的排序。

快速排序:它同样是冒泡排序的改进,它通过一次交换能消除多个逆序,这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下,它的排序时间复杂度为O(nlog2n)。即每次划分序列时,能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时,一串为空,另一串为m-1(程序中的100K正序和逆序就正是这样,如果程序中采用每次取序列中部数据作为划分点,那将在正序和逆时达到最优)。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢,这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”,在理论上讲,如果每次能均匀划分序列,它将是最快的排序算法,因此称它作快速排序。虽然很难均匀划分序列,但就平均性能而言,它仍是基于关键字比较的内部排序算法中速度最快者。

直接选择排序:简单的选择排序,它的比较次数一定:n(n-1)/2。也因此无论在序列何种情况下,它都不会有优秀的表现(从上100K的正序和反序数据可以发现它耗时相差不多,相差的只是数据移动时间),可见对数据的有序性不敏感。它虽然比较次数多,但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。

堆排序:由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤:-是建堆,二是排序(调整堆)。所以一般在小规模的序列中不合适,但对于较大的序列,将表现出优越的性能。

直接插入排序:简单的插入排序,每次比较后最多移掉一个逆序,因此与冒泡排序的效率相同。但它在速度上还是要高点,这是因为在冒泡排序下是进行值交换,而在插入排序下是值移动,所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较,在最坏情况下,将需要n(n-1)/2次比较。

希尔排序:增量的选择将影响希尔排序的效率。但是无论怎样选择增量,最后一定要使增量为1,进行一次直接插入排序。但它相对于直接插入排序,由于在子表中每进行一次比较,就可能移去整个经性表中的多个逆序,从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法,所以对数据有序敏感。

归并排序:归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。但可改造成索引操作,效果将非常出色。

基数排序:在程序中采用的是以数值的十进制位分解,然后对空间采用一次性分配,因此它需要较多的辅助空间(10*n+10), (但我们可以进行其它分解,如以一个字节分解,空间采用链表将只需辅助空间n+256)。基数排序的时间是线性的(即O(n))。由此可见,基数排序非常吸引人,但它也不是就地排序,若节点数据量大时宜改为索引排序。但基数排序有个前提,要关键字能象整型、字符串这样能分解,若是浮点型那就不行了。

按平均时间将排序分为类:

(1) 平方阶(O(n2))排序

各类简单排序,例如直接插入、直接选择和冒泡排序;

(2) 线性对数阶(O(nlog2n))排序

如快速排序、堆排序和归并排序;

(3) O(n1+§))排序

§是介于0和1之间的常数。希尔排序便是一种;

(4) 线性阶(O(n))排序

本程序中的基数排序,此外还有桶、箱排序。

排序方法的选择

因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法很重要

(1)若n较小,可采用直接插入或直接选择排序。

当记录规模较小时,直接插入排序较好,它会比选择更少的比较次数;

但当记录规模较大时,因为直接选择移动的记录数少于直接插人,所以宜用选直接选择排序。

这两种都是稳定排序算法。

(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机,原因见上的快速排序分析);这里快速排序算法将不稳定。

(3)若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。

归并排序是稳定的排序算法,但它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

(4)特殊的箱排序、基数排序

它们都是一种稳定的排序算法,但有一定的局限性:

1、关键字可分解。

2、记录的关键字位数较少,如果密集更好

3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

  

爱华网本文地址 » http://www.413yy.cn/a/25101012/135326.html

更多阅读

等额本金和等额本息的区别与选择 提前还贷 等额本金

等额本金和等额本息的区别与选择——简介买房也可以说是终身大事,对于大部分朋友来说,买房子要向银行贷款,而跟银行借贷款有两种方式:等额本金法和等额本息法,很多人因为不清楚两者的区别和利息的算法,导致在贷款买房的时候吃大亏,下面笔者

平衡二叉树的生成理论 平衡二叉树

本文由作者收集整理所得,作者不保证内容的正确行,转载请标明出处。作者:关新全1、AVL的插入算法描述在平衡的二叉排序树T上插入一个关键码为kx的新元素,递归算法可描述如下:(一)若T为空树,则插入一个数据元素为kx的新结点作为T的根结

传感器产品知识:磁性开关两线制与三线制的比较与选择

【无触点式磁性开关】又名:固态电子型磁性开关。原理:利用半导体加放大回路构成开关形式,问题:存在漏电流、内部电压降等。【两线制磁性开关】特点:磁性开关的负载直接接在电源的导线上。例如:SME-10M-DS-24V-E-2,5-L-OE【三线制磁性开关

二叉树的应用详解 二叉树遍历代码详解

概述:平衡树——特点:所有结点左右子树深度差≤1排序树——特点:所有结点“左小右大字典树——由字符串构成的二叉排序树判定树——特点:分支查找树(例如12个球如何只称3次便分出轻重)带权树——特点:路径带权值(例如长度)最优树——是带权路

二叉排序树的实现 二叉排序树的查找

二叉排序树的实现 分类: 数据结构 2012-08-12 20:42 265人阅读 评论(0) 收藏 举报nullinsertdeletetreeclass算法二叉排序树(Binary Sort Tree)又称二叉查找树。 它是一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结

声明:《基本排序算法比较与选择 二叉排序算法》为网友抠脚女神分享!如侵犯到您的合法权益请联系我们删除