假设我们事先知道未排序数组中的每条记录与其在已排序数组中的位置的距离最多为 d << n。我们想利用这个属性。假设所有 n 个键都是不同的。例如:令列表为 3 8 18 2 7 20 24 15 22 30 40。不难看出，对于这个未排序的列表，每条记录与其在排序数组中的位置的距离最多为 3。
设计一个运行时间为 O(n lg d) 的排序。
这是一道作业题。一些提示会很有用。
最佳答案
这是我的建议(我会发布完整的解决方案，但正如您所说，这是来自作业):
您已经知道某个元素位于正确索引的 2d 范围内。您如何能够扫描数组，但一次最多只能查看 2d 元素？
更具体地说，假设您刚刚通过检查从索引 i - d 到 i + d 的所有内容来找出第 i 个元素。您如何利用已知的知识在 O(log d) 时间内计算出第 i+1 个元素？
关于algorithm - 设计一个运行时间为 O(n lg d) 的排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17433081/