转载

快速排序递归

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

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

让我们来写写代码：

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:

翻译成图就是：快速排序递归