任意分布数据的二次分“档”链接排序算法研究

A NEW SORTING METHOD BY TWICE GRADING AND LINKING ABOUT RANDOM DATA

本文提出一种谓之二次分“档”链接的新排序方法 (以下简称为“二次分“档”链接排序”) ,给出了该排序算法的描述、时间复杂度分析、空间复杂度分析及用 C语言编写程序进行算法比较的实验结果 .算法分析和实验结果都表明 :二次分“档”链接排序方法与待排序数据分布情况无关且时间复杂度仅为 O( N) ,而附加存储空间开销仅为 N+Δ M+2 (这里 ,N为待排序数据个数 ,△ M为关键字的变化范围 ) ,该算法不仅稳定 ,而且排序速度明显优于 Quick Sort、FlashSort〔2〕、Proportion Split Sort〔3〕、分段快速排序〔5〕等算法 .

A new sorting method about random data, the method of twice grading and linking is presented. Its algorithm description, time complexity, space complexity and experimental results in C are given. The algorithmic analysis and experimental results show that the time complexity of this method is O(N) and it has nothing to do with data distribution, additional memory cost is only N+ΔM+2.