算法之快速排序

[front-thinking]

算法之快速排序

快排是初级算法题里最经典的一道题，不仅是因为提现了分治策略里的思想，更多的是能够快速考察出面试者是否真正懂得算法的一种手段。所以，掌握快排显得尤为重要。就我有限的面试经历里，已经被问了不止三四次快排的算法，其中不乏微信、百度等优秀的部门和岗位，虽然自己都胸有成竹，但每次面试都不尽人意。不知道其他人怎么看待，但就我个人而已，每次看快排都觉得完全掌握了，再遇到这样的面试题肯定没问题。但每次被问到这样的问题却又是事与愿违。今天，我就想再次把快排拿出来跟大家分享一下我自己对快排的理解，希望能给大家带来帮助。

小学生排队

在开始分享快排这个算法之前，我想大家一起分享个小时候的观察。我们读小学就知道，每次上体育课集合，老师一声令下，每个人都去查找自己的位置，然后站好。小学生排队的思路是什么呢，虽然看起来乱哄哄的一堆人换来换去，但有没有发现大家会很快排好队。那么我们来把这个过程放慢一些。
假设我是A，那么老师一声令下以后，我要开始查找我的位置。哪个才是我的位置呢，其实我并不关心紧紧挨着我前面和后面的人，我只要能做到我前面的人都比我矮，我后面的人都比我高，那么我就快速的找好了我的位置。然后，我前面的人也用同样的方法找到各自的位置，我后面的人也是重复这一过程。用画图的方式来看就是：

仔细看，其实会发现这就提现了快排的算法。我们对一个数组进行排序，首先选出一个人这里是A，然后遍历数组，比A小的全换到前面，比A大的换后面，然后就能把A的位置确定了。第一轮下来，A的位置就是最终排序完自己的位置。然后开始第二轮，A前面和后面的小分队都按照类似的方案来进行。最终直到全部排序完毕。

伪代码

看到这里相信你已经理解了快排的算法过程，这里有一个很重点的问题是选择A也就是选择pivot的问题。有证明随机选择pivot的情况会导致快排更优化，这里不再展开，大家可以自行搜索。下面是我们的伪代码：

function quickSort(arr, l, h) {
    pivotIndex = partition(arr, l, h);
    quickSort(arr, l, pivotIndex);
    quickSort(arr, pivotIndex, h);
   return arr;
}
function partition(arr, l, h) {
    pivot = arr[h];
    pivotIndex = l;
   for(i=l; i<h; i++) {
       if arr[i]<pivot  swap(arr[i], pivot); pivotIndex++;
   }
  swap(arr, pivtoIndex, pivot)
  return pivotIndex;
}

简单的讲就是重点分区，分区就是按照A的个头来，比A小的站前面，比A大的站后面，最后把A放在正确的位置并返回位置的坐标。

快排JavaScript的实现

有了伪代码，真正的实现就简单很多了。这里我们给出JavaScript的实现：

var quickSort = function (arr, left, right) {
  var len = arr.length, pivot, partitionIndex, left = left || 0, right = right || arr.length - 1;
  if (left < right) {
      pivot = right;
      partitionIndex = partition(arr, pivot, left, right);
      quickSort(arr, left, partitionIndex - 1);
      quickSort(arr, partitionIndex+1, right)
  }
  return arr;
};

function partition(arr, pivot, left, right){
    var pivotValue = arr[pivot],
        partitionIndex = left;

    for(var i = left; i < right; i++){
        if(arr[i] < pivotValue){
            swap(arr, i, partitionIndex);
            partitionIndex++;
        }
    }
    swap(arr, right, partitionIndex);
    return partitionIndex;
}

var swap = function (arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};

复杂度

可以看出来，这里我们采取了in-place也即是原地交换的策略，因此额外只使用了常数空间。所以空间复杂度是O(1)。
时间复杂度：平均情况下的时间复杂度是O(nlogn)，最坏的情况是O(n方).
当划分产生的两个子问题分别包含 n-1 和 0 个元素时，最坏情况发生。
当划分产生的两个子问题分别包含⌊n/2⌋⌊n/2⌋和⌈n/2⌉−1⌈n/2⌉−1个元素时，最好情况发生。
平均情况下，比如一次坏的划分接着一次好的划分，坏的划分那一项可以合并到好的划分里，统计上来讲平均情况下的时间复杂度仍然是Θ(nlgn)。
通常采用随机选择pivot的方式来避免最坏的情况放生。