字符串反转算法

最近在翻阅《编程珠玑》第二版，真的是字字珠玑。在看到第二章的“啊哈，算法”的一道题目，将字符串反转。将一个具有n个元素的一维向量x向左旋转i个位置。例如，将 abcdefg 向左旋转 3 个位置之后得到 defgabc。要求是花费与n成比例的时间以及尽可能少的空间来完成这个操作。看到此题后的第一想法就是临时数组，下面来看下具体代码：

临时数组法

使用js原生splice与concat方法，可减少大量代码：

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap1 (arr, x) { 
    return arr.splice(x).concat(arr);
}
console.log(swap1(arr, 4));

不用javascript原生的方法：

var arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap2(arr, x) {
    var temp = [],
    len = arr.length;
    for (var i = 0; i < x; i++) {
        temp[i] = arr[i];
    }
    for (var i = x; i < len; i++) {
        arr[i - x] = arr[i];
    }
    for (var i = 0; i < x; i++) {
        arr[len - x + i] = temp[i];
    }
    return arr;
}
console.log(swap2(arr2, 4));

这种方法大多数人都能够想得到，这是最普通的方法，但比较浪费空间。接下来在看一个也比较普通的方法，不使用临时数组。

元素移位

var arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap3(arr, x) {
    var temp,
    len = arr.length;
    for (var i = 0; i < x; i++) {
        temp = arr[0];
        for (var j = 0; j < len - 1; j++) {
            arr[j] = arr[j + 1];
        }
        arr[j] = temp;
    }
    return arr;
}
console.log(swap3(arr3, 4));

程序的实现原理也很简单，将第一位元素往后移动，而其他元素向前移动。虽然不浪费空间，但如果x比较大的话，花费的时间成本就比较高了。

机智的反转

下面来看作者给出的一个比较机智的方法，真的是灵光一闪的感觉。原问题可以理解为这样：将原数组看成 ab，需要转换成 ba，先单独对子数组a进行反转得到a’b（a’表示a反转后的结果），同理单独反转b，得到 a’b’，最后将得到的 a’b’ 一起进行一次反转可得 （a’b’）’，而这就是最终结果 ba了。还有一个很形象的图来说明：

你可以用自己的双手照着图反转着试一下，看看结果是不是正确的。下面给出这种反转的代码：

// 反转函数 1234 => 4321
function reverse(arr, start, end) {
    var temp,
        len = arr.length, 
        mid = Math.floor((start + end) / 2);
    for (var i = start; i < mid; i++) {
        temp = arr[end - i - 1 + start];
        arr[end - i - 1 + start] = arr[i];
        arr[i] = temp;
    }
};
function swap4(arr, x) {
    reverse(arr, 0, x);
    reverse(arr, x, arr.length);
    reverse(arr, 0, arr.length);
    return arr;
}

性能对比

jsper的测试结果：http://jsperf.com/reversea

从上面的数据看来单位时间内，swap4的性能最好了（果然机智），用js原生的方法则最差，比最快的慢了80%多。swap2在执行上也很快，但多用了一块空间来存放待偏移的temp字符，以空间换时间。swap3性能一般，比较依赖于x的位置，x的位置越靠后，需要花费的时间会越长。

还有一种巧妙的方法

巧妙的杂技表演

先将x[0]移到临时变量t中，再把x[i]移到x[0]腾出来的位置中，x[2i]移到x[i]中，以此类推（每一次移动时将x[]中的下标对其长度n取模），直到又回到从x[0]提取元素，此时应该把临时变量t放入到上一个位置中，并开始下一次迭代，即对x1进行类似的操作。找来书中直观的图如下：

代码如下：

function reverse(arr, m){
   var k = 0; 
   for(var i = 0; i < m; i++){ 
      k = 1;  //每次迭代都从1倍位移开始 
      var temp = arr[i]; 
      while(( k * m + i) % arr.length !== i){ 
          arr[( k - 1 ) * m + i] = arr[k * m + i]; 
          k++; 
      } 
      arr[(k - 1) * m + i] = temp; 
   } 
} 

但这种方法有限制性，如果数组的长度不能整除m，则无法正常的运行。

个人知乎，欢迎关注：https://www.zhihu.com/people/iamaddy

欢迎关注公众号【入门游戏开发】