五种排序算法的性能分析

排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除.通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂性和空间复杂性,指出5种排序算法可分为平方阶排序和线性对数阶排序两类.通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则:当记录较小时,可采用插入或选择排序;当记录基本有序时,可选用插入或冒泡排序;当记录较大时,则应选择快速排序或归并排序.     

快速排序的改进算法

对快速排序算法进行了改进,根据在待排序列基本有序的情况下,插入排序有较好的性能特点,在改进算法中,只对长度k大于的子序列递归调用快速排序,最后再对整个序列用插入排序方法排序,我们得到了时间复杂性为1.386 nlog(n/k) nk/4 3(n 1)/(k 1) O(logn)的排序算法,当k取值为8左右时,改进算法的性能较隹.     

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

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

一种改进的归并排序算法

提出了一种改进的归并排序算法.采用非递归方法,对记录集从头至尾顺序地进行扫描,并将相邻的两个有序序列合并成一个整体.该算法较2_路归并排序算法更简单,更易理解,同时也取消了栈空间.     

基于Mealy机的蒙古文排序算法

排序是语言文字信息处理中的重要工作之一,它的目的是将单词(或词组)的任意序列重新排列成按关键字有序的序列,从而优化存储结构,提高检索速度.但由于蒙古文排序习惯和其"UCS"编码的特殊性,单词排序不能完全依靠字符编码的自然顺序.单词的排列顺序不仅与字符编码有关,而且与字符状态有着密切的关系.因此先给出字符状态和词状态的定义,然后提出一种基于Mealy机的字符串排序算法.该算法是传统的字符串排序算法的一种扩展,主要解决了编码相同状态不同情况下词的排序问题,并且在传统蒙古文排序中的应用证实了算法的有效性.该算法具有很好的适应性,能够解决其它一些复杂文本语言的排序问题.     

冒泡排序算法的分析与改进

冒泡排序算法有两个优点：1＂.编程复杂度＂很低,很容易写出代码;2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,但当需要排序的数据较多且无序时,冒泡排序算法的时间复杂度较大,比较次数较多,本文提出了一种冒泡排序算法的改进方法,可以大大减少比较的次数,降低算法的时间复杂度。     

双向自然合并排序算法

双向自然合并排序是根据欲排序数据局部不是升序就是降序的自然有序特点，先线性扫描出自然有序的子数组段，再进行合并排序．扫描时的有序数段长度越长，段数越少，对应合并树的层数就会越少，算法的效率越高．     

一种改进的计数排序算法

提出了一种改进的计数排序算法。首先找到待排序记录应该存放的位置,然后在原数组空间上进行交换。与传统的计数排序算法相比,在不改变时间复杂度的同时,降低了空间复杂度,提高了算法性能。     

基于多线程归并排序算法设计

为解决传统递归方式的归并排序算法串行执行效率低的问题, 使用数据依赖关系分析方法对归并排序算法进行并行性分析。通过分析发现算法本身具有并行的特征, 在多核处理器下使用OpenMp编译制导语句对算法进行直接并行化处理。在数据量较大的情况下, 为了使算法执行的速度更快, 在多核处理器系统中设置多个线程, 并将序列分成多个组, 每个线程操作一组数据, 最后对多个局部有序的结果进行逐一合并。实验验证结果表明, 该并行化算法可使执行速度提高50%以上。     

对层次聚类算法的改进

介绍了层次聚类算法的基本思想,在原算法的基础上,通过对类间距离进行预排序从而避免合并类时重新计算类间距离,该算法降低了计算的复杂度．实验表明,改进后的算法在与原算法聚类效果相同的情况下运行速度明显提高．     

常用排序算法时间开销的实验统计分析

以数值数据为排序对象,对交换排序、冒泡排序、选择排序、插入排序、归并排序以及快速排序等常用的六种排序算法的时间复杂度从实验统计角度进行分析和对比.本实验统计数据分析可知具有相同定性指标的排序算法,可能实际时间效率有着很大的差异,这组实验数据可为实际应用中排序算法的选择提供参考.     

基于FastICA的低信噪比雷达信号分选算法

针对传统的基于参数的信号分选系统已无法适应当前复杂情况下的雷达信号分选问题,将基于独立分量分析(ICA)的盲源分离算法引入雷达信号分选算法.快速ICA(FastICA)算法结合了定点迭代和非高斯最大化算法,具有稳定性好、收敛速度快、计算量小等优点.但该算法对噪声非常敏感,无法在低信噪比情况下进行信号分选.针对这一缺点,引入同步累加平均降噪算法,并结合信号均衡、平滑处理进行改进,使得新算法在低信噪比情况下对雷达信号进行分选.仿真表明改进后的算法在低信噪比情况下具有良好的分选效果,并保留了原算法的优点.     

无序数组的最大有序序列

从现实世界的游戏规则出发，讨论在不打破原向量本身次序的基础上寻求一个最大的有序序列的算法问题（可能同时存在多个增序（或降序）序列，但本文讨论增序问题）。     

一种基于堆的快速排序算法

堆排序算法具有低时间复杂度和低空间复杂度的优点;但对原始序列的有序性不敏感。快速排序算法是在平均情况下公认的高速算法;但有较高空间复杂度。对两个算法扬长避短,设计了一种新的排序算法HQSort;并从理论和实例两个角度分析了该算法的效率,在不同量级的数据集上对该算法和三种经典排序算法进行了对比运行和测试,验证了该算法不仅在时间效率上优于其他算法,而且在辅助存储空间上比快速排序算法减少约50%。     

数据等概率分档统计插入排序算法

提出了一种按数据等概率分档的排序算法,此算法应用现代统计学的一些知识和技巧,结合传统的排序算法,对具有一般分布的数据进行排序,使排序的运算量为O（n）,达到了排序运算量的下限,实验表明,在n较大时此算法效率要优于现有的同类排序算法。     

基于分治策略的排序方法的比较研究

讨论了运用分治策略的思想实现快速排序、归并排序和堆排序三种排序算法,从分、解、合三方面剖析排序,从而得出分割方式是影响排序效率的关键,并将分治法扩展应用到更多排序方法中.     

一类基于冒泡排序的改进算法的分析与比较

排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且还直接影响着计算机的工作效率．目前排序领域许多最简单的算法都是基于冒泡排序算法，该文对这些算法的基本原理进行了介绍和分析，并对它们的算法性能进行了比较．     

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

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

基于脉内特征的雷达信号分选方法

当前复杂的电子环境下不同调制的多种雷达信号,具有交叠严重、分选困难的特点。针对这一问题提出一种基于时频原子特征的雷达信号分选方法。该方法根据欧氏距离准则,在超完备的Chriplet时频原子库中,利用杂草算法提取可分性较好的原子,并与各信号做内积作为雷达信号分选的特征值,利用改进的FCM聚类算法进行聚类。在不同信噪比下,对5种不同调制参数的雷达信号进行分选,仿真结果表明,在较低的信噪比下,该方法能够进行有效的雷达信号分选。     

带索引的排序方法

提出了适用于多种排序法的带索引排序和基于带索引排序方法的记录环移动算法,并对所提算法复杂度进行了分析。实验结果表明,在一定条件下,带索引排序方法使算法的时间复杂度有明显的改进。