低熵多键排序问题的实用算法

Practical algorithm for low-entropy multi-key sorting

给出低熵情况下的多键排序改进算法.利用众数投票算法结合中位数选择算法产生枢纽元,对与枢纽元相等的元素使用改进算法,其他元素仍采用原算法.理论分析表明,重复数据较多时改进算法速度较快,且在数据量不大时其性能接近线性算法.

A modified multikey sorting algorithm is presented for the elements with low entropy.are combined to generate A pivot is generated by the combination of majority vote algorithm with median selection algorithm;the elements which equal to the pivot are operated with the modified algorithm,while others are operated by the original algorithm.Theoretical analysis shows that the modified algorithm runs faster when there are a lot of repeated keyword values in data,and its performance is close to linear algorithm when the scale of the data is not very large.