交换两个数据块位置（数组的连续移位）

发表于 更新于 分类于 ， 本文字数： 510 阅读时长 ≈ 1 分钟

连续的数据，如 abcdefg , 经过多次循环移位后，（如 abcdefg 经一次循环移位后变为 bcdefga ），该数据会变为什么。

我们知道数组的移位是 O (n)，很耗时间，如果连续移动 m 次的话时间消耗会很大。最近在读《编程珠玑》， 上边提供了两种算法。第一种称之为 “杂技算法”，即给定一些临时空间（设为可存放 k 个数据，需连续移动 m 次），先将前 k 个数据放入里面，之后将第 m+1 到第 m+k 个数据移入第 1 个到第 k 个中，其后依次移入其所在位置。（本文章并不想详细说此方法）。

第二种方法则比较巧妙，使我想起了暑假集训时做到的一道题目。那道题目和本题很相似，不过是要做多次这种连续移位，更加复杂。但其解决方法的思想和第二种方法思想一致。若总共有 n 个数据，要连续移动 m 次，算法如下：

  • Reserve(0, m-1)
  • Reserve(m, n-1)
  • Reserve(0, n-1)

如 abcdefg ， 第一步翻转后变为 cbadefg , 第二步后变为 cbagfed , 第三步后变为 defgabc。 即为答案，十分巧妙！

暑假那题因为需要多次进行连续移位，所以用到了 Splay 树。还有巨巨们用了 rope（块状链表）。 也是我第一次听说这种数据结构。不过 Splay 树效率更高些。