分段快速排序法

本文给出分段快速排序方法,对于给定的N个数据记录,此方法的最大平均排序时间为O(N)。本文最后给出利用三种快速排序方法在IBM—PC机上分别关于均匀分布数据记录和正态分布数据记录进行排序的实验结果。     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

用归并法改进快速排序

针对快速排序法在最坏情形下算法效率较低的弊端,提出了一种改进算法,即利用归并法对快速排序进行改造,使其在最坏情况下的性能有了显著的提高。     

分段快速排序法的改进

针对分段快速排序法^[1]因分段映射策略不理想而造成算法复杂度显著增加之问题,本文提出了一种由按位块分段、分段映射和局部快速排序所组成的新排序算法－按位块分段快速排序法（以下简称为“按位块分段快速排序”）。算法分析和实验结果都表明：在待排序数据均匀分布或正态分布的情况下,按位块分段快速排序法的时间复杂度可以达到O(N),是附加存储空间开销却仅仅为N＋M（M为分段数目,1≤M≤N）,同时排序速度明显优于QuickSort^[2]、分段快速排序^[1]、分“档”统计插入排序^[5]和Proportion Split Sort^[7]等算法。     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

基于距离排序的快速支持向量机分类算法

传统支持向量机算法由于时空复杂度较高,因此很难有效地处理大规模数据。为了降低支持向量机算法的时空复杂度,提出一种基于距离排序的快速支持向量机分类算法。该算法首先计算两类样本点的样本中心,然后对每一个样本计算它与另一类样本中心之间的距离,最后根据距离排序选择一定比例的小距离样本作为边界样本。由于边界样本集合很好地包含了支持向量,而且数目较原始样本集合少得多,因此算法可以在保证支持向量机学习精度的前提下,有效地缩短训练时间和节约存储空间。在UCI标准数据集和20-Newsgroups文本分类数据集上的实验说明算法较以往支持向量预选取算法而言可以更为快速准确地进行支持向量预选取。     

快速分组排序

§1.排序 对一组给定的数据记录 x_1,x_2,…,x_i,…,x_N (1)排序,就是在计算机上经过一定的计算处理,把数据记录(1)排成递增或递降的数序列。如排成递增的数序列     

“分级快速排序法研究”的研究

本文深入研究和分析分级排序方法，修正其缺陷并给出改进的容易在机器上实现的方法     

简单快速排序算法

内部排序是计算机程序设计中的一种重要操作,排序算法也很多,每一种方法都有各自的优缺点,适合在不同的环境下使用。在这里我们先比较一些常用的排序算法,再提出一种针对排序数连续性较好的简单和较快的排序算法。     

快速排序性能分析

在决策树计算模型下,任何一个基于比较来确定元素相对位置的排序算法需要的计算时间是Ω(nlog2n).如果能设计一个需要O(nlog2n)时间的排序算法,在渐近的意义上,这个排序算法就是最优的.由C.A.R.Hoare发明的快速排序算法它在平均情况下需要O(nlog2n)时间.本文就该算法在最好情况下、最坏情况下、平均情况下的性能进行分析.     

超快速排序算法

快速排序算法结构简单,平均性能较佳;基数排序性能较稳定。结合快速排序和基数排序,提出超快速排序算法,通过理论分析和实验表明,新算法的性能优于快速排序算法和基数排序算法。     

多队列快速排序

快速排序算法的平均时间小于所有已知的O(nlogn)排序算法。它的平均时间是O(nlogn),最坏情况为O(n~2)本文提出的算法对n个元素的排序时间为O(nlogm),其中其最佳性能为O(n)在M 16计算机上运行的结果符合文中给出的算法分析     

快速排序的应用

有一些基础的同学,一定学过一些排序的算法,如冒泡 法、插入法。这些算法很容易掌握,用它们排序通常需要两 重循环,对于n个数据,算法的时间复杂度为0(n2),效率 是比较低的。当n达到几万甚至十几万时,程序会运行得相 当缓慢。 下面介绍一种效率较高的算法。排序的过程是:取出待 排序数据之一(称为基准数据),并将数据分为两部分,使 得基准数据一侧的数据皆小于基准数据,另一侧的数据皆大于 基准数据,如果某一侧的数据至少有2个,则对这一侧的数 据递归地进行同样操作。 问题的难点在于,如何完成“将数据分为两部分”这 一步。我们以下面的数据为例(需要对其进行升序排列), 介绍一种较好的方法:     

超快速排序算法

快速排序将文件分成两个子文件，然后递归地将两个子文件排序，其平均复杂性为Ｏ。本文给出超快速排序算法，建立将文件分成Ｎ个子文件，然后递归地将Ｎ个子文件排序，其平衡复杂性为Ｏ（Ｎ）。     

一种基于选择排序的快速求核算法

关于求核的算法有很多,本研究利用选择排序的思想设计了求解等价类的算法,其时间复杂度为O（｜C｜｜U｜）。在此基础上,设计的求核算法,算法时间复杂度为O（｜C｜^（2）｜U｜）。通过实验,证明了算法的正确性和高效性。