1

给定一个包含整数的数组，每个整数距其最终位置最多 n 个位置，最好的排序算法是什么？

我一直在思考这个问题，我似乎无法找到一个好的策略来开始处理这个问题。有人可以指导我吗？

4

4 回答 4

7

我将列表（大小为 N）拆分为 2n 个子列表（使用从零开始的索引）：

列表 0：元素 0、2n、4n、...
列表 1：元素 1、2n+1、4n+1、...
...
列表 2n-1：元素 2n-1、4n-1、...

这些列表中的每一个显然都是排序的。

现在合并这些列表（一次重复合并 2 个列表，或者使用一个最小堆和每个列表中的一个元素）。

就这样。时间复杂度为 O(N log(n))。

这在 Python 中很容易：

>>> a = [1, 0, 5, 4, 3, 2, 6, 8, 9, 7, 12, 13, 10, 11]
>>> n = max(abs(i - x) for i, x in enumerate(a))
>>> n
3
>>> print(*heapq.merge(*(a[i::2 * n] for i in range(2 * n))))
0 1 2 3 4 5 6 7 8 9 10 11 12 13
于 2012-04-05T23:52:58.720 回答
1

对于最初的随机数组/元素集合，堆排序非常快。在伪代码中，这种排序将按如下方式实现：

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

对于不同的情况，例如“少数独特”的“几乎排序”，算法可以以不同的方式工作并且更有效。有关各种情况下带有动画的算法的完整列表，请参见这个精彩的网站。

我希望这有帮助。

附言。对于几乎排序的集合（如上所述），插入排序是您的赢家。

于 2012-04-05T19:10:44.930 回答
0

我建议使用梳子排序，只需以等于最大距离（或大约在那里）的间隙大小开始它。预计为 O(n log n)（或者在您的情况下为 O(n log d)，其中 d 是最大位移），易于理解，易于实现，并且即使元素的位移超出您的预期，也可以工作。如果您需要有保证的执行时间，您可以使用堆排序之类的东西，但过去我发现空间或计算时间的开销通常不值得，最终几乎实现了其他任何东西。

于 2012-04-05T19:28:49.783 回答
0

自each integer being at most n positions away from its final position：

1) 对于最小整数（也就是最终排序数组中的第 0 个整数），它的当前位置必须在 A[0...n] 中，因为第 n 个元素距离第 0 个位置有 n 个位置

2) 对于第二小的整数（也就是最终排序数组中的第一个整数，从零开始），它的当前位置必须在 A[0...n+1]

3) 对于第 i 个最小的整数，它的当前位置必须在 A[in...i+n]

我们可以使用一个 (n+1) 大小的最小堆，其中包含一个滚动窗口来对数组进行排序。您可以在此处找到更多详细信息：

http://www.geeksforgeeks.org/nearly-sorted-algorithm/

于 2013-07-23T13:24:10.427 回答