performance - 是否有比快速排序更快的专门算法来重新排序数据 ACEGBDFH？

Question

我有一些来自硬件的数据。数据以 32 字节的 block 形式出现，并且可能有数百万个 block 。数据 block 按如下方式分散成两半(一个字母为一个 block ):

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

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

限制主要在空间上。我不想分配另一个缓冲区来重新排序:再分配一个 block 。但我也想保持较低的移动次数:一个简单的快速排序是 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 中有关排列的章节。