2

假设我们事先知道未排序数组中的每条记录与其在排序数组中的位置之间的距离最多为 d << n。我们想利用这个属性。假设所有 n 个键都是不同的。例如：让列表为 3 8 18 2 7 20 24 15 22 30 40。不难看出，对于这个未排序的列表，每条记录与其在已排序数组中的位置的距离最多为 3。

设计一个运行时间为 O(n lg d) 的排序。

是作业题。一些提示会很有用。

4

1 回答 1

4

这是我的建议（我会发布一个完整的解决方案，但正如你所说，这是来自作业）：

您已经知道一个元素在2d正确的索引范围内。您如何能够扫描数组，但一次只能查看大多数2d元素？

更具体地说，假设您刚刚i通过检查从 indexi - d到i + d. 你如何使用你已经知道的东西来及时找出i+1第 th 个元素O(log d)？

于 2013-07-02T18:37:29.743 回答