排序算法的比较、选择及其改进

排序是计算机科学中最重要的研究问题之一。在对常用的几种排序算法进行了综合比较的基础上,本文提出了在实际应用中如何选择排序算法的一般原则,同时也给出了一些算法的改进策略及其C语言实现。     

一种基于有序双端链表的高效排序算法

本文提出一种新的基于有序双端链表的比较排序算法,即ODListsort(ordered double-end linked list sort)算法。该算法首先要定义一个可共存的链表最大数量,然后通过生成链表、根据规则插入数据以及合并操作来对数据集进行排序。在ODListsort算法中,数据元素是以链表形式进行动态内存分配的,因此它比一些经典的排序算法性能更优。实验结果表明,对于随机数据集,ODListsort排序与快速排序的速度接近,比归并排序、选择排序、插入排序以及冒泡排序的速度更快;对于有序数据集,ODListsort排序的效率远超快速排序,略高于归并排序。     

快速稳定表选择排序算法研究

为改进直接选择排序算法的不稳定性及对数据的不敏感性,笔者研究了表选择排序算法.该算法约定用静态链表存储待排数据,先创建有序链表,再根据链接信息将数据顺序存储.此算法不仅保证排序算法的稳定性,也使时间复杂性由原来的O(n~2/2)在最好和平均情况下分别降到O(n)和O(n~2/4)(最坏情况不变),另外还保证后续其他操作也同样具备顺序存储的优点.从排序稳定性、数据比较次数和移动次数三方面来看,本文中提出的排序算法在简单排序算法中是最优的.     

一种基于元搜索引擎的排序算法

本文在研究元搜索引擎及排序算法的基础上,提出了一种基于元搜索引擎的加权Borda排序算法,该算法通过权重信息来推荐成员搜索引擎,为元搜索引擎在海量数据搜索中提高查全率和查准率提供帮助。     

《数据结构》中有关排序算法的教学研究

本文阐述了《数据结构》中主要排序算法的教学方法 ,并进一步启发学生对有关排序算法进行改进 ,以加深其对算法的掌握和理解。     

基于Map/Reduce的分布式数据排序算法分析

为了解决大规模数据的存储与计算,近年来分布式系统得到了大量的应用.如何在分布式系统中对大规模数据集进行排序是影响许多应用性能的基础问题,其中不仅涉及每个节点上排序算法的选择,更重要的是设计协调各节点的分布式算法.本文总结了分布式系统中常用的分布式排序算法,对每种算法的执行流程、代价模型和适用场景进行了分析,并通过实验对分析结果进行了验证.本文的工作可以帮助开发人员选择和优化分布式环境下大规模数据排序的算法.     

可行的排序算法探讨

本文分析了三类排序算法的优点和缺点,给出了必要的证明,探讨了研究可行的排序算法条件。此外,本文把第三类排序算法引入了并行算法。     

排序算法的比较与选择研究

影响排序效率的因素有很多,首要因素是使用的算法;其次是为实现算法而进行的程序编制。算法时间复杂性的“0”表示法反映了渐近特性,但不能作为选择排序算法的唯一和最佳依据。本文指出了影响排序效率的各种因素,在实际中还需要根据这些因素选择不同的算法;文章还给出了几种排序程序的选择前提,分配排序的程序在执行时间上具有明显的优势。文章还给出了几种排序程序的实验数据,这些数据表明当待排序数据较多时,分配排序的程序在执行时间上具有明显的优势。     

均值加速中值滤波算法

本文介绍一种均值加速中值滤波迭代算法,该算法不需要对所有像素的邻域值进行排序,而是对像素的邻域值有选择性的排序,排序后的中值直接替代原像素值。理论分析与实验结果表明:该算法能有效地降低中值滤波算法的时间复杂度,可将常用的快速排序算法复杂度(ONlnN)简化为O(N(1 lnN)/2),且去噪声效果良好,在图像处理中有广泛的应用前景。     

排序算法在文档资料整理工作中的应用

本文以试卷整理工作过程中排序方法的应用为例,详细分析阐述了数据结构中各种排序算法在日常文档资料整理工作中的实际应用。     

排序算法的分析与比较实现

本文论述了内部排序的几种算法,在思想、时间复杂度、空间复杂度及稳定性方面进行了比较。最后用C#语言比较了几种算法在大量数据中进行排序的比较次数和花费的时间。     

逻辑堆与树排序

树排序算法是堆排序算法的变体，本文给出了逻辑堆的结构并将其应用于树排序算法中使得树排序算法的最坏复杂度由原来的４ｎｌｏｇｎ＋Ｏ（ｎ）降低到２ｎｌｏｇｎ＋Ｏ（ｎｌｏｇｌｏｇｎ）＋Ｏ（ｎ），接近于最优堆排序算法（复杂度为ｎｌｏｇｎ＋ｎｌｏｇｌｏｇｎ＋Ｏ（ｎ），并且对几乎已有序的输入，算法的复杂度为Ｏ（ｎｌｏｇｌｏｇｎ），这在ｎ＜２１８的实际应用中基本保持了原树排序算法的优势．     

关于构造关系传递闭包的三个算法

在本文中,阐明了如何由给定结点集上的二元关系来构造其关系传递闭包并给出三个有关的算法。 第一个是改进了的Warshall算法,当用计算机实现时,它可比原Warshall算法节省许多时间和空间。 第二个是排序算法,本文指出:结点的排序对所有使用布尔矩阵的算法的运算效率有严重影响,而此排序算法将给出结点的合理排序,它将进一步提高Warshall算法以及上述算法的效率。 我们还提出了第三个算法,它适用于结点数少于30左右的情况,此算法中使用了一个简单图解方法,它可直接从给定的关系图中得出传递闭包。     

快速多次分组排序法

本文给出了一种快速排序法。本算法中每次分组后,只有数据个数少于阈值E(≥15)的那些组用直接挑选法排序,其余各组必须再次分组。在每个数据都是均匀分布的随机数的假定下,严格论证了本算法的总计算量少于一次分组排序的算法,并且得到最优阈值为15。     

三种常用内部排序算法探讨

排序是计算机程序设计中一项经常而又重要的操作,研究排序算法具有重要的理论意义和广泛的应用价值。本文论述了常用的三种内部排序算法,并比较了它们的异同,最后得出一定指导意义的结论。     

一种基于排序理论的精确直方图规定化算法

本文提出了一种基于排序理论的精确直方图规定化的算法,该算法通过把离散情形的统计模型在一个K维空间里进行转化,在图像像素中诱导出一个严格排序,从而得到一个可逆的累计分布函数,并且给出了实验结果和诱导排序的统计模型.     

基于后缀数组的快速排序算法

在搜索技术和各种流行的排序算法优缺点比较的基础上,给出了一种基于后缀数组的新的快速排序算法,该算法在时间和空间性能上均优于传统的快速排序算法;并在同等的条件下,用该方法与快速排序算法对相同的内容进行排序,结果表明:该算法特别适用于大文本的排序问题,可用于搜索技术和数据压缩中.     

排序算法时间复杂度的实验统计分析

本文叙述了各种排序算法的伪代码表示方法,并针对各种排序算法,描述如何利用实验方法进行算法时间复杂度的统计计算,在此基础上,叙述如何开发一个应用软件来对各种算法的时间复杂度进行横向和纵向比较分析,得出各类算法的评估结论。统计分析的结果可直接应用于软件的设计和编码中。     

Moore-Hodgson算法最优性的新证明

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore-Hodgson算法可以在时间O(nlogn)内得到误工问题的最优解。虽然经过改进,然而Moore-Hodgson算法最优性的证明仍然非常复杂。本文给出Moore-Hodgson算法最优性的一个非常简洁的新的证明。由于误工问题在排序论里的重要性,本文给出的新的证明在理论上是有重要意义的,是可以为排序论的专著和教材所采纳的。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有"一致性"关系的排序问题,或者工件的加工时间与工件的权有反向"一致性"关系的排序问题等,也可能有简洁的证明。     

一种改进的起泡排序算法

本文给出了一种改进的起泡排序算法．改进后的起泡排序算法与经典的起泡排序算法相比，通常可以减少排序过程中总的比较次数．用ＰＡＳＣＡＬ语言描述的与算法有关的类型定义和变量说明如下：ＴＹＰＥｎｏｄｅ＝ＲＥＣＯＲＤｋｅｙ：ｉｎｔｅｇｅｒ；ｉｎｆｏ：ｄａｔａｔ...