基于特定范围的关键字的快速排序算法

Fast Sorting Algorithm Based on Keywords in a Given Scope

本文给出了一种对关键字在特定范围内的数据记录不用进行数据的比较交换的快速排序算法、算法思想、算法描述、时间复杂度及空间复杂度分析,并用C++语言编写程序进行算法比较。结果表明:在关键字范围远远小于记录数的情况下,此算法的时间复杂度仅为O(n),并且明显优于其他排序算法。

The paper proposes a new fast sorting method for the records whose keywords limit in a specific scope, and the method does not require comparing and exchanging data. Then it gives the new method＇s algorithm thought, algorithm description and time/space complexity analysis, simultaneously algorithm comparison is made in C＋＋ programming. T- he results shows that, when the scope of keywords is much smaller than the number of records, the method＇s time complexity is O（n）, so it is better than other sorting algorithms.