排序算法（通用10篇）
排序算法 篇1
引言
排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。排序是将数据元素的任一序列, 重新排列成一个关键字有序的序列。基于比较和移动的排序算法具有通用性, 包括插入排序、选择排序、交换排序、归并排序、基数排序等等。各种排序的算法各具有优缺点, 但就其全面性能而言, 很难提出一种被公认的最好的方法。判断一个排序算法优劣的标准一般为时间复杂度、空间复杂度和稳定性。
一、简单选择排序算法
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期。
[5]张忆文、谭霁:《简单选择排序算法的改进及分析》, 《信息科学》, 2009 (18) 。
排序算法 篇2
教学内容：
选择排序的算法思想 选择排序的实现过程 选择排序的编码实现
总结和思考：大数据背景下的排序
排序(Sort)是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。排序方法分为两大类：一类是内排序：冒泡排序、选择排序、插入排序、希尔排序、交换排序、快速排序等；另一类是外排序。
从教学理念上看，本节课利用维果斯基的“最近发展区理论”，把学生的现有水平和兴趣点，结合教学的目标，形成最近发展区。教学着眼于学生的最近发展区，提供带有难度的内容，调动学生的积极性，发挥其潜能，超越其最近发展区而达到下一发展阶段的水平，然后在此基础上进行下一个发展区的发展。
从教学方法来看，主要使用案例分析法、讲授法等，从分析当前流行的冒泡排序算法的案例开始，由浅入深的介绍选择排序的基本概念,算法思想以及编码过程。
从教学过程来看，首先从回顾冒泡排序的内容导入，在改进冒泡排序的过程中，提出选择排序的概念和思想。用直观的动画方式展现选择排序思想和过程，总结分析出关键代码，引导学生写出完整代码，最后分析选择排序的关键点，并提出思考，大数据背景下的排序改进方法。
排序算法 篇3
摘要： 对搜索结果的排序是搜索引擎中至关重要的一项技术，算法的好坏直接关系到用户输 入关键词后能不能迅速查看到要查找的信息。系统的介绍超链接分析技术及基于超链接分析 的搜索引擎页面排序算法。对两种最基本的页面排序算法PageRank和HITS的算法思想和实现 原理进行详细阐述。通过分析对比，总结出它们各自存在的优点和不足进而指出适合其应用 的条件领域。最后指出搜素引擎应用超链接分析时应注意的一些影响因素。
关键词：搜索引擎；超链接分析；页面排序；PageRank；HITS
中图分类号：TP301文献标识码：A[WT]文章编号：16721098(2008)02007305
Analysis of Two Kinds of Search Engine Pageranking
Algorithm Based on Hyperlink Analysis
ZHANG Shujiang
(School of Computer Science and Engineering, Anhui University of Science and Tec hnology, Huainan Anhui 232001, China) Abstract: Search results sorting is a key technology in search engine, the algo rithmhas a direct influence on whether users can quickly find their expected i nformation afterkeywords are entered or not. The technology used for hyperlinkanalysis andpageranking algorithms based on hyperlink analysis were system ic ally presented. The ideas and principles of two of the most fundamental pager an king algorithms, PageRank and HITS, were expatiated. After analysis and comparis on, their respective advantages and disadvantages were summed up, and the condit ions and fields suitable for their application given. Finally some factors to benoted when search engine uses hyperlink analysis were pointed out.
Key words:search engine; hyperlink analysis; pageranking;PageRank; HITS
在互联网发展初期，网站相对较少，信息查找也比较容易。然而伴随互联网爆炸性的发展， 从1994年万维网（World Wide Web，WWW或Web）出现到现在短短十几年的发展，由于其开放 性和其上信息广泛的可访问性极大的鼓舞了人们创作的积极性使其日益发展成为一个最为丰 富庞大的信息资源库。对于一个普通互联网用户要想在这个硕大的信息库中找到自己所需的 资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生了。
这些专业搜索网站的核心就是搜索引擎技术。而搜索引擎技术中搜索结果页面的排序算法在 搜索引擎中处于举足轻重的地位，因为排序算法决定了系统索引的网页与用户查询意图的相 关程度，同时也决定了网页在查询结果中出现的次序。它的好坏直接关系到用户输入关键词 后能不能得到要查找的信息。因此搜索引擎页面排序算法越来越受到众多研究学者的青睐， 尤其是基于超链接分析的排序算法更是层出不穷。
1超链接分析技术简介
传统的Web搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档。也有基 于目录分类的搜索引擎，比如早期的Yahoo、新浪的搜索服务。但这些搜索引擎的搜索结果 并不令人满意。因为有些网站拥有者为了使自己的网站在搜索结果中能排在较为前端的位置 故意提高某些关键字的出现频率从而破坏了搜索结果的客观性和准确性。此外，有些重要网 页可能并没有包含查询项因而也就不可能被搜索引擎检索到。
然而，一些研究学者们逐渐发现，Web上超链结构是个非常丰富和重要的资源，如果能够充 分利用的话，可以极大的提高检索结果的质量［1］189。进而提出了基于超链接分析 的搜索结果排序算法。文献［2］78提出的PageRank算法开启了超链接分析研究的热 潮 。超链接分析的基本原理是：在某次搜索的所有结果中（大型商业搜索引擎通常会有数十万 甚至上百万个搜索结果），被其它网页用超链指向越多的页面，其价值就越高，在输出排序 中就应该排得越靠前［3］。即一个网页的重要性取决于该网页被其它网页链接的数 量，特别是被一些已经被认定为“重要”网页链接的数量。
超链接分析其实是一种引用投票机制，也就说如果一个网页被另外一个网页链接一次就相当 于另一网页对其投了一票，其重要性被肯定一次。对于静态网页或网站主页，这种机制具有 一定的合理性。因为这样的网页容易根据其在互联网上受到的评价而产生超链接指向的数量 ，超链分析的结果可以从很大程度上反映该网页的实际重要程度，能够为搜索用户返回接近 其搜索意图且很有价值的搜索结果。事实上，超链分析技术除了分析网页本身的文字外，还 分析所有指向该网页的链接URL、链接文字、甚至链接周围的文字。这样，有时候即使某个 网页html1中并没有包含某个词，比如“下载”，但如果有别的网页html2用链接文字“下载 ”指向这个网页html1，那么用户在搜索“下载”这个关键词时也能找到网页html1。而且， 如果有越多网页（html2、html3、html4、html5…）用“下载”链接指向这个网页html1 ，或者给出这个链接的源网页（html2、html3、html4、html5…）越优秀，那么网页html 1在用户搜索“下载”时就会被认为越相关，在搜索结果中的排名也就会越靠前。
由此看见，所谓链接分析主要基于如下两个重要假设:①超文本链接包含了用户对一个网站 的判断信息;②对一个网站而言，如果其他网站链接到该网站的链接数（即入链数）越多， 则该网站越重要。这两个假设在各种基于链接分析的算法中均以某种方式体现出来［2 ］78。
基于这种超链分析思想，一些学者提出了许多页面排序算法。目前有：PageRank算法、HITS算法、SALSA（Stochastic Approach for LinkStructure Analysis）算法、PHITS算法（Probabilistic analogue of the HITS）；贝叶斯算法、Reputation算法［3］6。还有在各自的基础上进行改进而产生的算法变种。这些算法 有的已经在实际的系统中实现和使用，并且取得了良好的效果。在这些算法中，PageRank和 HITS是最著名也是最基本的页面排序算法，其它算法是在两者基础之上进行某种程度的改进 版。下面对这两个基本算法作个详细的介绍与分析以为以后的研究工作做好基础准备工作。
2基于超链接分析的算法
2．1PageRank算法
2.1.1基本思想在基于超链接分析的排序算法中，PageRank算法是最有名的一种。它最初是Sergey Brin和L awrence Page在1998年提出的，后来被用在世界上最著名的搜索引擎Google中一直到今天。 Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在搜索结果集中的出现 位置，PageRank值越高的网页，在结果中出现的位置越靠前。
其基本思想是:如果某一网页玊存在一个指向网页A的链接，则表明网页T的所有者认为网页 A是比较重要的，从而把T重要性得分值（即网页T的PageRank值）的一部分赋予獳。A 得到的分值大小由玊的PageRank值玃R(T)和T的出链(从T链出的链接)数C(T)决定。用公 式表示为:PR(T)/C(T)。因而对于页面A，其PageRank值玃R(A)就是从所有指向它的页 面分得的重要性分值的总和。可用以下公式计算オPR(A)=PR(T1)/C(T1)+…+
PR(Tn)/C(Tn)(1)
其中：玊1、T2、T3…Tn为含有指向A的链接的页面。
由于互联网上也存在一些页面没有入链或出链那么就无法计算其PageRank值。为避免这个问 题（即所谓的LinkSink问题）一些研究学者对其进行改进，为式（1）添加一个阻尼系数 玠使其变为
PR(A)=(1-d)+d［PR(T1)/C(T1)+…+PR(Tn)/C(Tn)］(2)
玠为阻尼系数，Google常指定为0.85［4］。这样在整个网络内的页面经过多次递 归迭代计算，直到PR值达到收敛即求得页面的PageRank值。
2.1.2优缺点分析从以上PageRank的计算公式中也以看出，一个页面会将自己的PageRank值均匀的分配给它所 引用的页面，它引用的页面越多，每个被它引用的页面所分得的PageRank值越少。因而一个 页面会因为别的页面对自己的引用而增加自己的PageRank值，但并不会因为自己对别的页面 的引用而提高自己的PageRank值。这样，对于一个网页来说要想获得较为靠前的排名就要获 得较大的PageRank值，而要获得较大的PageRank值就要被较多重要的网站所引用，因为只有 那些重要网站才有较大的PageRank值。而如果两个页面各自本身的PageRank值都很低，则它 们互相链接后也增加不多，重复链接对两者更是有害无益。由于页面的链接数越多，被链接 页面得到的PageRank值就会越低因此高级别的网站也不会与质量不高的网站互换链接。一个 网站要想获得较高级别的PageRank值就只有一个办法那就是要求网站拥有者老老实实地做好 自己的每一个网页，提高整个网站的质量水平才能换得高级别网站的链接。所以PageRank技 术可以很有效的避免某些网站为获得较高排名来欺骗搜索引擎。
PageRank技术的另外一个优点在于它是一个与查询无关的静态算法。尽管所有网页的PageRa nk值都要通过进行递归迭代计算以求得收敛值，这一过程中计算量很大，但这些计算不要求 实时性，可以离线计算获得结果后保存起来。这样能有效的减少在线查询时的运算量极大的 缩短查询响应时间。
然而，PageRank技术的缺点也是显而易见的。因为PageRank仅仅依靠计算网页的外部链接数 量来决定该网页的排名，而完全忽略了页面的主题内容与用户查询意图的相关性从而影响搜 索结果的相关性和准确性。另外，有一些Hub页本身并不突出，除了链接外也没有多少内容 也没有多少链接指向它，但它却指向了某个话题最突出的页面链接。可以说一个好的页面由 多个好的Hub页面所指向，一个好的Hub页面指向多个好的页面。这应该是一种互动关系，但 在PageRank中并没有考虑到［5］。再者，对于一些较新的网页由于还没有被发现故 被引用的次数很少因而即使质量很高也不会获得很高的PageRank值。也就是说PageRank会对 新网页表现很大的歧视性。
2．2HITS算法
2.2.1基本思想HITS（Hyperlink Induced Topic Search）算法是Kleinberg在1998年提出的，是基于超链 接分析排序算法中另一个最著名的算法之一。在该算法中,按照超链接的方向,将网页分成两 种类型的页面：Authority页面（权威页）和Hub页面（目录页）。二者是HITS算法中两个十 分重要的概念。Authority页面是指与某个查询关键词和组合最相近的页面；Hub页面是指它 的出链中包含了很多的Authority页面的页面，它的主要功能就是把这些Authority页面联合 在一起［6］。
HITS基本思想是：将查询玵提交给传统的基于关键字匹配的搜索引擎，搜索引擎返回很 多网页，从中取前玭个网页作为根集(Root Set)，用玆表示。R一般满足如下三个条件 ：① R中网页数量相对较小；② R中网页大多数是与查询q相关的网页；③ R中包 含 较多的权威网页。然后根据这个集合R在整个网页有向图中的位置来扩展这个根集合。即通 过向R加入被R引用的网页和引用R的网页将R扩展成一个更大的集合称为基集T。在得到这 个集合后，就开始计算集合中每个网页的目录型权值和权威型权值。利用Authority页面和H ub页面互相增强属性,对集合玊进行链接分析,通过迭代的计算方法为玊中的每个页面 计算一个Authority值和一个Hub值,作为结果页面排名的依据。
假定基集玊中的页面分别为 1，2，3，…玴 。每个页面玴有一个Authority值玜 p和Hub值玥p；页面玴的入链页面集表示为Bp(m），出链页面集表示为獸p（n ）。则ap和hp用如下公式进行计算
ap=∑[DD(]m[]i=1[DD)]hi(i∈Bp(m))
hp=∑[DD(]n[]i=1[DD)]ai(i∈Fp(n))
这样的递归式很容易用矩阵方法表示。令所有选出来的网页都进行标号，得到所有网页的编 号集｛1,2,…,玭｝。令相邻矩阵A为一个n×n的矩阵，如果存在一个从 网页i 链接到网页j 的超链，就令矩阵中A的第（i, j）个元素置为1，否 则置为0。同时，将所有网页的权威型 权值x和目录型权值y都分别表示成向量x=(x1,x2,x3,…,xn),y=(y1,y2,y3, …,yn)。由此可以得到计算x和y的简单矩阵公式：y=A•x,x=A 琓•y其中A琓是A的转置矩阵。进一 步，我们有：
x=A琓•y=A琓•Ax=( A琓A)•x
y=A琓•x=AA琓y=(AA琓)• y
因此向量玿,y均可经过多次迭代而得。经过一定次数的递归运算后，会得到集合中每个网 页的权威型权值和目录型权值。按照这两个不同的权值，分别取出前k个页面输出返回给 用户。根据线性代数的理论,迭代序列经过标准化最终将收敛于矩阵A的 特征向量,即上文计 算的Hub权值和Authority权值是页面集合的固有特征,不是由初始向量和参数的选择决定的 。
2.2.2优缺点分析由HITS的计算过程我们可以看出这种算法是一种依赖于查询关键字的算法。每得到一个检索 ，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再通过 运算获得各个网页的相应链接权值。实际应用中，由R生成T的时间开销是很昂贵的 ，需要下 载和分析R中每个网页包含的所有链接，并且排除重复的链接。一般玊比R大很 多，由T生 成有向图也很耗时。需要分别计算网页的A/H值，计算量比PageRan k算法大。已有实验数据 表明，这种算法获得的排名准确性高于PageRank算法。但在用户检索时进行如此大量的运算 ，检索效率显然不高。
HITS算法最大的弱点是处理不好主题漂移问题（topic drift），也就是紧密链接TKC（Tigh tlyKnit Community Effect）现象［7］。由于HITS只计算主特征向量，也就是只 能发现玊集合中的主社区（Community），忽略了其它重要的社区。如果在集合玊中 有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页 ，从而偏离了原来的查询主题。因此，HITS更适合于宽主题的查询。
另外，HITS算法不能有效的识别网站制作者对搜索引擎的欺骗。Web页面中有许多链接是为 其他目的而创建的,例如付费广告、网站本身导航等等,因此单凭链接数目来判断页面的Auth ority值和Hub值,是不合理的。
用HITS进行窄主题查询时，还可能产生主题泛化问题，即由根集到基集的扩展后引人了比原 来主题更重要的新主题，新主题可能与原始查询无关。泛化的原因是因为网页中包含不同主 题的向外链接，而且新主题的链接更加具有重要性。
3超链接分析应注意的问题
基于超链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容， 不需人工干预就能自动发现Web上重要的资源，挖掘出Web上重要的社区，自动实现文档分类 ［3］4。但由于互联网的开放性和自由性使得Web页面上的超链接也呈现鱼龙混杂状 态，给超链分析工作带来一定的干扰和欺骗。避害趋利，力求算法做到最大程度的精确 有效。有一些共同的问题影响着算法的精度我们必须给与重视。
(1) 根集的质量根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页， 产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量 网页集找出很多高质量的网页。
(2) 噪音链接Wed上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商， 用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果［1］196。如何 有效的去除这些无关链接，也是算法的一个关键点。
(3) 锚文本的利用锚文本有很高的精度，对链接和目标网页的描述比较精确。在具体的实 现中我们应大加利用锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很 大。
(4) 查询的分类每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法， 以求获得最好的结果。因此，对于查询的分类也显得非常重要。
4结束语
随着Internet上信息量的爆炸式增长，人们越来越依赖于搜索引擎获取所需信息。虽然目前 的商用搜索引擎取得了很大的成功，但还有许多方便需要进一步完善。本文主要对基于超链 接分析的两种最基本的搜索结果排序算法PageRank和HITS进行了详细介绍和分析对比。希望 为将来在这两种算法思想的基础上进行改进，提出更精确更完善的排序算法打下基础。搜索 引擎的研究是一个热点,要能真正的研究并有所创新,对现有基础技术理论的学习和深入理解 是基础。
参考文献：
［1］李晓明，闫宏飞，王继民.搜索引擎——原理、技术与系统［M］.北京：科 学出版社,2004：189，196.
［2］吴江.使用超链分析技术的搜索引擎［J］.图书情报工作，2004，48(7)：78 81.
［3］李绍华，高文宇.搜索引擎页面排序算法研究综述［J］. 计算机应用研究，2007,24(6):47.
［4］刘琨，郑有才.搜索引擎剖析［J］.微机发展，2004,14(3):1922.
［5］徐宝文,张卫丰.搜索引擎与信息获取技术［M］. 北京:清华大学出版社,200 3：109110.
［6］张娜，张化祥.基于超链接和内容相关度的检索算法［J］. 计算机应用，2 006,26(5):1 1711 173.
［7］郑煜,钱榕.一个基于链接分析的相关度排序算法及其在专题搜索引擎中应用 ［J］.计算机应用与软件，2007，24（7）：5455.
数组排序算法浅析 篇4
顺序排序的主要思想是每一轮比较结束后都可以确定某一元素;在一轮的比较过程中, 将要确定的位置上的元素与其后所有的元素进行比较;对于一个长为N的数组, 需进行N-1轮比较。其第一轮的比较过程如下:
该轮中, a[0]与a[1]~a[n-1]的所有元素进行比较, 比较过程中, 如果发现哪个元素比a[0]小, 则与a[0]进行交换。一轮比较之后, 确定a[0]为数组中最小的元素。相同方法, 依次确定a[1]、a[2]、a[3]…a[n-2]。
由上表, 可以写出其实现代码
可以发现当数组原有的顺序是降序, 要实现其升序排序时, 每一轮中的交换的次数将会非常多, 严重影响排序效率。所以对该方法进行改进:先找出数组中最小值, 再与相应位置上的元素进行交换, 这就是选择排序。
选择排序的主要思想是每次从待排序的数据元素中选出最小的一个元素, 放在待排序数列的起始位置, 直到全部待排序列的数据元素全部排列完毕。
第一轮的比较过程如下:
选择排序的实现代码
选择排序相较于顺序排序有更高的执行效率, 而且思想同样利于理解。
冒泡排序的主要思想是“相邻元素”之间的比较, 如果前面的元素大于后面元素就把他们互换。一轮比较之后可以确定最后一个元素为最大, 第二轮比较之后可以确定最后一个元素为第二大的元素……依次类推, 第N-1轮比较, 可以确定倒数第二个元素, 这个时候数组的排序完成。冒泡排序的过程如下:
冒泡排序的实现代码
顺序排序算法, 思想简单易于理解且适于任何的数组, 无论什么情况下都可以使用;但是顺序排序效率较低, 可以采用选择排序法进行改进;即使如此选择排序的效率依然受到比较次数的影响, 所以对于比较元素比较少的数组, 可以采用冒泡排序法。
如果数组中99%的数值已经排序好, 即只有很少的元素需要进行排序, 可以选择冒泡排序法;如果你所要排序的数据数目相对较少并满足100个以下, 你就可以采用选择排序法;如果上述几种情况都不满足, 那么就选普遍适用的排序算法即顺序排序法即可。
以上所述只是三种常见排序, 在众多的排序算法中各有优缺点, 每一种算法只有在某一种情况下才表现的最好, 我们应当合理的根据实际情况选择算法。
参考文献
[1]张巍.基于Page Rank算法的搜索引擎优化策略研究[D].四川大学, 2005.
[2]郭敏杰.基于云计算的海量网络流量数据分析处理及关键算法研究[D].北京邮电大学, 2014.
选择排序算法总结 篇5
1. 首选在数组
2. 遍历一遍数组(从left到right)，将比主元
3. 比较主元位置
稳定快速排序算法研究 篇6
快速排序算法在所有的排序算法中是比较优秀的算法, 也是推荐的常用算法, 但它不完善, 即它是不稳定的排序算法。所谓排序算法的稳定性是指在待排序的记录序列中, 如果存在多个具有相同的关键字的记录, 若经过排序, 这些记录的相对次序保持不变, 即在原序列中, 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.
数值排序算法比较分析 篇7
按照排序的数据规模，可以将排序分为内部排序和外部排序两类[3]。内部排序就是将待排序序列全部加载到内存中一次性排序的过程。外部排序是数据规模超过内存容量而产生的一种多次读取外存数据到内存，分别进行排序后最终整合的排序过程。外部排序本质上是多次内部排序加上多次外存读取的融合，因此，内部排序是排序问题的基础和核心。常用的内部排序算法按照基本思想可以分为插入排序、交换排序、选择排序、归并排序和基数排序等几类，在此选取了常见的7种排序算法，冒泡排序、快速排序、直接插入排序、希尔排序、堆排序和基数排序进行比较分析。
在排序方面的研究和文章已经存在[2,3,4,5]，但是这些研究和数据都是基于C平台和整形数据，而实际应用中Java平台和浮点型数据应用较多。鉴于目前Java计数的广泛应用，在Ja va平台上用7种常用的数值排序算法测试不同规模的整型数据和浮点型数据，为采用何种排序算法提供参考。
1 算法描述和分析
算法描述中的待排记录均用R{R1,R2,R3,R4,R5….Rn}表示，n表示数据规模。
1.1 冒泡排序
1.1.1 基本思想
冒泡排序是一种交换排序算法。基本思想是依次从头到尾依次遍历含有n个元素的待排记录R，比较相邻元素，例如R1,R2，若R1>R2则交换两元素位置。每遍历一次选出最大的元素并且置于排序记录尾位置，为一次冒泡过程。接着排序前n-1个元素序列，进行相同的比较交换过程，选出最大元素置于序列的次尾位置。依次类推，直到待排序列有序位置。通常冒泡排序中会有一个哨兵来记录是否发生了元素交换，当一次遍历中没有发生元素交换时，表明序列已经有序。
1.1.2 时间复杂度
若有n个待排元素，第1次遍历的比较次数为n-1,第二次遍历为n-2,依次类推，第i次为n-i，时间复杂度表示为
冒泡排序的最差时间复杂度为O(f(n))=O(n2)，最优时间复杂度为O(f(n))=O(n)
1.1.3 空间复杂度与稳定性
冒泡排序中只是在元素交换过程中需要一个辅助空间，空间复杂度为O(1)。元素交换只发生在R1>R2的情况下，保持了原序列相同元素的前后位置，所以冒泡排序是一种稳定的排序算法。
1.2 快速排序
1.2.1 基本思想
快速排序是一种交换排序算法。首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面的序列Rleft，所有比它大的数都放到它后面序列Rright，这个过程称为一趟快速排序。接着分别对Rleft和Rright进行同样的快速排序，重复相同的操作，直到序列有序为止。
1.2.2 时间复杂度
每次快速排序是将待排序列分成两个规模较小的子序列接着进行快速排序，即二分问题，形似二叉树问题。其时间复杂度是由快速排序的次数和排序规模决定的，也就是二叉树的树高和元素的个数。
根据树结构理论，快速排序的最优，也是平均时间复杂度为O(f(n))=O(nlog2n)，最差时间复杂度为O(f(n))=O(n2)。
1.2.3 空间复杂度和稳定性
每执行一次快速排序都需要一个辅助空间，若采用递归方式实现需要额外的压栈空间，快速排序的空间复杂度即为执行快速排序的次数，为O(nlog2n)。在排序过程中，不能保证原序列中相同元素的前后位置，是不稳定的。
1.3 插入排序
1.3.1 基本思想
插入排序在这里指直接插入排序，直接插入排序是最简单的插入排序算法。基本思想是把待排记录R按其关键码值的大小逐个插入到一个已经排好序的有序序列RinOrder中，直到所有的元素插入完为止，得到一个新的有序序列。
1.3.2 时间复杂度
插入排序的时间主要消耗在查询待排元素Ri的插入位置过程中，一般采用从后向前顺序遍历序列Rin Order，找到插入位置j,顺序移动Rj(Ri>=Rj）后的元素并将Ri插入到原Rj处。时间消耗由排序序列长度n和和待排元素在原序列中的位置i决定，
最差时间复杂度O(n2)，最优时间复杂度O(n2)，平均时间复杂度O(n2)。
1.3.3 空间复杂度和稳定性
插入排序只需要一个辅助空间，并且插入过程保持了原序列相同元素的前后位置。空间复杂度为O(1)，稳定的排序算法。
1.4 希尔排序[6]
1.4.1 基本思想
希尔排序是一种改进的插入排序算法。首先选取一定的增量d(d<n)将待排记录R进行分组，形成若干个类似分组Ri{Ri,Ri+d,….Ri+jd|i+jd<=n}。在每个小分组里面进行直接插入排序，使得分组记录有序。接着逐渐减小d值，重复相同操作，直到增量d为1，待排记录R有序。
1.4.2 时间复杂度
希尔排序时间复杂度和增量的选取有关，一般采用希尔增量，即初次增量选取待排记录的一半，以后每次减半，直到增量为1。选取希尔增量的时间复杂度为O(n2)，希尔排序时间复杂度的下界为O(nlog2n)。
1.4.3 空间复杂度和稳定性
希尔排序只需要一个辅助空间，空间复杂度为O(1)。希尔排序反复执行了多次插入排序，相同的元素可能在各自的插入排序中移动，所以，插入排序是不稳定的排序。
1.5 堆排序
1.5.1 基本思想
堆排序是一种选择排序算法。堆排序将待排记录R根据元素下标关系看作一棵完全二叉树，并且具有根元素最大或者最小性质，简称大根堆或小根堆。每次排序首先调整大根堆或者小根堆性质，而后交换堆顶R0与最后一个元素Rn(n为待排记录长度，随着排序过程递减)位置，接着在余下待排记录R{R0,…,Rn-1}上进行相同的排序操作，直到只有一个元素R0，排序完成，记录有序。
1.5.2 时间复杂度
堆排序的时间主要消耗在大根堆或小根堆的调整上。堆调整过程是相当于一次完全二叉树的查询过程，整个过程的复杂度为O(nlog2n)。
1.5.3 空间复杂度和稳定性
堆排序过程只需要一个辅助空间用来存放交换过程中的临时变量，但是在交换过程中不能保证原纪录中相同元素的前后位置。空间复杂度为O(1)，算法不稳定。
1.6 归并排序
1.6.1 基本思想
归并排序是一种采用分治思想、建立在归并操作上的有效排序算法。归并操作将已经有序的子序列合并，得到完全有序的序列。通常以每个子序列长度为1开始，两两合并成长度为2的序列，再继续进行归并操作，直到待排记录R完全有序。
1.6.2 时间复杂度
以二路归并为例，每次归并过程都是将两个有序子序列合并为一个有序序列，时间消耗是一个递推的过程。和其他二分递归问题类似，时间复杂度为O(nlog2n)。
1.6.3 空间复杂度和稳定性
归并排序过程需要和待排记录R等大的辅助空间，但是保持了原序列相同元素的前后位置关系。所以，归并排序的空间复杂度为O(n)，稳定的排序算法。
1.7 基数排序
1.7.1 基本思想
基数排序是一种分配式排序算法，也称作桶子法。基数排序根据键值的部分信息（例如数值最高位）将待排记录R分组，而后将分组后的待排记录排序并且按序组合，再按照键值的部分信息（例如数值次高位）分组，继续按序组合。重复相同的过程，直到遍历全部键值信息（例如数值最低位），待排记录R即有序。
1.7.2 时间复杂度
基数排序的时间复杂度和待排记录长度n、采用的键值部分信息（简称关键码d）以及d取值范围r有关，复杂度为O(d(n+r))。空间复
1.7.3 空间复杂度和稳定性
基数排序需要和待排记录R等大的辅助空间来存储原始排序记录，另外仍然需要rd个空间来辅助计数排序的过程。空间复杂度为O(rd+n)，保持了原序列相同元素的顺序，是稳定的排序过程。
2 实验与结果
本实验使用一台装配32位Win7系统，4G内存，core i5CPU的电脑，在Eclipse开发环境下进行。为了验证基本数据类型、数据泛型封装和代码实现（泛型）对算法的影响，实验首先采用正序和逆序的int型序列对算法进行测试，而后调用Java里面的随机函数生成随机待排序列进行实验。
2.1 算法性能测试
为了测试算法实际运行效率实验选取1000-50000间隔为1000的49组正序、逆序、随机的int类型数据进行5轮测试，计算每种算法的时间消耗平均值，绘制得到图1正序序列排序时间消耗图、图2逆序序列排序时间消耗图和图3随机序列排序时间消耗图。
对比3组实验对比折线图，可以看出各个排序算法实际效率和理论分析基本一致。BubbleSort、InsertSort和ShellSort表现出了对序列顺序的敏感性。HeapSort和MergeSort时间消耗比理论要高，甚至在逆序下耗时超过BubbleSort，其原因在于算法实现过程中引入了过多的条件判定操作、分配内存操作以及寻址操作，这些操作增加了算法的复杂度，致使程序本身的复杂度增大。至于HeapSort和BubbleSort效率相当，与序列是随机序列以及HeapSort操作破环了堆的随机性[8]存在关系。
2.2 测试序列数据类型对排序影响
为了观察基本数据类型是否影响算法效率，实验分别选取1000-50000间隔为1000的49组正序、逆序、随机的int、double基本数据类型数据进行5轮测试，计算每种算法的时间消耗平均值，得到表1实验结果。
算法的性能稳定性指的是随着数据规模的改变，时间消耗是否稳定变化，表现为时间消耗折线图的走势是否平滑。根据实验结果显示，BubbleSort、QuickSort和InsertSort性能稳定，其余算法稳定性较差。
基本数据类型影响着排序算法的效率，排序相同规模下的浮点型数据和整形数据，浮点型数据消耗略大于整形数据。
2.3 Java内部封装类对排序算法的影响
为了测试Java内部封装类[9]对排序算法的影响，实验同样进行了5次。每轮实验仍然调用Java随机函数生成50组范围1000-51000间隔为1000的实验数据，类型为Integer、int、Double和double，测试明确指定数据类型的7种排序算法。而后，计算5轮实验时间消耗的平均值，得到表2的实验结果。
根据表2中实验数据，可以看出Java内部的封装数据类型对排序算法存在影响，程度因算法而异。InsertSort和Radix Sort受影响较大，封装数据类型和基本类型时间消耗比例达到了4:1,MergeSort受影响最小，浮点类型封装数据Double排序效率超过了基本数据类型double，产生这种现象的原因和Jav对象的存储机制和内存的分配方式有关。总结起来就一般情况而言，封装数据类型会加大排序算法的开销，时间开销是基本数据类型的1.2到4倍。
2.4 泛型编程方式对排序算法影响
为了测试采用泛型[7]方式编写程序对排序算法效率影响，实验进行了5轮重复测试。每轮实验调用随机函数生成50组范围1000-51000间隔为1000的实验数据，数据类型为Inte ger和Double，测试采用泛型方式和非泛型方式编写的7种排序算法。而后，计算5轮实验时间消耗的平均值，得到表3的实验结果
根据表2的实验结果，可以得到采用泛型编写方式对算法效率存在影响，影响程度依据算法的不同存在差异。Insert Sort和HeapSort影响程度较大，MergeSort基本不受影响，产生这种差距的原因和Java自身的运行机制存在一定的关系。总体来说，采用泛型编程方式会加大排序算法的时间开销，约为非泛型编程的1.5-2.4倍。
3 结果分析
通过以上的实验结果，可以得出如下结论：
(1）排序算法的效率在很大程度上由算法的思想决定。
(2）算法的实际运行效率也依赖于书写代码的复杂度以及采用的基本操作类型等外界因素。
(3）排序算法效率和基本类型有关，排序相同排序规模的浮点型数据比整形数据耗时。
(4）使用Java内部封装类会影响排序算法效率，排序相同规模数据的时间消耗增加0.2-3倍。
(5）采用泛型方式编写程序会增加排序算法的时间消耗，为非泛型方式的1.5-2.4倍。
(6）根据实验数据显示，综合多种因素的影响，QuickSor和ShellSort表现出良好运行效率，符合[8]中的描述。
4 结语
排序算法的效率是由多种因素决定的，本实验验证了排序记录数据类型、数据封装以及代码的编写方式对排序算法的影响。但是影响算法效率的因素还有很多，在选择排序算法时应该综合考虑各种因素，以便做出最合理选择。
摘要：排序是计算机科学领域的一个基本问题。从算法时间复杂度、空间复杂度和稳定性的角度对常见的7种内部数值排序算法进行了理论分析。在Java平台下测试了7种算法的执行效率,指出了算法的执行效率不仅和算法设计思想相关,基本数据类型、数据封装,以及代码实现方式都影响算法的执行效率。同时进行了实验对比数据,为排序算法的选择提供一定的参考。
关键词：内部排序算法,效率,数据类型,数据封装
参考文献
[1]Dongarra J.The top 10 algorithms[J].IEEE Computing in Science&Engineering,2000,2(1):22-23.
[2]江燕,周军,等.内部排序算法的表分析[J].电脑编程计数与维护,2014,12:23-24.
[3]吴伟娜,等.常用排序算法的比较分析[J].电脑知识与技术,2013,03:2416-2147.
[4]张静.常用的排序算法的分析与比较[J].河西学院学报,2010,02:26.
[5]淦艳,等.五种排序算法的性能分析[J].重庆文理学院学报,2016,06:45-50.
[6]杨智明.希尔算法实现与分析[J].软件与开发,2010,02:13-14.
[7]Joshua Bloch.Effective Java[M].北京.机械工业出版社,2009:97-102.
[8]Mark Allen Weiss.数据结构与算法分析:Java语言描述[M].北京.机械工业出版社,2008:77-125,183-219.
改进的双向选择排序算法 篇8
为了采用查找效率较高的查找法, 通常希望待处理的数据按关键字大小有序排列, 因而排序是计算机程序设计中的一种基本操作[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.
一种极速排序算法 篇9
1 源程序 (以VFP为例)
DIMENSION A (1001) //定义数组ASTORE 0 to A//初始化数组A?'排序前的数值'+CHR (10) I=0do whil I<100
2 结论
算法的高效与否与数列中数字间的比较次数有直接的关系, 比较次数越多效率越低, 运算速度越慢。极速排序之所以高效是因为在程序运算过程中没有进行一次数字间的比较, 采用这种排序算法可直接提高程序执行的速度, 进而提高整个软件的性能。
运行结果:
排序前的数值
排序后的结果
摘要：本文通过对一组整数进行排序算法的研究, 采用一种新的算法利用简单的循环, 没有进行一次数字间的比较, 就实现很快速的排序。
关键词：排序算法,合并排序,入排序,冒泡排序,单循环
参考文献
[1]章立民.FoxPro命令与函数实用详解.学苑出版社, 1994年.
冒泡排序动态演示算法设计 篇10
关键词：程序,循环,冒泡排序,算法
一、引言
程序设计是大学工科学生一门必修课, 排序算法是计算机数据处理中常用的一种算法, 因此在程序设计教学中占据非常重要的地位, 尤其是冒泡排序算法非常经典, 学生在学习程序设计课程时冒泡排序是程序设计课程必学的一个重要算法。冒泡的思想学生基本上都能理解, 但是到程序设计的时候, 学生就无从入手, 学生在学习冒泡排序时, 总是觉得非常难学懂, 有畏惧心理, 总觉得学不好, 认为一维组数怎么会用到二重循环, 用一重循环编程不就可以了吗;如何教会学生学会排序算法, 一直引起教师们的注意和思考, 我们也经常讨论怎样的讲课方法, 怎样的教学方法才能使得学生轻松学会程序设计, 特别是学习一些经典算法, 使学生们学习起来不觉得困难;我们通过多年的教学实践, 总结出冒泡排序教学的有效方法, 自己设计一个冒泡排序的动态演示算法, 让学生一步一步对照冒泡算法, 程序执行到哪一步, 程序发生了什么变化, 变量的存储单元的值有发生哪些变化, 使学生一目了然算法的基本执行情况。
二、冒泡排序设计的基本框架
在教学中, 我校以学生为中心, 学生是教学的主体, 按照培养目标, 我们以学生的认知规律和学习特点安排教学;从学生的实际情况出发, 实施教学的每一个环节, 调动学生学习的积极性, 引导学生主动学习、激发学生的学习兴趣。冒泡法排序就是首先调动学生的积极性, 活跃课堂, 强调课堂师生互动, 才能使学生逐步理解。
现在冒泡算法讲解一般采用PPT的演示[1], 也有一些用Flash等演示, 这些方法致命的缺点, 就是不能动态地反应程序在计算机内部执行的情况, [2][3]文中的动态还不能反映存储的动态变化。我们设计的算法从头到尾, 从数据到存储的变化, 就是动态变化, 只要输入的数据不一样, 程序执行的过程就不一样, 完全是动态执行和存储动态变化。示例如下:
冒泡排序的动态算法演示, 有助于学生理解算法, 以下是冒泡排序的动态算法演示的框架结构的基本步骤。
1. 手动排序, 单击鼠标一步一步执行, 让学生看得明明白白。
2. 自动排序, 主要是演示, 让计算机自动一步一步执行冒泡排序的算法, 并且可以设定每一步显示时间的秒数。
3. 手动和自动之间任意切换。
4. 每执行一步变量发生变化, 立刻在文本框中显示出来。
5. 程序的每一步执行过程都以高亮度把源程序显示, 明确已经程序执行到那一步。
6. 每执行一步, 程序在做什么事情, 左边的数组流程图和右边的程序一一对应, 便于学生对应理解。
7. 冒泡算法的基本步骤和设计思想显示。
三、冒泡排序动态演示的实现过程
冒泡排序动态演示的设计, 重要的是要设计2个定时器, 定时器的目的主要是为了程序执行时, 什么时候单步执行, 什么时候自动执行, 什么时候停止程序运行, 当激活定时器时, 程序就自动执行, 当定时器设为不可用时, 程序就自动停止执行。
开始把冒泡算法的整个源程序通过加载在窗体的右上角的列表框中显示出来, 然后在窗体的左边显示n个文本框和文本框对应的标签, 文本框就是放数组, 标签就是数组的编号, 目的为了显示排序的过程和结果。窗体下面显示冒泡排序的设计思想, 中间显示存储单元的变化情况, 以及命令按钮。
刚开始定时器1和2都设为不可用, 把冒泡排序的程序放在时钟Timer1＿Timer () 和Timer2＿Timer () 中, 用多分段语句把冒泡算法放在各个多分段语句中, 其中设一个计数器, 用于多分段语句的执行次序, 当单击手动按钮时, 就是调用定时器1, 由于没有激活定时器1, 每调用计时器一次, 就像普通的过程调用, 定时器就计数器所对应的语句执行一次;当在Timer1＿Timer () 中执行到内循环时, 调用定时器2, Timer2＿Timer () 主要是为了执行数组的排序过程, 以及数据的下沉和上浮, 同时对数组中数据的颜色显示, 以及存储单元的变化, 那么就是单步执行, 我们也称手动操作。
如果是自动演示, 只要在命令按钮中把定时器1设为“true”, 并且设置每执行一步的秒数, 程序就会在定时器中反复执行, 当要执行到内循环时, 停止定时器1, 即把定时器1设为“false”, 定时器2设为“true”, 同样定时器2执行完毕, 又把定时器1设为“true”, 定时器2设为“false”, 定时器1有启动了。
排序算法设计的引伸教学的思考, 动态冒泡排序算法可以延伸到程序设计中任何算法和程序, 同样可以延伸到其它学科的动态演示[5]。
四、总结
由于冒泡排序相对比较难学, 我们自己编制了一个“基于动态的冒泡排序自学习演示算法”, 结合讲课方法, 边讲解边演示, 也可以帮助学生在平时自己复习和学习, 这种程序动态的变化, 包括存储单元值的动态变化, 使学生一目了然看清程序每一个语句的执行情况和存储单元变化的情况, 更有利于学生快速地掌握选择法排序的算法, 不管在何时何地, 只要有电脑的地方都可以方便地学习。
教学方法探讨无止境, 这种教学方法实际上和选择法排序算法有很多相似之处, 只要学生学会了冒泡排序算法的基本思想, 很容易推广到选择法排序算法和其它排序算法, 学生也比较容易学会;如果有条件的学校, 编制一些其它排序的算法, 然后让学生编一个其它排序的算法, 教师给出一些提示, 要求学生编完程序以后和选择法排序和冒泡排序作一些比较, 那个算法更优, 对以后的学习学生的编程兴趣和积极性会更高, 可以充分调动学生学习的主动性, 激发了学生学习程序设计的热情和兴趣, 同时也培养了学生的思考能力和解决问题的能力, 做到了事倍功半的效果。
我们不仅编写了C程序设计的冒泡算法, 而且还设计了C和VB的一整套动态演示算法, 包括选择法排序、if…else、switch、for、while、do…while、求素数、求最大值等一系列动态演示算法, 以后准备设计成一个CS结构的C程序设计和BS结构的动态演示系统。这些算法只要学生肯学, 一定能让学生会学会程序设计, 除非学生不学。本文交流的目的就是想达到一个抛砖引玉的作用, 大家共同来探讨程序设计的教学方法, 提高教学质量。
参考文献
[1]杜素芳.“排序算法的实现”教学探索[J].福建电脑, 2011, (2) :213-214.
[2]胡晓芳, 李欣.基于Flash制作的算法演示动画的设计[J].中国教育技术装备, 2009, (8) , 45-47.
[3]冯娜, 孙义欣.基于冒泡法排序的动态演示程序[J].电脑知识与技术, 2009, 5 (5) :1175-1178.
[4]刘娜, 佟冶.归并排序算法实现的理解与教学过程[J].计算机教育, 2007, (9) :66-68.