Simona&Peter

从快排递归说起

Zhang Xiao -

快排最简洁的是递归写法，可是当我问自己你真的想明白到底发生了什么吗？如果你有些不能肯定，那么我们一起来看看到底发生了什么。

其实快排的原理用语言描述起来挺容易的，简单说就是在数组中找一个值作为对比值(常常找中间那个元素)，然后把数组中小于此值的值放入一个数组，把大于此值得放入另一个数组。然后针对这两个数组重复递归上面的过程，把所有的值连接起来就是最后的结果了。

让我们来写写代码：

var qsort = function(arr) {
if(arr.length <= 1) {
   return arr;
}
var pivot = arr.splice(Math.floor(arr.length/2), 1)[0],
left = [],
right =[];

for(var i=0; i<arr.length; i++) {
  if(arr[i] < pivot) {
    left.push(arr[i]);
  } else if(arr[i] > pivot) {
    right.push(arr[i]);
  }
}

return qsort(left).concat([pivot], qsort(right));
}

这是网上很多写法中的一种，需要注意的点是递归写法必须有递归结束的条件，不然就会无限递归会死机的。。。这里的递归结束点是：

arr.length <= 1

也就是说当数组元素里只有一个元素或者没有元素的时候就不用再排序了，此时返回数组本身，为什么是返回数组本身呢？这里有两点原因，一是我们最后的结果是三个数组concat的结果，所以需要返回数组类型的值，二是此时的数组就是我们要的数组结果。然后呢？完了么？可能有些同学觉得这么简单还用说，是啊，我就是属于笨的那种需要细细消化下。。。所以还有兴趣的可以接着看，到底发生了什么？递归啊！可是递归你真的想明白了么，让我们脑演一遍计算机计算的过程吧~

在chrome中，我们可以输入monitor(qsort), 然后执行qsort([5,1,4,3,8,2,6]);会看到如下的函数调用过程：

function qsort called with arguments: 5,1,4,3,8,2,6
function qsort called with arguments: 1,2
function qsort called with arguments: 1
function qsort called with arguments: 
function qsort called with arguments: 5,4,8,6
function qsort called with arguments: 5,4,6
function qsort called with arguments: 
function qsort called with arguments: 5,6
function qsort called with arguments: 5
function qsort called with arguments: 
function qsort called with arguments:

翻译成图就是：

剩下的就是感受一下计算机是怎么思考的吧~

然后我又自己试着用这种方式写了二分查找的递归算法，如下：

var bs = function(arr, target) {
  
  var midIndex = Math.floor(arr.length / 2);
  
  if(arr.length === 0) {
    return false;
  }
  
  if(arr.length === 1 && arr[0] === target) {
     return true;
  }
  
  if(target < arr[midIndex]) {
     
    return bs(arr.slice(0, midIndex), target);
  
  } else if(target > arr[midIndex]) {
    
     return bs(arr.slice(midIndex + 1, arr.length), target);
  } else { 
     
    return true;
  }

};

这个算法就是要注意边界情况的测试，方法会返回是否存在此元素，发现并没有实现返回元素的位置信息的东西。。。然后就去网上看别人写的，有这样一种算法，巧妙的保留了index的信息，而不是像我上面写的那样，每次递归参数都是新数组导致保留原有位置信息很困难，代码如下，可以体会一下为什么，其实我觉得最关键的一步就是：

 var midIndex = Math.floor((sindex+eindex)/2);

而不是每次针对新的数组:

var midIndex = Math.floor(arr.length / 2);

进而保留了元素组的index到midIndex中。

var bs2 = function(arr, target, sindex, eindex) {
  
  if(eindex < sindex) {
     return -1;
  }
  
  var midIndex = Math.floor((sindex+eindex)/2);
  
  if(target < arr[midIndex]) {
      eindex = midIndex - 1;
      return bs2(arr, target, sindex, eindex);
  } else if(target > arr[midIndex]) {
      sindex = midIndex + 1;
      return bs2(arr, target, sindex, eindex);
  } else {
      return midIndex;
  }
  
}

它的非递归是变成循环，逐次衰减循环次数来达到目的的，注意条件语句中的顺序，最后不要忘记了都不符合的条件下是返回-1的，如下：

var bs3 = function(arr, target) {
    var sindex = 0,
        eindex = arr.length - 1,
        midIndex = 0;
  
  while(sindex <= eindex) {
  
    midIndex = Math.floor((sindex + eindex)/2);
    if(target < arr[midIndex]) {
        eindex = midIndex - 1;
    } else if(target > arr[midIndex]) {
        sindex = midIndex + 1;
    } else if(target == arr[midIndex]) {
        return midIndex;
    } else {
        return -1;
    }
  }
}

我常常觉得递归这种东西很难理解，因为我觉得递归就好像一个无穷的黑洞一样，你无法一眼看穿它有多深，但他又能以近乎直白的语言表示给计算机使用。好吧，什么是递归，可能我还不能完全把它理解的很好，暂时的理解就是：

递归是一层一层的洋合葱，你需要从最外层一层一层的剥去它的外衣，然后在最后一层拿到藏在里面的答案，然后拿着答案再从里到外在每一层加工完答案再合起来外衣，最后把最终的答案从洋葱里拿出来的过程。当然你可能同时或者在某个时刻操作的可能不是一个洋葱，也许是多个啊。本来想更感性的认识一下递归，可是呢，发现还是没说明白，哈哈哈，慢慢来吧~