五种排序算法的性能分析

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

无监督排序学习算法的一致性比较

对于无监督的排序学习算法来说,排序结果的评价指标是非常具有挑战性的问题.从一致性的角度,比较了4种比较典型的无监督排序学习方法,并在机器学习标准数据库中进行实验比较分析.结果显示,RPC这种非线性的无监督排序融合方法产生的排序结果有最小的Kendall距离和Spearman简捷距离,体现了RPC在无监督排序方法上的优越性.     

SIMD-SM模型上的奇偶排序算法

Batcher排序网络在排序深度上不是最优的,但由于有较好的并行性和时间复杂度,因此许多并行排序算法都基于Batcher排序网络.通过观察Batcher奇偶排序网络,提出在SIMD SM模型上的一种奇偶排序算法.该算法占用n/2个处理器,在○(log22n)时间里排序n个关键字.     

单台机器排序问题中工件的预排序

在排序问题中,为了寻找一个工件的加工次序,有时需要对原来工件进行重新编号,即对工件进行预排序.例如用动态规划求解工件有先后约束关系的单台机器排序问题时,需要对工件进行预排序,使得先加工的工件的序号小于它的后继工件的序号,且使得某种指标达到最优.对于工件之间的先后关系呈链状结构的单台机器排序问题,给出了一个算法,并证明了该算法是最优的.对于工件之间的先后关系呈树形结构的单台机器排序问题,也给出了一个算法,并证明了对于某些特殊的树形结构的单台机器排序问题,该算法是最优的.     

基于串行计算的排序算法实证分析

文章简述了排序算法的研究现状,着重分析地址映射计数排序的基本思想,提出了相异密度因子的概念,以快速排序为参照系,通过理论分析和实验数据的实证分析验证,表明相异密度因子是应用领域选择合适的排序算法的重要参考因素,最后指出了排序算法的研究新趋势.     

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

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

基于排序互信息的无监督特征选择

根据排序问题的单调先验知识,无监督学习问题中的观测属性之间也具备单调关系;否则该属性与排序无关,为冗余属性.基于排序互信息反应的两属性之间的单调关系,提出用每个属性与其他属性之间的平均互信息,来衡量每个属性与排序学习的相关程度,具有最高的平均互信息即为排序最相关的属性.     

三种高效排序算法性能分析

排序是计算机科学中的基本操作,快速排序、堆排序和归并排序是三种常用的效率较高的排序算法.为便于理解和掌握,并为具体问题选择适合的算法提供借鉴和依据,本文详细阐述了每种算法的基本思想和实现步骤,给出了每种算法的时间复杂度的推导过程,分析了每种算法的稳定性和适用情况.     

一种改进的行和归一化排序方法

提出了一种改进的行和归一化排序方法(INRAM), 从保序性、置换不变性、相容性和累积优势度等方面对该方法的合理性进行了研究, 并且利用互补判断矩阵和互反判断矩阵之间的转换公式, 给出了相应的求解互补判断矩阵排序向量的算法, 从而丰富和发展了互反和互补判断矩阵的排序理论. 最后,通过算例将NRAM法和INRAM法与特征根排序方法(EM)及对数最小二乘法(LLSM)作了对比分析. 数值结果表明: INRAM法不仅简洁易行, 而且与EM 法的排序结果完全一致, 故能较好地揭示方案的真实排序.     

公共交货期窗口待定的单机成组分批排序

研究有组安装任务的单机窗时排序问题,所有工件的提前/延误惩罚费用相同;公共交货期窗口大小给定但位置待定,由线性定位费用衡量;最优排序是使所有这些费用的和最小.给出了最优排序的一些性质,提出一个多项式时间算法.     

一个高效的外排序方法

针对外排序存在的困难，给出了一种高效的外排序方法．利用分段的思想将内、外排序算法结合起来，减少计算过程中读写外存的次数，从而提高速度和效率，算法复杂性为Ｏ（ｎｌｏｇ２ｎ），通常数百万的排序数据仅需读写磁盘二三遍便可完成排序，大大地减少读写磁盘遍数．本算法既适合内排序，也适合外排序     

利用通用排序函数实现日期排序

通用排序函数是将各种类型数组的元素进行排序的函数．而日期型数据比较特殊，使用通用排序函数实现日期型数据排序，必须做一些特殊的处理．首先，把日期型数据转变成单个的数，然后把这些数存于数组，利用通用排序函数进行排序，最后将排序后的数组转变成日期输出．     

后置群决策问题的一种集结方法

针对后置群决策问题 ,提出个体排序的位置得分函数 ,用来反映个体偏好在群决策中的价值 ,在考虑个体权重的情况下 ,用位置偏差系数来反映个体间偏好差异 .建立了一个群决策的位置指标公式 .讨论了它的一些排序性质 .通过实例说明了其作为群排序指标的合理性 .     

一种改进的基于编号的选择排序方法

排序是计算机程序设计中的一种重要操作,在现有的排序方法中,多数情况都是对数据原始排列顺序的一种破坏,一旦进行了排序,数据原始存储顺序就发生了改变,若想再基于数据原始排列顺序进行其他操作也就困难了.排序只是对数据的一种分析手段,对数据记录并不需要一定将其排列有序,只需要对它做好排序准备,在需要排序时再进行排序操作.文中基于应用对选择法排序做了改进,同时,在选择法一次只能选一个的基础上,提高成一次可以确定两个记录,这样也提高了排序效率.     

任意分布数据的映射归并排序算法研究

针对银行业务管理、高考成绩统计、气象资料整理等一类特殊“汇总”排序问题。文中提出了一种以映射、链接和归并为基础的新排序算法－映射归并排序算法（以下简称为“映射归并排序”）,给出了该排序算法的描述、时间复杂度分析及用C语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明：映射归并排序方法和待排序数据分布无关,其时间复杂度仅为O（N）;而且在处理上述大规模“汇总”排序问题时,映射归并排序速度明显优于Flash Sort,Proportion Split Sort,2－路重复的K路归并排序和直接K路归并排序等算法。     

常见排序算法多线程实现与比较

目的 对目前常用排序算法进行多线程实现,并运用不同类型数据集进行比较研究,以充分利用现代计算机多核处理器优势,有效提高大规模数据排序操作。方法 首先简要介绍目前常用的11种排序算法的基本原理,然后基于Go语言采用多线程模式进行代码实现,最后用3种不同类型测试数据进行详细比较,分析这些排序算法的优缺点及适用范围。结果 对于同一个排序方法,多线程可以明显提高排序效率,但相同规模数据条件下,不同的数据类型影响排序效率。结论 多线程排序能够充分利用计算机多核资源,提高排序效率。对于大规模数据,多数排序方法都可以快速得到排序结果。     

基于分级规划的加工方法排序规则研究

结合工艺决策的分级规划策略，构造了一种新的实用化的加工方法排序规则，该排序规则将传统排序规则分解成两个相关的部分：工序排序规则与工步排序规则。工序排序规则代表了排序规则的普遍性，描述了一类零件的总体加工过程，只与加工方法有关，与组成零件的形状特征等其他因素无关；工步排序规则代表了排序规则的特殊性，描述了工序中各特征的加工顺序，与特征有关而与加工方法无关。     

对某种排序算法是“稳定的”或“不稳定的”的浅析

排序是《数据结构》这门学科所包括的一项重要内容.排序主要是针对文件而言，有些文件存在多个具有相同排序码的记录，对于这样的文件，按着不同的排序算法进行排序，会得到不同的排序结果．排序算法可以分为“稳定的”和“不稳定”的两种，应正确理解这两个概念，掌握不同的排序算法的基本思想．     

一类处理机具有准备时间的恒速机排序问题

讨论任务的加工是不可中断,处理机是恒速机且处理机具有准备时间的排序问题,目标函数是极小化最大完工时间.对于2台处理机的情况,已经有了一个与处理机加工速度有关的排序的界.研究了对于m(m≥2)台处理机的一种特殊情况,给出了一个与处理机加工速度有关的算法的界.     

时间错位限制下最小化总完工时间的继列分批重新排序

研究在时间错位限制条件下,继列分批最小化总完工时间的重新排序问题.对于最大时间错位和总时间错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的拟多项式时间算法.