我有一些来自硬件的数据。数据以 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) 中是否有更快的解决方案？
由于这些数据始终处于相同的顺序，因此根本不需要经典意义上的排序。您不需要任何比较，因为您已经提前知道两个给定数据点中的哪一个。
相反，您可以直接对数据产生排列。如果您将其转换为循环形式，这将准确地告诉您要执行哪些交换，将置换数据转换为有序数据。
这是您的数据的示例：
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 中的排列的章节。
所以你有数据以这样的模式进入
a 0 a 2 a 4 ...a 14 a 1 a 3 a 5 ...a 15
你想让它排序
b 0 b 1 b 2 ...b 15
通过一些重新排序，排列可以写成：
a 0 -> b 0
a 8 -> b 1
a 1 -> b 2
a 2 -> b 4
a 4 -> b 8
a 9 -> b 3
a 3 -> b 6
a 6 -> b 12
a 12 -> b 9
a 10 -> b 5
a 5 -> b 10
a 11 -> b 7
a 7 -> b 14
a 14 -> b 13
a 13 -> b 11
a 15 -> b 15
因此，如果您想在一个临时的仅一个块额外空间的情况下对其进行排序t，这可以在 O(1) 中完成
t = a8; a8 = a4; a4 = a2; a2 = a1; a1 = t
t = a9; a9 = a12; a12= a6; a6 = a3; a9 = t
t = a10; a10 = a5; a5 = t
t = a11; a11 = a13; a13 = a14; a14 = a7; a7 = t
编辑：
一般情况（对于 N ！= 16），如果它可以在 O(N) 中解决，实际上是一个有趣的问题。我怀疑循环总是以满足的素数开始，p < N/2 && N mod p != 0并且索引具有像 i n+1 = 2i n mod N 这样的递归，但我无法证明这一点。如果是这种情况，推导 O(N) 算法是微不足道的。
也许我误解了，但是如果订单总是与给定的订单相同，那么您可以“预先编程”（即避免所有比较）最佳解决方案（这将是交换次数最少的解决方案）从给定的字符串移到 ABCDEFGHIJKLMNOP 并且对于这么小的东西，您可以手动计算 - 请参阅 LiKao 的答案）。
我更容易用数字标记你的集合：
0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
从 14 开始，将所有偶数移动到位置（8 次交换）。你会得到这个：
0 1 2 9 4 6 13 8 3 10 7 12 11 14 15
现在您需要另外 3 次交换（9 与 3、7 与 13、11 与 13 从 7 移出）。
共11次交换。不是一般的解决方案，但它可以给你一些提示。
您还可以将预期的排列视为地址位 `abcd <-> dabc' 的洗牌（abcd 是索引的各个位），例如：
#include <stdio.h>
#define ROTATE(v,n,i) (((v)>>(i)) | (((v) & ((1u <<(i))-1)) << ((n)-(i))))
/******************************************************/
int main (int argc, char **argv)
{
unsigned i,a,b;
for (i=0; i < 16; i++) {
a = ROTATE(i,4,1);
b = ROTATE(a,4,3);
fprintf(stdout,"i=%u a=%u b=%u\n", i, a, b);
}
return 0;
}
/******************************************************/
我相信那是计数排序