论链式排序(英文)

ON A NEW SORTING ALGORITHM WHICH LOOKS LIKE CHAINS AND FORKS

本文提出一种新的排序算法,作为对排序算法的突破性尝试。与QUICKSORT排序算法相比,无论关键字值是整数、实数、字符串、单个和多个关键字值的排序,也无论关键字值的分布方式和分布范围如何,速度全面大幅度提高。在空间代价方面,从纯理论上讲,它比QUICKSORT多付出少量内存(但无论排序数量多大,它多付出的少量内存保持定值不变)。在绝大多数实际应用中,它的内存占用量少于快速排序。更理想的是,它是稳定的排序。文章给出了新算法的时间复杂性是O(N)的理论证明和关键字分别是二字节整数、四字节单精度实数、最大长度为20的字符串三个演示程序。

This paper introduces a new sorting algorithm,as an attempt for a break though in sorting algorithms. Compared with Quick-sort. Its speed overall strikingly rises ,whether type of sorting key word is integer, real or string, whether distribution and distributive scope of magnitudes of sorting key word ,too. Only on pure theory .its memory cost is a little more thanQuicksort,-the magnitude of a little more than Quicksort is always a constand, whether therecords which take part in sorting is more or less-but in mostly application,its memory costis less by far than Quicksort. In this paper ,it has been proved that the time cast of the new algorithm is O(N). Three demonstrative programs whose sorting key words are respectively integer, real or string are provided. Furthermore, the new algorithm is stable.