·您当前的位置:首页 > 技术教程 > AS2与AS3技术 >

[AS3]as3排序方法和算法

时间:2013-08-14 15:54CuPlayer.com
对于数据的处理工作,排序是其最基本的运算之一。在当今的计算机系统中,花费在排序上的时间占系统CPU运行时间的很大比重

一、概论
对于数据的处理工作,排序是其最基本的运算之一。在当今的计算机系统中,花费在排序上的时间占系统CPU运行时间的很大比重。有资料表 明,在一些商用计算机上,在排序上的CPU时间达到20%至60%。为了提高计算机的工作效率,人们提出了各种各样的排序方法和算法。这些算法有力地发 展、并充分地展示了算法设计的某些重要原则和高超技巧。因此,对于计算专业人员来说掌握排序算法是十分重要的。

二、排序算法简介
本次课程中我们将介绍六种排序方法:插入排序,选择排序,冒泡排序,希尔排序,快速排序及二路归并。

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

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

<3>冒泡排序(Bubble Sort):将相邻的两个数据元素按关键字进行比较,如果反序,则交换。对于一个待排序的数据元素序列,经一趟排序后最大值数据元素移到最大位置,其它值 较大的数据元素向也最终位置移动,此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止,则已完成对记录的排序。

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

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

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

热门文章推荐

请稍候...

保利威视云平台-轻松实现点播直播视频应用

酷播云数据统计分析跨平台播放器