浮点数的基数排序法

在计算机数据处理中常常遇到排序,以往人们较注意比较排序算法的研究和应用,如归并排序、快速排序、堆排序、希尔排序,插入法、冒泡法等等。但已经证明比较排序法的计算量的下限为0(N 10g_2N)级,当N较大时仍然相当费时。在文献〔1〕和一些数据结构方面的书中都曾介绍过一种线性的排序方法:基数地址排序法。(地址排序法对于N很大(N≥10000)及关键字值域M有限(0～1000的整数),相当有效。但对较大的M则不能容忍,因此将它与基数法结合起来用)但一则它需要的附加内存空间大,(0 (n+m)),再则书中只介绍了关键字值为整数的情形,所以很少看到这种算法在实际中应用。