分段快速排序法的改进

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

ASS算法分析与改进

本文提出了一种新的排序方法－－数轴分段排序算法，此方法彻底抛弃了传统排序算法对数据反复比较和交换两种操作，以数据值同空间的对应关系完成其排序过程。其排序运算量为Ｏ，达到了排序运算量的下限。     

一种新的分"档"统计插入排序算法

提出了一种谓之数据代码转换,分“档”统计,迁移插入的新排序方法,给出了该排序算法的描述,时间复杂度分析用Ｃ语言编写程序进行算法比较的实验结果,算法分析和实验结果都表明：在待排序数据均匀分布的情况下,分“档”统计插入排序方法的时间复杂度为Ｏ（Ｎ）,并且排序速度明显优于快速排序,分段快速排序,按位段分块排序等算法。     

实型数据的非比较分段排序算法

实型数据非比较分段排序算法(简称RNCSS)是根据实型数据机内编码的特点提出来的一种快速非比较排序算法,文中给出了算法的分析和关键的源程序段。该算法的时间复杂度为0(N),且附加存储空间极小,特别适合干数据量大的场合。     

分组散列排序算法

以比较为基础的快速排序（ｑｕｉｃｋｓｏｒｔ）算法，其复杂性为Ｏ（ＮｌｏｇＮ）。本文结合概率论知识，提出分组散列查找算法，给出算法描述，其算法复杂性为Ｏ（Ｎ），从而优于快速排序算法。最后给出实验结果和ＢＡＳＩＣ程序。     

基于数据分布特性的快速排序

文中提出了一种基于数据分析特性的快速排序算法，根据被排数据的分布行性，选择数据比较次数和数据移动次数较少的排序算法，当被排数据存在ｍ个有序序列时，其算法的时间复杂度为Ｏ（ｎｌｏｇ２ｍ）其中ｍ∈（１，ｃｆ√ｎ），ｃ为某一常数，其最佳性能为Ｏ（ｎ）。当ｍ≥ｃ（√ｎ）时，保持快速排序的最佳平均性能，使排序运行于较优状态下。     

二次分级连接排序算法

近年来，人们提出了不少排序运算量为Ｏ（Ｎ）的新算法。但对这些算法分析研究的结果表明，普遍存在着以下两点不足：（１）附加空间开销大；（２）排序效率过分依赖于键值的均匀分布。对此，本文提出了一个排序算法－二次分级连接排序法。该方法保证排序时间在最坏下为Ｏ（Ｎ）的基础上，仅需附加空间开销Ｎ＋√△Ｍ＋２。这里，△Ｍ为键值的变化范围。     

一种新的映射链接排序算法

本文通过对长记录数据特性的分析,提出了一种谓之映射链接的新排序方法（以下简称为“晌射链接排序”）,给出了该排序算法的描述、时间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果。算法分析和实验结果都表明：映射连接排序方法与待排序数据分布情况无关,其时间复杂度仅为Ｏ（Ｎ）;对于大规模长记录数据的排序,其速度远远优于快速排序、快速分组排序、Ｐｒｏｐｏｒｔｉｏｎ Ｓｐｌｉｔ Ｓｏｒｔ等算法。     

关于排列集p（n,r）的几种有效算法

本文在按字典排序的前提下，给出了生成排列集ｐ（ｎ，ｒ）的枚举算法，为建立ｐ（ｎ，ｒ）与它的反相集合的映射及逆映射，提供了一对编解码算法；在此编解码算法的基础上，为建立ｐ（ｎ，ｒ）与ｚ＝｛１，２，…，│ｐ（ｎ，ｒ）│｝之间的一一映射关系，还给出了相应的排序和逆排序算法。实际上，我们给出的这些算法，与已知的算法相比，更具有普遍性和优越性。     

整数排序—一种新的图排序算法及应用

提出一种新的图排序算法，它将一些较难实现的图排以简化为整数排序，不仅提高了问题解的精度度，而且便于编程，该算法的时间复杂率为０（ｍ＾２），文中还介绍了该算法的一些应用。     

Sorting on STAR

This paper gives timing comparisons for three sorting algorithms written for the CDC STAR computer. One algorithm is Hoare's Quicksort, which is the fastest or nearly the fastest sorting algorithm for most computers. A second algorithm is a vector version of Quicksort that takes advantage of the STAR's vector operations. The third algorithm is an adaptation of Batcher's sorting algorithm, which makes especially good use of vector operations but has a complexity of N (log N)2 as compared to a complexity of N log N for the Quicksort algorithms. In spite of its worse complexity, Batcher's sorting algorithm is competitive with the serial version of Quicksort for vectors up to the largest that can be treated by STAR. Vector Quicksort outperforms the other two algorithms and is generally preferred. These results indicate that unusual instruction sets can introduce biases in program execution time that counter results predicted by worst-case asymptotic complexity analysis.     

应用于大数据的Trie树排序算法

针对在数据量动态增加的场景下现有的排序算法管理数据导致算法性能大大降低的问题,提出一种16-bit Trie树排序算法.借助邻居节点上存储的链节点指针完成排序,它不仅可以边构建边排序,且引入动态数组可以提高该算法的空间效率.仿真结果表明,传统Trie树支持数据动态更新,但通过遍历Trie树的方式完成排序耗时较多,快速排...     

Exploiting partial order with Quicksort

The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A simple change can be made to the Quicksort strategy to give a bestcase performance of n, for ordered data, with a smooth transition to O(n log n) for random data. This algorithm (Transort) matches the performance of Sedgewick's claimed best implementation of Quicksort for random data.     

A stable quicksort

A sorting algorithm, called Stable Quicksort, is presented. the algorithm is comparable in speed with the Quicksort algorithm, but is stable. The experimental evidence presented support the theoretical evaluation of the performance of Stable Quicksort.     

Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case time complexity when compared with classical insertion sort (IS). By comparing our new proposed algorithm with the Quicksort algorithm, BCIS indicated faster average case time for relatively small size arrays up to 1500 elements. Furthermore, BCIS was observed to be faster than Quicksort within high rate of duplicated elements even for large size array.     

A new external sorting algorithm with no additional disk space

This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster.     

归并方式的多线程快速排序算法

本文基于Java平台针对经典快速排序提出改进方案,使用归并的思想对快速排序作了多线程优化,并对单、多线程下的快速排序进行了对比测试和分析。结果表明,通过多线程优化,快速排序在双核主机上对5千万个随机整型数据进行排序的速度是单线程的1.6倍,说明了该优化方法的有效性。该方法思路直观、容易理解,宜作为多核技术教学案例。     

A parallel version of cook and Kim's algorithm for presorted lists

The Cook and Kim algorithm is a well known method for sorting presorted lists. This paper presents observations based on an implementation of the algorithm on a single processor. An extension of the algorithm to a tightly coupled multiprocessor will also be presented. The performance of the parallel version of the algorithm on presorted lists will be compared to that of a heavily used parallel sort algorithm for tightly coupled multiprocessors, Parallel Quicksort.     

The analysis of Quicksort programs

Summary The Quicksort sorting algorithm and its best variants are presented and analyzed. Results are derived which make it possible to obtain exact formulas describing the total expected running time of particular implementations on real computers of Quicksort and an improvement called the median-of-three modification. Detailed analysis of the effect of an implementation technique called loop unwrapping is presented. The paper is intended not only to present results of direct practical utility, but also to illustrate the intriguing mathematics which arises in the complete analysis of this important algorithm.This work was supported in part by the Fannie and John Hertz Foundation, and in part by the National Science Foundation Grants No. GJ-28074 and MC S75-23738     

Splaysort: Fast,Versatile, Practical

Adaptivity in sorting algorithms is sometimes gained at the expense of practicality. We give experimental results showing that Splaysort — sorting by repeated insertion into a Splay tree — is a surprisingly efficient method for in-memory sorting. Splaysort appears to be adaptive with respect to all accepted measures of presortedness, and it outperforms Quicksort for sequences with modest amounts of existing order. Although Splaysort has a linear space overhead, there are many applications for which this is reasonable. In these situations Splaysort is an attractive alternative to traditional comparison-based sorting algorithms such as Heapsort, Mergesort, and Quicksort.