是否有一种比快速排序更快的专用算法来重新排序数据ACEGBDFH？

Question

我有一些来自硬件的数据.数据以32字节为单位,可能有数百万个块.数据块按以下方式分散在两半中(字母是一个块):

A C E G I K M O B D F H J L N P

或者如果编号

0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15

首先是所有具有偶数索引的块,然后是奇数块.是否有专门的算法来正确地重新排序数据(字母顺序)？

限制主要是空间.我不想再分配另一个缓冲区来重新排序:再多一个块.但我还想保持低移动次数:一个简单的快速排序就是O(NlogN).对于这种特殊的重新排序情况,O(N)中是否有更快的解决方案？

Answer 1

由于这些数据总是以相同的顺序排列,因此根本不需要经典意义上的排序.您不需要任何比较,因为您事先已经知道两个给定数据点中的哪一个.

相反,您可以直接在数据上生成排列.如果将其转换为循环形式,这将告诉您要进行哪些交换,将置换数据转换为有序数据.

以下是您的数据示例:

0 2 4 6 8 10 12 14 1 3  5  7  9 11 13 15
0 1 2 3 4 5  6  7  8 9 10 11 12 13 14 15

现在计算逆(我将跳过这一步,因为我在这里很懒,相反我假设上面给出的排列实际上已经是倒数了).

这是循环形式:

(0)(1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14)(15)

因此,如果你想重新排序这样结构的序列,你会这样做

# first cycle
# nothing to do

# second cycle
swap 1 8
swap 8 4
swap 4 2

# third cycle
swap 3 9
swap 9 12
swap 12 6

# so on for the other cycles

如果您已经为逆而不是原始排列做了这个,那么您将获得具有经过验证的最小交换次数的正确序列.

编辑:

有关此类内容的更多详细信息,请参阅TAOCP中的"排列"一章.