一种适宜于海量数据的快速分组排序算法

A Quick Group-Sort Algorithm for a Great Deal of Data

提出了一种高效的适宜于海量数据的无指针分组排序算法,分析了该算法的原理及其时间复杂度和空间复杂度.在最坏情况下的时间复杂度是θ(mn),最好情况和平均情况下的时间复杂度均是θ(nlog(n/mk));在最坏情况下的空间复杂度是O(mn-m2+m),最好情况和平均情况下的空间复杂度均是O(n)).

A pointerless group-sort algorithm is proposed for the disposal of a great deal of data, and its underlying principle and complexities of time and space are analyzed in this paper. Its time complexity is θ （mn） in the worst situation and θ（n log （n/m^k）） in the best or in average situation. Its complexity of space is O（mn-m^2＋m） in the worst situation and O（n） in the best or in average situation. In a simulation comparative experiment with multi-group random data, the group-sort algorithm was compared with the quicksort algorithm and the result showed that the conclusion in this paper is correct.