排序算法整数最多有n个点的整数

Question

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

我一直在想这个问题，我似乎无法得到一个好的策略来开始处理这个问题。有人能指导我吗？

Answer 1

我分成2n个子列表的列表（大小为N）（使用基于零的索引）：

列表0：0的元素，2N，4N，...
列表1：元素1 ，2N + 1，N + 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 

Answer 2

Heap Sort对于最初的随机数组/元素集合非常快。

# 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) 

对于不同的情况下，像“近排序”“一些独特”的算法可以不同的方式工作是比较有效：在伪代码如下这种将imlemented。有关各种情况下带动画的算法的完整列表，请参阅this brilliant site。

我希望这会有所帮助。

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

Answer 3

我推荐使用comb sort，只需以等于最大距离（或在那里）以上的间隙大小开始。期望O（n log n）（或者在你的情况下，O（n log d），其中d是最大位移），易于理解，易于实现，并且即使在元素移位超过预期时也能工作。如果你需要有保证的执行时间，你可以使用像堆排序这样的东西，但是在过去，我发现空间或计算时间的开销通常不值得，并最终实现其他任何事情。

Answer 4

由于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 [i-n ...i + n]

我们可以使用一个（n + 1）大小最小的堆，它包含一个滚动窗口来获取数组。你可以在这里找到更多的细节：

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