基于极值索引的数据排序算法

Data Sorting Algorithm Based on Extremum Index

提出一种新的数据排序算法,将数学极值的求解原理与数据排序结合,把极小值的概念扩展到记录的序列中,并按数据的排列规律,建立了极小记录索引,通过索引快速搜索待排序列中的记录,对待排序列快速的排序。该算法的最大时间复杂度T(n)为O(nlogn)和空间复杂度O(n),在提高排序效率的同时,保证了排序结果中的相同大小记录之间相对位置的稳定。

This thesis proposes and discusses a new internal sorting algorithm, which combines mathematics extremum principle with data sorting algorithm. The algorithm expands the concept of minimum, establishes minimum extremum record index and can search very fast record from sequences through indexes of extremum record. As compared with the traditional internal sorting algorithms, the time complexity T(n) of the algorithm is O(n log n) at the most and it抯 space complexity is O(n). The algorithm guarantees the stability of data sorting while improves the efficiency of sorting.