研究文章雷竞技app下载苹果版

使用哈希和位操作符提高随机签名排序的性能

摘要

在整数排序领域所做的研究已经大大提高了下限，并实现了比较排序，即确定性算法的下限为[1]，空间中仅依赖于输入整数的数量的基数排序算法的下限为[1]。Andersson et al.[2]在预期的线性时间和空间中提出了签名排序，其性能比传统的快速排序差得多。众所周知，在[1,c]范围内的整数可以使用基数排序及时排序。可以对任意范围[1，]内的整数按时间[1]排序。然而，这些算法使用额外的内存。我们提出了一种简单而稳定的整数排序签名排序的变体，它在时间上工作，并且只使用额外的内存。在这方面，我们试图通过不同的实现来提高签名排序的性能，并将其与传统排序算法的性能进行比较，并查看寄存器大小对算法的影响。

塔玛娜·帕塔克和迪帕克·加格博士

阅读全文下载全文