我有一些数据从硬件到来。数据来自以32字节的块，并且有可能有数百万块。数据块分布在两半以下的方式（一个字母一个块）：

I have some data coming from the hardware. Data comes in blocks of 32 bytes, and there are potentially millions of blocks. Data blocks are scattered in two halves the following way (a letter is one 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

首先与连索引，然后奇数块的块。是否有一个专门的算法来正确地重新排序的数据（按字母顺序排列）？

First all blocks with even indexes, then the odd blocks. Is there a specialized algorithm to reorder the data correctly (alphabetical order)?

的约束是主要的空间。我不想分配一个缓冲区来重新排序：只有一个多块。但我也想保持的移动次数低：一个简单的快速排序是O（NlogN）。是否有O（N）为这个特殊的重新排序情况下，更快的解决方案？

The constraints are mainly on space. I don't want to allocate another buffer to reorder: just one more block. But I'd also like to keep the number of moves low: a simple quicksort would be O(NlogN). Is there a faster solution in O(N) for this special reordering case?

推荐答案

由于该数据总是以相同的顺序，在传统意义上是没有必要的排序。你不需要任何的比较，因为你已经提前知道其中两个给定的数据点。

Since this data is always in the same order, sorting in the classical sense is not needed at all. You do not need any comparisons, since you already know in advance which of two given data points.

相反，你可以直接产生对数据的排列。如果你将其转化成环状的形式，这将告诉你到底是哪交换做，对置换后的数据转换为有序数据。

Instead you can produce the permutation on the data directly. If you transform this into cyclic form, this will tell you exactly which swaps to do, to transform the permuted data into ordered data.

下面是为您的数据为例：

Here is an example for your data:

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

现在计算逆（我会跳过这一步，因为我懒在这里，假设而不是上面其实我已经给了置换是逆的话）。

Now calculate the inverse (I'll skip this step, because I am lazy here, assume instead the permutation I have given above actually is the inverse already).

下面是循环形式：

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

所以，如果你想重新排序的序列结构这样，你会怎么做

So if you want to reorder a sequence structured like this, you would do

# 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

如果你会的倒数代替原有的置换做到了这一点，你会得到正确的序列互换的证明最小数量。

If you would have done this for the inverse instead of the original permutation, you would get the correct sequence with a proven minimal number of swaps.

修改

有关这样的事情的详细信息，请参阅TAOCP例如在置换的章节。

For more details on something like this, see the chapter on Permutations in TAOCP for example.