共查询到20条相似文献,搜索用时 15 毫秒
1.
冒泡排序算法及其改进算法的实验分析 总被引:1,自引:0,他引:1
排序是计算机科学的基本问题之一.通过描述传统的、带标记的、双向的和交替排序四种冒泡排序算法,总结出它们的时间复杂度为O(n2)和空间复杂度为O(1).通过编程验证了四种排序算法在不同随机度情况下的性能,指出它们的适用原则:当随机度比较小时,应选取非传统冒泡排序算法;当随机度比较大时,则应选取传统冒泡排序算法.实验表明,四种算法的时间消耗与输入序列的规模近似地呈指数曲线关系,传统冒泡排序算法的时间消耗与输入序列随机度近似地呈水平直线关系,而其它三种算法的时间消耗与输入序列随机度呈40?左右的斜线关系. 相似文献
2.
刘怀辉 《山东师范大学学报(自然科学版)》2007,22(2):34-36
阐述了冒泡排序算法设计的基本思想、实现步骤,并通过Visual Basic编程予以实现,指出其效率不高的缺陷,提出了对冒泡排序改进的标志变量法及其编程实现,其效率及性能较冒泡排序算法有一定程度的提高.同时对冒泡排序及其改进算法进行了时间复杂度、空间复杂度和稳定性的分析和比较. 相似文献
3.
排序算法的分析与比较实现 总被引:1,自引:0,他引:1
本文论述了内部排序的几种算法,在思想、时间复杂度、空间复杂度及稳定性方面进行了比较。最后用C#语言比较了几种算法在大量数据中进行排序的比较次数和花费的时间。 相似文献
4.
郑明秀 《西南民族大学学报(自然科学版)》2015,41(6):723-726
以数值数据为排序对象,对交换排序、冒泡排序、选择排序、插入排序、归并排序以及快速排序等常用的六种排序算法的时间复杂度从实验统计角度进行分析和对比.本实验统计数据分析可知具有相同定性指标的排序算法,可能实际时间效率有着很大的差异,这组实验数据可为实际应用中排序算法的选择提供参考. 相似文献
5.
鸡尾酒算法是一种基于双向遍历的排序算法,相比于传统的冒泡排序算法在排序效率上有一定的提高,但仍存在大量的重复数据比较以及对初始输入序列随机度过于敏感等问题.针对上述问题,引入了一种鸡尾酒排序算法的改进算法(Trigger-Conditional Cocktail Sort Algorithm,简称T-CCS).通过记录... 相似文献
6.
陈崚 《中国科学技术大学学报》1994,(2)
本文提出一种在SIMD-EREW计算模型上实现的并行排序算法.算法采用基数交换排序方法,在处理过程中无存贮访问冲突.对长度为n的序列,算法使用不超过个处理单元,时间复杂度为O(u.log2n),其中u为不超过处理器字长的常数.该算法适合于具有较多重复元素的序列排序. 相似文献
7.
针对传统排序算法的比较思想 ,提出了一种简单而快速的排序算法 ,尤其在非均匀分布下的数据效果更加明显 ,该算法在最坏情况下待排数据较多较大时的时间复杂度为O(n) . 相似文献
8.
陈Leng 《中国科学技术大学学报》1994,24(2):243-246
本文提出一种在SIMD-EREW计算模型上实现的并行排序算法。算法采用基数交换排序方法,在处理过程中无存贮访问冲突。对长度为n的序列,算法使用不超过n/2个处理单元,时间复杂度为O(u.log2n),其中u为不超过处理器字长的常数。该算法适合于具有较多重复元素的序列排序。 相似文献
9.
10.
堆排序算法具有低时间复杂度和低空间复杂度的优点;但对原始序列的有序性不敏感。快速排序算法是在平均情况下公认的高速算法;但有较高空间复杂度。对两个算法扬长避短,设计了一种新的排序算法HQSort;并从理论和实例两个角度分析了该算法的效率,在不同量级的数据集上对该算法和三种经典排序算法进行了对比运行和测试,验证了该算法不仅在时间效率上优于其他算法,而且在辅助存储空间上比快速排序算法减少约50%。 相似文献
11.
通过研究希尔排序算法的机制,以不同增量序列对一些规模较大的待排序列进行试验,分析其时间复杂度与增量序列的关系,探索具有最优渐近时间复杂度时的增量序列及其选择方法。 相似文献
12.
应用信息熵原理研究排序算法的效率 总被引:1,自引:0,他引:1
齐国清 《大连海事大学学报(自然科学版)》2002,28(1):85-88
应用信息熵的概念表示序列的无序程度并分析基于关键字间的比较的排序算法的效率,首先讨了序列的信息熵的定义,证明了序列的信息熵即为基于直接比较的排序方法所需的比较次数的理论下限,然后利用信息熵原理分析了插入排序和归并排序的效率,指出当序列长度大于4时,任意直接插入排序的比较次数大于理论下界,最后探讨了利用熵原理寻找比较次数最少的排序方法。 相似文献
13.
提出了一种基于哈希函数的超“快速排序”算法。根据数组下标递增的特点,对待排序的任意整数序列建立有效的哈希函数,通过循环映射链接完成排序。分析了算法的时间和空间复杂度,实验验证了算法的运行效率。结果表明:算法的时间和空间复杂度均为O(n),在问题规模较大时,效率优势明显。 相似文献
14.
陈思思 《邢台师范高专学报》2008,(4):107-109
介绍排序的基本概念以及几种常用的排序算法,通过分析它们的算法和各自的时间复杂度、空间复杂度等,对这几种算法进行比较和选择,给出这几种排序算法的改进方法。 相似文献
15.
贺清碧 《重庆文理学院学报(自然科学版)》2004,3(1):45-48
排序算法对于计算机信息处理很重要,一个好的排序不仅可以使信息查找的效率提高,而且还直接影响着计算机的工作效率目前排序领域许多最简单的算法都是基于冒泡排序算法,该文对这些算法的基本原理进行了介绍和分析,并对它们的算法性能进行了比较. 相似文献
16.
为改进直接选择排序算法的不稳定性及对数据的不敏感性,笔者研究了表选择排序算法.该算法约定用静态链表存储待排数据,先创建有序链表,再根据链接信息将数据顺序存储.此算法不仅保证排序算法的稳定性,也使时间复杂性由原来的O(n~2/2)在最好和平均情况下分别降到O(n)和O(n~2/4)(最坏情况不变),另外还保证后续其他操作也同样具备顺序存储的优点.从排序稳定性、数据比较次数和移动次数三方面来看,本文中提出的排序算法在简单排序算法中是最优的. 相似文献
17.
18.
通过分析任意输入的n个数据的组成特性,设计一种O(n nlog2m)时间复杂度的排序算法,m为原始输入数据序列中有序/逆有序的子序列个数,1≤m≤n/2。此排序算法的时间复杂性结果与输入数据的概率分布假设无关。 相似文献
19.
20.
张勤 《高等函授学报(自然科学版)》2012,(2):85-87
本文首先总结排序算法的发展现状和分类,然后对内部排序中的交换排序和插入排序做了进一步的研究,包括对其基本思想和实现方案的研究。在基于冒泡排序和简单插入排序的基础上更深入的研究了快速排序和希尔排序这两种更为有效的排序方案并分析和比较这些算法的性能。 相似文献