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

Question

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

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

Answer 1

我将列表(大小为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