旋转算法演示

Question

在许多地方，我看到 [begin, end) 范围内的数组旋转 "middle point" m 实现为：

void rotate(begin, m, end)
    reverse(begin, end);
    reverse(begin, m);
    reverse(m, end)

其中反向函数等同于 std::reverse，这很好用。标准库算法std::rotate更进一步，只用forward_iterators进行旋转（反向需要bidirectional_iterators）。

你知道我在哪里可以找到旋转算法的正式演示，或者如果有适合 SO 答案的简单演示，你能在这里给我解释一下吗？

Answer 1

我会尝试提供视觉证据。

考虑这样一个字符串：

begin----->m--->end

应用reverse(begin, end)将导致：

begin<---m<-----end

应用reverse(begin, m)将导致：

begin--->m<-----end

最后 reverse(m, end) 将导致：

begin--->m----->end

从而旋转字符串。

Answer 2

想想那个轴点m:

begin----->m-1,m,m+1----->end-1

在 reverse(begin, end) 之后：

end-1----->m+1,m,m-1----->begin

在 reverse(begin, m) 之后：

m+1----->end-1,m,m-1----->begin

在 reverse(m, end) 之后：

m+1----->end-1,begin----->m-1,m

因此将 begin...m 旋转到最后几位，并将 m+1...end-1 旋转到第一位。

Answer 3

我在 youtube 上找到了一个很好的视频。轮换的解释比在编程基础中更好，像我这样的笨蛋就是不明白。

Demonstration for rotation algorithms