检测算法排序（共7篇）
检测算法排序 篇1
1 引言
1.1 有向无环图与拓扑序列
集合及在上的偏序关系[1]可以用有向无环图(DAG:Directed Acyclic Graph)表示[2]。其中,V是G的顶点集合,E是有向边的集合,代表了上的偏序关系。连接V中的顶点i,的边{i,j}表示偏序关系R中的一个偏序r。拓扑序列是由某个具有偏序关系的集合得到的该集合上的一个全序序列。对于一个有向无环图,其拓扑序列是顶点的线性排列P,连接顶点的边{i,j}意味着在序列P中顶点i的出现要先于顶点j。而构造这样的线性序列的过程称为拓扑排序[1,2,3,4]。有向图当且仅当无环时才可以拓扑排序,且通常有多个解。
1.2 拓扑排序的基本算法
拓扑排序理论的研究最早是在项目管理日程安排中的计划评审技术(PERT:Program Evaluation and Review Technique的相关背景下出现的(Jarnagin 1960)[5]。拓扑排序算法最早则是由Kahn(1962)提出来的[6]。在计算机科学中,这种类型的应用也出现在计算机指令调度,电子表格中在重新计算公式值时的公式单元评价结果的排序,逻辑综合,执行编译文件中的编译任务的顺序的测定和串行化以及在连接器中的符号依赖关系的解析等。
拓扑排序的基本算法有:源点消去算法、广度优先搜索算法和深度优先搜索算法3种。
(1)源点消去算法又称无前驱顶点优先算法,是最经典、最简单的,也是教科书中最常介绍的关于有向无环图的拓扑排序算法。该算法的伪代码如下所示[7]:
上述伪代码所述的算法的输入必须是有向无环图,其输出序列是图的某一个拓扑序列。若将其中的第一条伪代码修改为如下形式:
则算法输入就允许是一个有向图(无论是否有环)。只需通过判定输出序列中的元素数量是否与图的顶点的数量相同,即可判定图是否有环。即输出序列中的元素数量小于图中顶点的数量,则可判定图中有环;若相等,则图中无环,输出的就是图的一个拓扑序列。
(2)广度优先搜索算法[8,9]常常用于图的最小生成树或顶点之间的最短路径的搜索,当然也能够用于拓扑排序[10]。从本质上来讲,该方法与源点消去算法的基本原理是一样的,是一种更有效的改进方法。广度优先搜索算法首先要在有向无环图中找出所有无入边(入度为0)的顶点(源点),插入到结构S中(结构S可以是集合、队列或是堆栈,但最常用的还是队列)。该算法的伪代码如下所示[11]:
该算法允许输入一个有向图(无论是否有环)。算法的最后的部分给出了是否有环的判定方法。
(3)深度优先算法[8,10,11,12]最早是由Tarjan(1972)发表的。该算法采用递归调用,代码简洁高效,也是针对大规模网络中各种动态拓展研究中最常采用的算法。其伪代码如下所示[11]:
其中visit()是递归函数。采用深度优先搜索算法,首先添加到L中的是首次沿搜索路径查找到的深度优先搜索树末端(该路径最深处的)顶点。L中的结果是拓扑序列的逆序。求逆后就是所求有向无环图的一个拓扑序列。
1.3 问题的提出
拓扑序列是有向无环图的顶点的一个线性序列,在这个序列中,顶点的排列顺序满足边所代表的偏序关系。只有有向无环图才具有拓扑序列。因此,拓扑排序算法的输入通常都是有向无环图。实际上,源点消去法和广度优先搜索法的输入可以是任意的有向图。在这两种算法中,若输入的是带环的有向图,环上的顶点都不是入度为0的顶点,因此不会添加到输出列表中。这样,就可以通过输出列表中顶点的数量判定有向图中是否存在环。若列表中的顶点数量等于有向图中的顶点数量,则有向图无环,列表中的序列就是该图的一个拓扑序列。反之,若列表中的顶点数量少于有向图中的顶点数量,就可以判定有向图中有环,不能进行拓扑排序。但是,对于深度优先搜索拓扑排序算法而言,其输入必须严格限定为有向无环图。这是因为除了有向图中存在的与其他部分不相连的独立的环外,1.2节描述的深度优先搜索算法都能遍历到图中由入度为0的顶点可达的所有顶点,并将遍历到的顶点添加到输出序列中,即这部分图中有环。因此无法像源点消除算法和广度优先搜索算法那样,利用输出序列中顶点的数量准确判定有向图中是否有环,从而无法判定由一个有向图产生的输出序列是否是一个拓扑序列。鉴于上述原因,往往需要先确认给定的有向图是无环的,然后才能使用深度优先搜索拓扑排序算法进行拓扑排序。这就为采用深度优先搜索拓扑排序算法带来了不便和负担。
确认一个有向图是否有环,通常采用的是判定有向图中强连通分量(SCC:Strongly Connected Component)的算法。有向图的强连通分量是图的最大强连通子图,如果一个有向图的每一个强连通分量都是由单个顶点构成的,则这个图就是一个有向无环图[13]。换句话说,当一个有向图的强连通分量的数量等于图的顶点的数量时,这个图就是一个有向图无环图。常见的求解有向图强连通分量的算法有3种:Kosaraju算法、Tarjan算法和Gabow算法,算法的处理过程都比较复杂。首先看看Tarjan算法,其伪代码如下所示[14]:
需要注意其中顶点v的两个变量:v.index和v.lowlink。该算法的处理过程是这样的:遍历V中的顶点v,若v尚未被搜索到,则对v调用递归函数strongconnect()。调用时,计数变量index的值将赋予v的两个变量v.index和v.lowlink,且index值随递归深度递增,同时将顶点v存入堆栈S中。然后,若v的每个邻接顶点w未曾搜索到则调用递归函数strongconnect(),且都是在递归函数返回时,又重新令v.lowlink取v.lowlink和w.lowlink中较小的值;若顶点w已被搜索(已在S中),同样令v.lowlink取v.lowlink和w.lowlink中较小的值。这样,随着递归调用的深入,若顶点v自身就是一个强连通分量(不是环上的顶点),v.index和v.lowlink的值必相等且随递归深度递增,若强连通分量是由若干顶点构成的环,则环上的顶点的v.index的值是随递归深度递增的,而环上所有顶点的lowlink的值均等于该环上值最小的深度优先搜索树根的lowlink。这样,环上的顶点只有“根”(环上第一个被搜索到的顶点)的index值和lowlink值相等,环上其余顶点的index和lowlink是不相等的。于是,每个非环上的顶点的index和lowlink值相等,是一个强连通分量,环上的顶点中只有称为“根”的顶点的index和lowlink值相等,代表一个强连通分量。从而获得了有向图的强连通分量的集合及其强连通分量的数量。显然,当一个有向图中的强连通分量的数量小于其顶点的数量时,说明图中有环。因此,可以利用该算法来判定一个有向图是否有环。
Gabow算法[15]与Tarjan算法的核心思想实质上是相通的。Gabow算法采用两个堆栈P和S来取代v.index和v.lowlink的操作[16],算法略为简洁一点。这两种算法在求解有向图的强连通分量时更受欢迎,因为只需要进行一次深度优先搜索。
如果要使用1.2节描述出的深度优先搜索算法对有向图进行拓扑排序,就需要先利用Tarjan算法或Gabow算法判定有向图中是否有环,然后在无环的情况下,再采用深度优先搜索算法进行拓扑排序。
值得一提的是Kosaraju算法。该算法的伪代码[17]如下所示:
该算法的设计思想非常巧妙。首先,采用深度优先搜索对有向图进行一次搜索,堆栈S中得到一个顶点的序列;其次,将有向图中有向边的方向倒置,获得一个转置的有向图;然后,依次从堆栈S中弹出一个顶点,若该顶点在转置的图中尚未被访问,则以这个顶点为根,对转置的有向图进行深度优先搜索,得到一棵深度优先搜索树,直到S中不存在顶点,就能获得深度优先搜索森林。森林中每棵树中的顶点集合就对应一个强连通分量,树的数量就是有向图的强连通分量的数量。同样,当强连通分量的数量等于图中顶点的数量时,这个图就是有向无环图。有趣的是:当图是一个有向图无环图时,则S中顶点的输出序列就是一个拓扑序列。遗憾的是:该算法还是需要进行两次深度优先搜索。
到目前为止,采用深度优先搜索的拓扑排序算法的都是针对有向无环图的,当输入的是带环的有向图时,则会给出错误的结果。因此,必须事先运行Tarjan算法、Gabow算法或其他可以检测有向图中是否有环的算法确认有向图无环后,才能再进行深度优先搜索拓扑排序。即使采用Kosaraju算法,也要进行两次深度优先搜索才能得到拓扑序列。Yufei Tao(2011)在其关于拓扑排序和深度优先搜索的课件中关于拓扑排序所使用的深度优先算法也只是针对有向无环图的,可喜的是关于拓扑排序算法正确性的证明中有“If v is grey(本文注:指顶点u的邻接顶点v是搜索路径上的顶点),then there is a cycle,i.e.,from v via another path to u,plus edge(u,v).This contradicts the fact that the graph is a dag.”[18]这样的描述,给出了在深度优先搜索过程中判定环的一个思路。下面将给出一个带有环检测功能的只需进行一次深度优先搜索的拓扑排序算法。
2 带环检测的深度优先搜索拓扑排序算法
2.1 伪代码表示
带环检测的深度优先搜索拓扑排序算法(以下简称CD_DfsTS)可以像源点消去拓扑排序算法和广度优先搜索拓扑排序算法一样,允许输入任意的有向图,在一次深度优先搜索的过程中同时完成环的检测和排序操作。一旦检测到图中有环时,立即终止搜索,返回环检出信息。在搜索最终结束后,根据输出序列中元素的数量就能判断图中是否有环。若图中无环,输出序列就是有向图的一个拓扑序列。参照1.2节的广度优先算搜索算法和深度优先搜索算法,给出CD_DfsTS算法的伪代码如下:
CD_DfsTS算法与1.2节描述的深度优先搜索拓扑排序算法基本相同,但由于输入的是无向图(可能有环),因此有一些不同之处:(1)每个顶点的访问情况不再是未被访问和已被访问两种,而是用3种标识,即:未被访问、已被访问和正在访问路径之上来表示。(2)递归函数要返回搜索是否正常完成的状态。(3)根据输出列表中元素的数量判定有向图是否有环。
有了第3种标识,算法中环的检测就变得非常简单了。首先,若顶点n尚未被访问,则先对n设置为在访问路径上,然后对n的所有邻接顶点m进行深度优先搜索的递归调用。若对m的递归调用是非正常返回时,不会将n添加到列表L中,直接返回false;若对n的所有邻接顶点的访问均正常返回,则将n添加到列表L中,这时才将n设置为已被访问过,然后返回true。其次,若顶点n的是正在访问路径之上的点,则判定有环,立即终止递归的调用,返回false。另外,算法隐含的是:若顶点n是已被访问过的,则不做任何处理,直接返回true。算法最终根据添加到L中的顶点的数量来判定图中是否有环。
2.2 算法分析
2.2.1 完备性与正确性分析
若算法的输入是一个有向无环图,从某一个不存在入边(入度为0)的顶点开始进行深度优先搜索的过程中,在搜索路径上遇到的顶点只能是未被访问的和已被访问的顶点两种情况,遇到的是未访问(unvisited)的顶点,才设置为在搜索路径上(on searching path),在递归返回时,再设置为被访问过(visited)。其过程与传统的深度优先搜索相比,除增加了设置在搜索路径上的标识及返回和判断搜索是否正常完成的状态以外,其余是完全相同的。对于输入的是有向无环图而言,算法的完备性与正确性毋庸置疑。因此,只需分析当输入的是带环的有向图的情况。
若输入是带环的有向图时,可分为两种情况:第一种情况:若有向图存在一个或一个以上的由独立的环构成的连通分量,由于这些环不存在入度为0的顶点,因此CD_DfsTS算法不会搜索到这些顶点,因此也不存在将其中的顶点添加到输出列表中的可能性,这样,输出列表中元素的数量必然小于有向图中顶点的数量。第二种情况:环是处在CD_DfsTS算法可搜索到的连通分量之中。算法搜索到环时会立即终止搜索,且在返回时不会再将顶点添加到输出列表中,输出列表中元素的数量也必然会小于有向图中顶点的数量。CD_DfsTS算法的搜索分为3种情况:(1)当搜索过程中遇到的是已被访问过的顶点时,则直接返回。(2)当搜索过程中遇到是未曾访问过的顶点时,则设为在搜索路径上,继续沿有向边搜索。当搜索到头时,依次返回,返回时将顶点存入列表L中,并将顶点设置为被访问过的。返回过程中遇到新的分支时,继续沿新的分支进行搜索。(3)搜索时遇到搜索路径上的顶点时,则判定检测到环,从而终止搜索。1和2与传统的深度优先搜索算法是相同的,因此只要证明搜索时遇到的搜索路径上的顶点是环上的顶点即可。
定理使用CD_DfsTS算法对有向图进行深度优先搜索时,若搜索过程中遇到当前搜索路径上的顶点,则该顶点是环上的顶点。
2.2.2 运行时间分析
分如下两种情况:
(1)输入的是有向无环图
在这种情况下,CD_DfsTS算法与传统的深度优先搜索算法相比,只是在返回前多了一次对顶点访问标识的设置,另外多了一次对递归调用返回状态的判定,通常认为这些操作所占用的时间都是可以忽略不计的。除此之外,对边的搜索和对顶点的访问处理和传统的深度优先搜索算法是完全相同的。因此,其运行所需时间也是[11]。
(2)输入的是有向有环图
2.3 算法的具体实现
这里给出一个用C++语言描述的已在实际应用中的CD_DfsTS算法的具体实现。
2.3.1 算法使用的数据结构
在深度优先搜索算法中关于边的邻接关系的最常使用的数据结构有邻接矩阵和邻接表。本文给出的关于边邻接关系的数据结构采用的是边集数组。在这里,边集数组中的元素采用的是由边的起始顶点的编号和终止顶点编号构成的结构体,初始化时,其中的元素按终止顶点编号为主序起始顶点编号为辅序的方式进行排序,以便在对该数组进行查询时,可以使某个顶点的邻接顶点按编号由小到大的顺序进行操作。
边集数组元素和数组的定义如下:
struct Edge//边信息结构体
顶点的标注(Label)可以是从0或从1开始的数字,也可以是字母甚至是单词或短语。因此,表示顶点的数据结构采用的是关于顶点标注的字符串数组,初始化时,元素的顺序是按顶点编号由小到大排列的。定义如下:
CStringArray m_saNodes;//顶点标注字符串数组
此外,还定义了对应每个顶点的访问标识和入度的整数数组指针,当程序初始化时,根据实际操作中顶点的多少动态地用new命令创建这两个整数数组,并将数组的地址赋给相应的指针,数组中的元素的顺序是按顶点编号由小到大排列的,m_Visited指向的数组中的元素都初始化为0(unvisited),m_Indegree指向的数组中元素初始化为对应顶点的入度。定义如下:
2.3.2 实现代码
3 结语
给出的CD_DfsTS算法不需要进行专门的有向图是否有环的检测和判定,为深度优先搜索拓扑排序提供了直接有效的方法。特别是对具有海量数据的有向图进行拓扑排序时,更加彰显其高效、简洁和便利,在实际应用中具有良好的效果。该算法对深度优先搜索算法做出了一个很有实际应用价值的拓展。
摘要：提出了一种带环检测功能的深度优先搜索拓扑排序算法,详细介绍了几种基本拓扑排序算法,分析了带环检测功能的深度优先搜索拓扑排序算法的意义和作用,并证明了该算法的完备性和正确性,给出了该算法的用C++编写的实现代码。
关键词：有向图,拓扑排序,深度优先搜索,环检测,强连通分量
简单选择排序算法的改进算法 篇2
排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。排序是将数据元素的任一序列, 重新排列成一个关键字有序的序列。基于比较和移动的排序算法具有通用性, 包括插入排序、选择排序、交换排序、归并排序、基数排序等等。各种排序的算法各具有优缺点, 但就其全面性能而言, 很难提出一种被公认的最好的方法。判断一个排序算法优劣的标准一般为时间复杂度、空间复杂度和稳定性。
一、简单选择排序算法
1、排序方法
选择排序 (Selection Sort) 是最符合人们思维习惯的一种排序方法。基本思路是每次从待排文件中挑选一个key值最小的 (或最大的) 记录放置于它应所在的位置。若待排文件长度为n, 则选择n-1趟便达到排序目的。选择排序一般又分为“直接选择排序”和“堆选择排序”。
2、直接选择排序的C语言算法
对上述算法进行优化, 在一趟中找到key, 如果该key就是i位置上的记录, 就不用交换。算法如下:
3、直接选择排序的算法分析
设排序文件的记录长度为n。算法中共进行了n-1趟选择, 每趟选择一个当前最小key的记录, 要经过n-i (1≤i≤n-1) 次的key比较, 故总的key比较次数C为:
另外, 当文件按key正序时, 记录移动次数等于0。而完全逆序时, 每趟选择后有3次记录移动, 所以最多移动次数为3 (n-1) 。故直接选择排序的时间复杂度T (n) =O (n2) 。直接选择排序属于稳定排序。
二、简单选择排序算法的改进算法
1、排序方法
基本思路是每次从待排文件中挑选一个key值最小的和一个key值最大的记录, 最小的放置于最前面, 最大的放置于最后面的位置。若待排文件长度为n, 则选择n/2趟便达到排序目的。
2、改进算法的C语言算法
3、改进算法的算法分析
设排序文件的记录长度为n。算法中共进行了n/2趟选择, 每趟选择一个当前最小key和最大key的记录, 要经过2 (n-2i) (1≤i≤n/2) 次的key比较, 故总的key比较次数C为:
C和=直ni∑/=1接2 (2选n择-排2i序) 的算法相比, 时间复杂度仍为T (n) =O (n2) , 但选择趟数减少了一半, 比较次数因为内循环中比较了2次, 和直接选择排序比较次数相当。
结束语
本文作者提出的上述改进的选择排序算法, 已通过在VC++6.0环境进行正确性测试。该算法是在简单选择排序的基础上提出来的改进算法, 提高效率是显而易见的。
摘要：排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。经典的排序包括:冒泡排序、选择排序、插入排序等等。本文以简单选择排序算法为基础, 对其进行改进, 得出与之具有更高的排序效率。
关键词：选择排序,改进算法
参考文献
[1]严蔚敏等:《数据结构 (C语言版) 》, 清华大学出版社, 2005.7。
[2]潭浩强:《C程序设计》, 清华清华大学出版社, 1999.4。
[3]方同祝、胡正国、田铮、金文凯:《一种节省空间的排序算法》, 《小型微型计算机系统》, Vol.26 No.7 July 2005。
[4]王敏:《改进的双向选择排序算法》, 《信息技术》, 2010年第9期。
最简单的排序算法 篇3
冒泡排序很简单,其原理也比较容易理解,但冒泡排序效率很差。世上也存在着许多效率很高的排序算法,但它们又都比较难理解。本文将介绍一种简单又“高效”的排序算法——珠排序, 大家不妨一起来玩玩。
空间站里玩排序
之所以要在“高效”两个字上打引号,是因为珠排序需要特殊的硬件支持。怎么个特殊法呢?为了方便说明问题,请想象在某个失重的空间站里,有一系列排列整齐、从1到n依次编了号码的透明管子,在管子里放入小球,小球的直径与管子横截面的直径相仿,只是略小一点,放球的规则如下:
1预先设定一系列未排序的数字, 如5、4、8、1、2、3、6、4。
2按预先设定的数字往管子里放球,如果是5,就放5个球,但并不是把5个球都放到1个管子中,而是依次放入1号到5号管子。如果是4,就把4个球依次放入1号到4号管子(如图1A、B)。
3在空间站的无引力真空环境中, 所有球都浮在空中,这时候若忽然施加重力,如用离心力模拟重力,于是所有的球都掉到了管子的底部,这时如果从侧面数球的个数,就能发现,先前的未排序数字,此时已经排序完成了(如图1C、D)。
这个实验当然不一定非要在太空站里做,把原本水平放置的管子竖立起来,产生的效果也是一样的。
记事本里玩排序
即便没有管子和小球,也可以在记事本中模拟珠排序的过程。
假设预设的未排序的数字为5、 4、8、1、2、3、6、4,第一个数字是5,则在记事本的第一列(注意是列而不是行) 写5个“1”,然后再在“1”下面多补充一些“0”,因为需要排列的数字最大是8,用8减去5得3,则最少补充3个“0”, 当然多补充点“0”是没关系的,接着要排序的数字是4,则在记事本第二列写4个“1”,再补充4个“0”,第三列8个“1”……以此类推(如图2)。
把所有的1和0按次序排列好后,用记事本中的“编辑—替换”功能,将文本中的“10”全部替换成“01”,反复这个全部替换过程,当不再有可替换的对象时,排序也就完成了(如图3)。 就这样,不用写一行代码就完成了排序。当然,若想要一本正经地把珠排序的代码写出来,也不是特别困难的事情, 这个任务就交给有兴趣的朋友自行探索了。
稳定快速排序算法研究 篇4
快速排序算法在所有的排序算法中是比较优秀的算法, 也是推荐的常用算法, 但它不完善, 即它是不稳定的排序算法。所谓排序算法的稳定性是指在待排序的记录序列中, 如果存在多个具有相同的关键字的记录, 若经过排序, 这些记录的相对次序保持不变, 即在原序列中, ri=rj, 且ri在rj之前, 而在排序后的序列中, ri仍在rj之前, 则称这种排序算法是稳定的, 否则称为不稳定的。在实际处理数据的过程中, 有时对排序的稳定性要求很高, 例如在处理类似有奖问卷问题时, 常根据问卷的成绩给部分人一定的奖品, 但有时相同成绩的人很多, 不可能都给奖品, 一般采取的是在成绩相同的情况下, 提交答案早的得奖品, 提交答卷晚的不得奖品, 这时就需要对成绩排序的算法是稳定的。
近年来, 不少学者提出各种改进的快速排序算法, 如三路基数快排[4]、高效快速排序算法[5]和超速快排[7]等, 都是增强了快速排序时间性能, 但对排序算法的稳定性基本上没有涉及。本文针对这一情况提出了一种稳定快速排序算法。
1 稳定快速排序算法设计
1.1 算法设计思想
经典的快速排序算法设计思想是通过一趟排序将待排记录分割成独立的二部分, 通过直接交换方式使其中一部分记录的关键字均比另一部分记录的关键字小, 然后再分别对这两部分的记录继续进行排序, 以达到整个序列有序。在把待排序的数据分割成两部分时, 需要把前后的数据直接进行交换, 这样的交换可能导致数据前后颠倒, 所以经典快速排序是不稳定的。要想使排序稳定, 需要改掉这种直接交换前后数据的办法, 采用其他方法处理。稳定快速排序算法就是这样一种改进算法。
稳定快速排序的设计思想如下:
(1) 通过一趟排序将要排序的数据划分成独立的两部分。
(2) 每部分各自再分成两小块, 使一小块所有数据都按原顺序排列且比另一小块按原顺序排列的所有数据都小 (或大) 。
(3) 把四块中两个小 (或大) 块按原顺序连接起来, 放在所有数据的前部, 把另外两个不小于 (或不大于) 块也按原顺序连接起来, 放在所有数据的后部。
(4) 然后再按此方法对形成的两部分数据分别进行稳定快速排序, 直到所有数据都是有序的。整个排序过程可以递归进行。
1.2 算法设计思路
本文以递增顺序排序为例进行说明。
(1) 增加与待排序数据数量相同的辅助存储空间如图1所示。
(2) 将待排序序列按经典算法的处理方法相似的方法分成二部分如图2所示深色部分和浅色部分, 同时把前面一部分数据进行如下处理, 所有小于middle值的元素按原顺序存放在原来存储区最前部D1区, 所有不小于middle值的元素按原顺序连续存放在辅助存储区最前部T1区;把后面一部分数据处理如下, 所有大于等于middle值的元素按原顺序存放在原来存储区最后部D4区, 所有小于middle值的元素按原顺序连续存放在辅助存储区最后部T3。
(3) 把前面一部分数据中不小于middle的数据 (T1区数据) 复制到后面一部分数据的最前部 (D3区) , 把后面一部分数据中小于middle的数据 (T3区数据) 复制到前面一部分数据的最后部 (D2区) 。一趟处理完成。
(4) 再递归地对第一部分和第二部分分别进行上述操作, 直至整个序列排序完成。
根据上面的算法设计思路可以知道, 当被排序的数据中任何数据相等时, 排在前面的数据永远排在前面, 所以此算法是稳定的。
1.3 算法描述
由于使用已知数据和未知数据不影响排序算法描述, 为了直观现以实际的数据为例对稳定快速排序算法进行描述, 假设待排序的关键码序列为Str1, 排序前增加同样存储空间的整型数组Str2, 如图3所示。
第一趟稳定快速排序过程:
(1) 选择str1中第一个数据34为middle, 作为数据分割依据。
(2) 从str1前面依次判断每个数是否小于middle, 34不满足小于middle条件, 结束判断。
(3) 从str1后面依次判断每个数是否大于或等于middle, 111满足条件, 34满足条件, 53满足条件, 21不满足条件, 结束判断。
(4) 把str1前面的34移到str2的前头, 把str1后面的21移到str2的后头, 结果如图4所示。
(5) 再回到str1前部继续判断21, 21满足小于middle的条件, 把21前移到原来34的位置, 继续判断53, 53不满足小于middle的条件, 判断结束。结果如图5所示。
(6) 再从str1后部继续判断, 123满足条件, 把123后移到原来21的位置, 78满足条件, 把78后移到原来123的位置, 8不满足条件, 判断结束。结果如图6所示。
(7) 把str1前部的53移到str2中34的后面, 把str1后部的8移到str2中21的前面。至此第一轮判断结束, 结果如图7所示。
(8) 最后把str2中前面的34、53顺序移到str1中78的前面, 把str2中前面的8、21顺序移到str1中21的后面, 结果如图8所示。到此整个第一趟稳定快速排序才真正结束。然后把分割的两部分再依次用上面方法完成整个稳定快速排序。
1.4 算法实现
下面的代码为用递归思想描述的稳定快速排序算法 (C语言实现) 。
2 稳定快速排序算法理论分析
本稳定快速排序算法是在原来的快速排序算法的基础上改进的, 算法理论与原快速排序的算法理论相似, 在此只对改进的地方进行分析。
2.1 算法稳定性
本稳定快速算法在进行数据分割的过程中, 把需要前后移动的数据不是直接交换, 而是先把它们按原顺序移出来保存起来, 被移走数据的位置用后面 (或前面) 的数据前移 (或后移) 填充, 等所有数据检查、移出和前后移完成后, 把保存起来要移动的数据分别移回到原来存储区前面所有数据的后面和后面所有数据的前面, 完成一次数据分割。然后把分割结果的前后两部分数据再按前述方法进行分割, 直到所有的数据都被分割成单个数据, 完成排序。确保相同的数据按原来的顺序存放即排序的稳定性。
2.2 算法空间复杂度
稳定快速排序算法与原来的快速排序算法相比, 在空间上多用了与原排序数据相同数据量的排序空间, 用来存放需要前后移动的数据, 它的空间复杂度还是O (N) 。
2.3 算法时间复杂度
稳定快速排序算法与经典快速排序算法在处理方式方面的主要不同在于对需要移动的数据处理方式有所差异, 算法时间复杂度不同就是由此引起的。
经典快速排序算法若需要数据移动, 通过前后两数据交换完成, 需要下面的处理过程:
稳定快速排序算法若需要数据移动, 先把数据顺序存放到临时存储区:
当所有数据检查处理完后, 再把临时存储区中所有数据顺序移回原数据区:
综上所述, 改进算法与经典算法相比每次移动数据只是多了一个赋值语句, 其他语句基本相同, 因此对n个排序数排序时最坏情况需移动n个数, 假定花费时间为Tf (n) , 对n个排序数进行一次划分的时间代价为C (n) , 则:
稳定快速排序的总时间代价为:
故, 稳定快速排序的算法没有引起时间性能大的变化, 算法时间复杂度仍为O (Nlog N) 。
3 实验结果与结论
3.1 稳定性测试
为了验证稳定快速算法, 随机组合了大量数据进行了实验, 如使用如图9表中十条记录的数据用本算法进行了简单的测试, 根据字段1按递增排序, 排序后记录数据的输出效果如图10所示。
从图中的结果可以看出, 根据字段1排序后, 字段1中相同的数据的先后顺序没有发生改变, 字段2为0的排第一位, 字段2为1的排序第二位, 字段2为4的排第五位, 因此算法是稳定的。
3.2 时间复杂度测试
在Windows XP的VC 6.0平台上, 对大量数据进行多次测试 (数据由随机函数Rand () 产生) 。
1) 随机产生50 000个整型数据用各种排序方法排序所用时间基本如图11所示。由图11可知, 稳定快速排序有很好的性能表现, 速度与原快速排序基本上相同, 与稳定排序的归并排序也基本相同。
2) 随机产生50 000个整型数据, 然后用求余法得到50 000个1位整数、50 000个2位整数、50 000个3位整数、50 000个4位整数和50 000个5位以上整数用稳定快速排序法进行排序所用时间基本如图12所示。由图12可知, 当数据的位数少时, 重复的数据多, 需要移动的数据多, 排序效率较慢, 3位以上数据的排序效率基本相同, 达到了最好。
4 结语
稳定快速排序算法是在原快速排序算法的基础上, 对算法的稳定性进行的完善, 理论和实践证明, 使用稳定快速排序算法, 可以确保排序是稳定的, 且本算法的时间复杂度没有大的改变, 只是多用了与排序数据数量相同的存储空间。
摘要：快速排序算法与其他算法相比是相当有效的排序算法, 但此算法并不完善, 它是不稳定的。为此, 对快速排序算法进行改进, 在每次对数据分割时, 对需要移动的数据先分别顺序拷出并保存, 分割结束前再按要求分别顺序拷入, 使得新排序算法是稳定算法。理论分析和实验数据表明, 在任何情况下, 稳定快速排序算法都是稳定的, 并且其他性能不比快速排序算法和归并算法差。
关键词：排序算法,算法稳定性,算法时间复杂度,算法空间复杂度,稳定快速排序
参考文献
[1]庞建雄.排序算法稳定性的深入讨论[J].桂林电子工业学院学报, 1996, 16 (1) :1-4.
[2]汪沁, 奚李峰.数据结构[M].北京:清华大学出版社, 2009.
[3]秦锋.数据结构[M].合肥:中国科学技术大学出版社, 2007.
[4]王善坤, 陶祯蓉.一种三路划分快速排序的改进算法[J].计算机应用研究, 2011, 29 (7) :2513-2516.
[5]汤亚玲, 秦锋.高效快速排序算法研究[J].计算机工程, 2010, 36 (7) :77-78.
[6]Cantone D, Cincotti G.Quic kHeapsort:An Efficient Mix of Classical Sorting Algorithms[J].The Oretical Computer Science, 2002, 285:25-42.
[7]周建钦.超快速排序[J].计算机工程与应用, 2006, 42 (29) :41-43.
最简单的排序算法(续) 篇5
虽然实现原理很简单,但毕竟还是用到了记事本这个软件。实际上根据珠排序的原理,自己DIY一台专门用来进行数据排序的计算机也是很容易的,使用到的设备,仅仅是几个逻辑门电路和移位寄存器。如果手头没有门电路的元件,那么用逻辑门电路模拟器也能实现设计,笔者使用的是Logisim,可从网上免费下载到。
需要解决的关键问题是如何利用逻辑门,搜索出字符串中所有的“10”,使之变成“01”。在一个字符串中搜索数据,首先,需要取出字符串中第一个和第二个数字,把数字输入到变量中;其次,匹配两个变量的值是否是“1”和“0”,若是则把两个变量的值重置为“0”和“1”,若不是则不用重置;再次,继续取出后续的数字进行匹配。如此多的步骤,实现起来似乎相当复杂,但实际上,只需要四个逻辑门,就可以完成任务。
这个装备需要用到与门和异或门两种逻辑门,与门的作用是当两个输入端均为1的时候,则输出为1,否则输出为0,用符号表示。异或门的作用是当两个输入端输入的值不相等时,输出为1,若两个输入端输入的值相等,则输出为0,用符号表示。
电路有三个输入端,一个输出端,用一个实际的例子能够更好地说明这个逻辑电路的作用(如下页图2)。假设初始值是“101”,首先,第一个初始数值“1”和第二个初始数值“0”进行逻辑门的与操作,得到中间结果A是“0”;其次,第二个初始数值“0”和第三个初始数值“1”进行逻辑门的与操作,得到的中间结果B是“0”;再次,第一个初始数值“1”和中间结果A即“0”作异或操作,得到的中间结果C是“1”;最后,中间结果C“1”和中间结果B“0”作异或操作,得到的结果是“1”。于是输入初始值“101”,得到结果为1。
不妨再来一个例子,假设初始值是“011”,首先,第一个初始数值“0”和第二个初始数值“1”进行逻辑门的与操作,得到中间结果A是“0”;其次,第二个初始数值“1”和第三个初始数值“1”进行逻辑门的与操作,得到的中间结果B是“1”;再次,第一个初始数值“0”和中间结果A即“0”作异或操作,得到的中间结果C是“0”;最后,中间结果C“0”和中间结果B“1”作异或操作,得到的结果是“1”。于是输入初始值是“011”,得到结果为“1”。
大家也许会说,在这里可一点也看不出“1”和“0”对调位置的效果。别着急,想象一下,如果对字符串“101”作“将10变为01”的替换,那么这个字符串会变成“011”,中间那个数字是“1”。如果对字符串“011”作替换,那么这个字符串仍然是“011”,中间那个数字仍然是“1”。上面的那个逻辑电路的作用,就是把三个数字作为一组,计算出搜索和替换后中间那个数值的值。
例如,字符串“1011001101011110”,如果我们想要将字符串中的“10”变成“01”,可以先把整个字符串首尾各补一个“0”,使其变成“010110011010111100”,则可以把字符串放进一个移位寄存器中(如图3)。首先,逻辑电路获得的数据是“010”,逻辑运算后得到结果是“0”;接着,移动一位,输入的数据是“101”,得到的结果是“1”;然后,再移动一位,输入数据是“011”,得到的结果仍然是“1”,以此类推。整个数据全部经逻辑电路运算后,得到的字符串就是“0110101010111101”,把初始字符串和经逻辑运算后的字符串并列排放,我们就能看出替换的效果了(如图4)。
初始字符串:1011001101011110
结果字符串:0110101010111101
既然能够对一行字符串进行替换操作,那么对多行的字符串进行替换操作其原理也完全相同。这样的话,就能很容易打造出一个实体的排序计算机,所需要的仅仅是两种逻辑门和若干移位寄存器。
改进的双向选择排序算法 篇6
为了采用查找效率较高的查找法, 通常希望待处理的数据按关键字大小有序排列, 因而排序是计算机程序设计中的一种基本操作[1]。
本文在介绍简单选择排序算法的基础上, 提出两种双向选择的算法设计方案, 并给出算法的C语言描述。部分参考文献中也有类似的关于该算法设计思路的描述, 但其算法实现中均存在不同程度的疏漏。本文详细分析了双向选择排序算法两种设计方案的具体步骤, 纠正了部分参考文献中存在的问题, 并通过对前后三种算法进行时间复杂度和空间复杂度的对比分析, 总结出双向选择排序算法的两种设计方案的优劣, 从而为简单选择排序算法的优化提供了一定的理论依据。
1 简单选择排序算法
待排序的记录序列所采用的排序方法可根据存储方式不同分为向量排序、 (链) 表排序和地址排序三种[2], 本文采用第一种方式, 即待排序的一组记录存放在地址连续的一组存储单元中。待排记录类型可用C语言定义如下:
以下均假定要求将各记录关键字按非递减有序进行排序。
1.1 算法设计思想
简单选择排序算法的基本设计思想是:第一趟排序从所有待排序记录的关键字中选择一个最小值, 同表头记录进行交换;第二趟排序从除去第一个的其余记录关键字中选择一个最小值, 同第二个记录进行交换;依此类推, 各趟排序均选择无序表部分的最小关键字, 并将其首先定位到最终位置 (无序表表头) , 从而逐步在无序表的表头形成有序表。
理论上讲, 有n个待排序记录需进行n-1趟排序。
算法执行过程中第i趟排序的关键步骤如下:
(1) 首先假定无序表表头记录 (下标为i的记录) 为当前关键字最小记录。
(2) 从第i+1记录开始至第n记录, 依次将各记录关键字同当前最小关键字进行比较, 并记下关键字更小的记录位置, 作为新的当前最小关键字。
(3) 第 (2) 步操作完成即得到第i趟中的最终最小关键字记录, 若该记录不在第i位, 则将其同第i位记录交换, 即完成第i趟排序。
1.2 算法的C语言描述与评价
基于RecordType定义类型的简单选择排序算法可用C语言描述如下 (其中, n为待排序记录个数) :
本算法利用C语言数组下标从0开始的特点, 将r[0]用作交换的中间暂存变量, 算法描述的初始化条件为各待排序记录存放在数组r[] 的1～n号下标单元。
从该算法的C语言描述中可以看出, 函数SelectSort ( ) 的核心语句由双重嵌套循环部分组成, 循环体基本语句 (if语句) 理论上共执行n-1+n-2+…+1=n (n-1) /2次, 此即关键字总的比较次数。将待排序的记录个数n看作问题的规模, 从而算法的平均时间复杂度可以关键字的比较次数来衡量, 即T (n) =O (n2) 。该函数在空间上除了待排序记录元素本身所占的向量空间外, 还引入了三个变量i, j和k的辅助空间, 其空间复杂度为常数阶, 即S (n) =O (1) 。
2 双向选择排序算法
简单选择排序法排序过程中的每一趟循环只能确定一个元素的最终位置, 算法效率不高, 可考虑改进为一趟确定两个元素的位置, 从而减少排序所需的循环次数[4,5,6,7,8,9,10], 称为双向选择排序算法。
双向选择排序算法的基本设计思想如下:
每趟排序均从待排序的无序表区间中选出关键字最小与最大的两个记录, 把最小关键字换到无序表表头, 最大关键字换到无序表表尾, 从而逐渐在无序表的两端形成有序表。这样, 理论上讲有n个待排记录只需进行n/2趟排序。
2.1 算法设计方案一
该方案直接对无序表部分进行双向选择排序。经过一趟排序, 即找到无序表部分的最大和最小关键字记录所在位置, 此时需分以下几种情况进行交换处理:
(1) 若最小关键字记录位于无序表表头, 且最大关键字记录位于无序表表尾, 则此时不需要进行交换即可进行下一趟排序扫描。
(2) 若最小关键字记录和最大关键字记录都不在最终位置, 则分以下几种情况进行交换处理:
①若二者位置刚好相反, 则将二者互换即可。
②若最小关键字记录位于表尾, 而最大关键字记录在除过表头的其它位置, 则按以下步骤处理:
将无序表中的表头记录暂存至r[0]; 将最小关键字记录 (此时即无序表表尾元素) 移至无序表表头位置 (此即其最终位置) ;将最大关键字记录移至无序表表尾 (此即其最终位置) ;将暂存在r[0]中的原表头记录移至最大关键字记录原来所在位置即可完成转换。
③若最大关键字记录位于表头, 而最小关键字记录在除去表尾的其它位置, 则按以下步骤处理:
将无序表中的原表头记录 (最大关键字记录) 暂存至r[0];将最小关键字记录移至无序表表头位置 (此即其最终位置) ;将无序表表尾记录 (下标n-i+1处的记录) 移至最小关键字记录的原位置;将暂存在r[0]中的最大关键字记录移至无序表表尾即可。
④若表头和表尾均不是最大或最小关键字记录, 则按以下步骤处理:
将无序表中的原表头记录暂存至r[0];将最小关键字记录移至无序表表头位置 (此即其最终位置) ;将无序表表尾记录 (下标n-i+1处的记录) 移至最小关键字记录的原位置;将最大关键字记录移至无序表表尾;将暂存在r[0]中的记录移至最大关键字记录空出的原位置即可。
(3) 若最小关键字记录位于表头的最终位置, 但最大关键字记录不在表尾, 则仅将最大关键字记录借助r[0]换到表尾即可。
(4) 若最大关键字记录位于表尾的最终位置, 但最小关键字记录不在表头, 则仅将最小关键字记录借助r[0]换到表头即可。
文献[4]在类似方案一的算法描述中虽然分情况进行了讨论, 但仍有未考虑的情况, 比如当最小关键字记录位于无序表表尾, 而最大关键字记录在除表头之外的其它位置的情况。
文献[5,6,7]关于方案一算法的描述是将选择排序蜕变成交换排序实现的, 相对原算法来说交换次数增多, 从而未能在真正意义上实现对原算法的优化。
文献[8,9,10]中关于该算法的描述均存在没有分情况讨论的问题, 从而排序过程的正确性无法保证。
2.2 方案一算法的C语言描述与评价
该算法的初始化条件同前, 基于RecordType定义类型的C语言描述如下:
从该设计思路的C语言算法描述中可以看出, 函数BiSelectSort_1 ( ) 同样由双重嵌套循环部分组成, 外层循环的循环体由一个循环语句和顺序执行的if语句组成, 因而基本语句为内层循环的循环体, 即两条定位最值的if语句。理论上一趟排序的比较次数为2 (n-2i+1) 次, 从而算法的总比较次数可按如下的公式计算:
可见, 该算法的平均时间复杂度虽仍为T (n) =O (n2) , 但算法中的比较次数略多于简单选择排序算法。另外, 该函数在空间上除了待排序记录元素本身所占的向量空间外, 还引入了四个变量i, j, min和max的辅助空间, 也比函数SelectSort ( ) 多用了一个变量的空间, 但其空间复杂度仍为常数阶, 即S (n) =O (1) 。这样, 该算法虽然同简单选择排序算法具有相同的平均时间复杂度和空间复杂度, 但效率略低于简单选择排序算法;此外又由于分情况讨论, 使得算法的复杂性要高于原算法。
2.3 算法设计方案二
方案一的算法直接对无序表部分进行双向选择, 在经过一趟排序扫描找到最小和最大关键字记录所在位置后, 需要分几种不同情况进行不同的交换处理, 这使得算法描述较为复杂, 可考虑进一步改进。
方案一中的一趟排序选择最值, 是在整个无序表的范围内进行的, 如果一开始先将无序表分割成最小关键字记录只位于表的前半部分, 最大关键字记录只位于表的后半部分, 则定位最小关键字记录只需在表的前半部分进行, 而定位最大关键字记录只需在表的后半部分进行, 从而将最值记录的定位进行了简化。
根据这种设计思想, 该算法第i趟排序的步骤可设计如下:
(1) 首先对无序表区间前后对应位置 (设无序表区间为i～ n-i+1, 则对应记录下标为i和n-i+1, i=1～n/2) 的记录关键字依次进行两两比较, 如有逆序则交换。整个交换过程完成后, 即将无序表中对应位置交换为关键字值较小者在前, 较大者在后。
(2) 在无序表的前半部分定位最小关键字记录, 若非表头记录, 则同表头记录互换。
(3) 在无序表的后半部分定位最大关键字记录, 若非表尾记录, 则同表尾记录互换。
这样共进行n/2趟排序即可完成整个排序过程。
文献[7]中关于方案二算法描述中的一趟排序, 是将前半部分和后半部分分别采用冒泡排序法的思路进行交换排序, 仍然存在比原选择排序算法交换次数增多的问题, 从而算法的执行效率不高。
2.4 方案二算法的C语言描述与评价
该算法的初始化条件同前, 基于RecordType定义类型的C语言描述如下:
从该设计思路的C语言算法描述中可以看出, 函数BiSelectSort_2 ( ) 同样由双重嵌套循环部分组成, 与思路一不同的是, 思路二外层循环的循环体由前后顺序执行的三条for语句组成。一趟排序过程中第一个for循环将无序表中对应位置的记录交换为关键字值较小者在前, 较大者在后, 理论上需进行n/2-i+1次比较;第二、三两个for循环分别在无序表的前半部分定位最小关键字记录, 后半部分定位最大关键字记录, 理论上均需进行n/2-i次比较, 则理论上一趟排序的比较次数为3 (n/2-i) +1次, 从而算法的总比较次数可按以下公式计算如下:
可见, 该算法的比较次数少于简单选择排序算法, 但平均时间复杂度仍为T (n) =O (n2) 。该函数在所占空间上同函数BiSelectSort_1 ( ) 一样, 其空间复杂度也为S (n) =O (1) 。另外, 由于该算法不需分情况讨论, 从而比BiSelectSort_1 ( ) 算法的复杂性大大降低。
3 结束语
双向选择排序算法是基于传统简单选择排序算法提出的一种改进的算法设计思路, 本文介绍的两种算法设计方案的C语言算法描述均已通过在VC++ 6.0环境进行正确性测试。
经过对3种算法进行时间复杂度和空间复杂度的对比分析, 本文最终得出以下结论:
两种设计思路的双向选择排序算法具有和原简单选择排序算法相同的平均时间复杂度和空间复杂度, 但思路一算法总的比较次数略高于原算法, 思路二算法的比较次数低于原算法;两种新算法在辅助空间上都比原算法多用一个变量空间。另外, 两种思路设计的算法就其简单性而言, 第二种优于第一种, 从而第二种思路设计的算法真正实现了对原简单选择排序算法的优化。
本文旨在给出简单选择排序算法的另一种分析设计思路, 纠正部分参考文献中关于该算法的疏漏。经过分析总结两种设计方案的优劣, 为简单选择排序算法的优化提供一定的理论依据, 也对《数据结构》相关章节的教学起到一定的指导作用。
参考文献
[1]耿国华.数据结构—C语言描述[M].西安:西安电子科技大学出版社, 2006.
[2]严蔚敏, 吴伟民.数据结构[M].北京:清华大学出版社, 2000.
[3]Wang Min.Analysis on Bubble Sort Algorithm Optimization[C].2010 International Forum on Information Technology and Applica-tions, July 2010 (待发表) .
[4]梁文忠.一种基于直接选择排序算法的改进[J].广西师范学院学报:自然科学版, 2004, 21 (4) :93-96.
[5]何洪英.两种排序算法的改进[J].绵阳师范学院学报, 2007, 26 (11) :98-99.
[6]江敏.双向选择排序算法[J].泰州职业技术学院学报, 2005, 5 (1) :60-62.
[7]张忆文, 谭霁.简单选择排序算法的改进及分析[J].硅谷, 2009 (18) :77, 94.
[8]葛玮, 刘斌.排序算法的比较、选择及其改进[J].江西广播电视大学学报, 2008 (3) :75-77.
[9]于春霞, 代文征.二路选择排序探讨[J].黄河科技大学学报, 2009, 11 (6) :107-108.
LSort字符排序算法研究 篇7
关键词：排序,算法,有序序列
1 排序算法的基本概念
随着计算机技术的发展及互联网的普及,各类数据量迅猛增长,导致日常数据查询效率较低,构造一个合适的排序算法可以极大提高工作效率。
传统的排序功能要求给定一个无序数据序列,经过排序操作后,将序列按从大到小或从小到大的顺序排列成有序序列,即:
输入序列:N1,N2,N3,...,Nn
排序算法一般分为稳定类算法与不稳定类算法,稳定类算法指当有两个相等记录的关键字Keyword1与Keyword2时,在原数据序列中Keyword1出现在Keyword2之前,经过排序操作后,关键字Keyword1仍然在关键字Keyword2之前;而不稳定排序类算法会在相等的键值中改变记录的相对顺序,所以在构造排序算法过程中,应该尽量避免不稳定类排序算法。目前,稳定类排序算法有冒泡排序算法、合并排序算法等[2]。
2 经典冒泡排序算法
冒泡排序算法属于典型的交换类排序算法,交换类算法的主要思想是将待排序数据的关键字进行两两比较,当两个元素的值大小相反时交换其位置,同理依次对所有数据进行两两比较[3]。
经典冒泡排序算法的核心思想是将被排序的无序数据序列N[1..n]进行垂直排列,每个数据N[i]被看作是重量为N[i].m的气泡。根据轻气泡在上重气泡在下的原则,从下往上扫描整个数据序列N,遇到顺序不符的轻气泡时调换其位置。对所有“气泡”进行扫描,使所有“气泡”都符合轻上重下的原则[4]。
每次排序过程都使有序气泡增加1个,在经过n-1次排序后,数据序列中就有n-1个气泡,而无序数据序列中气泡的重量大于或等于有序数据序列中气泡的重量,所以整个排序过程至多需要进行n-1次排序。若在某一次排序中未发现气泡位置交换,则说明待排序的无序序列中所有气泡都满足轻者在上重者在下的原则。
衡量算法优劣一般采用时间复杂度及空间复杂度方法,冒泡排序算法的时间复杂度为O(n2),空间复杂度为O(1)。
3 LSort字符排序算法
一个问题往往可采用多种算法进行解决,而算法的优劣将直接影响最终程序的效率。算法分析的目的在于选择合适算法和改进算法,冒泡排序算法在多种情况下,每个元素都需要与其它n-1个元素进行比较,在对大量数据进行排序操作时效率较低。为了提高排序操作的效率,本文设计一种新的排序方法—LSort字符排序算法。
其核心思想是对于一个无序字符序列,另外开辟一个与原来序列相同大小的空序列,新序列中要求所有存储元素都是有序的,即添加的元素与新序列中的每个元素进行比较,比如元素3添加到新序列:1,2,4,5中时,将元素3与第1个元素比较,当比较到元素4时,将元素4和5往后退一个空间,然后将3放到元素4之前的位置,具体实现代码如下:
4 LSort字符排序算法的时间复杂度
算法的时间复杂度在计算机科学中是一个函数,大概描述了算法的运行时间。时间复杂度一般使用“O”符号表达,结果一般以最高阶次为准,不考虑函数的低阶项和各项系数。时间复杂度一般考察输入值趋近无穷时的情况[5]。
排序算法中的基本操作重复执行的问题是规模n的函数,假设问题的规模是n,基本操作重复执行的次数是函数f(n),那么时间复杂度记作:T(n)=O(f(n))。
排序算法花费的时间与算法中语句的执行次数成正比,语句执行次数越多,对应的时间复杂度就越大。算法的时间频度从理论上不能直接计算出来,需要上机试运行才能得到具体频度值。时间复杂度一般考虑问题规模n的增长率,一般考虑重复执行次数关于n的阶数。
LSort算法中for循环操作重复n-1次,其它赋值判断等操作重复n-1次,所以LSort算法的时间复杂度T(n)=O(n)。
5 LSort字符排序算法的空间复杂度
空间复杂度是对算法运行过程中占用存储空间的一种量度。通过算法空间复杂度计算,可对程序运行所需内存的多少进行预估。算法执行除了包含程序本身所使用的指令、常数、变量和输入数据外,还需包含对数据进行操作的工作单元,以及部分辅助存储空间[5]。程序运行过程执行的存储空间主要分为以下两部分:
(1)固定空间:固定空间部分的大小与输入/出数据个数无关。主要包含代码空间、数据空间,属于静态存储空间。
(2)可调空间:主要包括动态分配的空间,以及递归堆栈所用的空间等,与算法有关。
算法空间复杂度一般考虑程序在运行过程中为局部变量分配的存储空间,具体包括形参列表分配的存储空间大小,以及在函数体中定义的局部变量的存储空间。对于递归类算法,空间复杂度等于所用堆栈空间的大小,等于调用所用的临时存储空间乘以被调用次数的积。
算法空间复杂度一般以数量级的形式表示,例如一个算法的空间复杂度为常量,即不随规模n的大小而改变时,算法空间复杂度等于O(1);当算法的空间复杂度与规模n呈线性比例关系时,可表示为O(n);当算法的空间复杂度与log2n成正比时,可表示为O(log2n)。假设形参为数组类型,只需为它分配实参传送来的地址指针所占用的空间;假如形参为引用类型,只需要分配存储地址所占用的存储空间。
LSort算法排序过程中,新序列所使用的空间为常量,且规模n的增长对空间并没有产生影响,所以其空间复杂度S(n)=O(1)。
6 结语
本文分析了排序算法的特点,讨论了经典冒泡排序算法的核心思想,并针对冒泡排序算法的效率提出了LSort字符排序算法。通过建立新的有序列表,能有效减少排序过程中的比较次数,经测试该算法适合对大量无序字符数据进行排序。
参考文献
[1]王红梅.数据结构(C++版)[M].北京:清华大学出版社,2011:167-188.
[2]贾丹.排序算法的性能分析[J].电脑知识与技术,2015(26):75.
[3]钟全.简单选择排序算法稳定性探究及其改进[J].软件导刊,2016(2):60-63.
[4]张朝鑫.C语言中的冒泡排序算法优化究[J].硅谷,2013(19):166.