经典快速排序实现

快速排序，简称快排。快排是所有排序算法中应用最广泛的。接下来我们将会说说一个经典的快排是如何实现的。

思路

快排的核心思想是分治。

所谓分治，就是分而治之的意思，将原来的问题拆分为多个规模较小子问题，这些子问题还能继续拆分，就是所谓套娃，直到规模小到直接求解。通过解决子问题，完成父问题，最终解决了原问题。

分治这个思想在实现上，使用的方法是递归。递归，是指函数执行中调用函数的一种形式，当递归到一定程度，就会触发退出迭代的逻辑。

分治是思想，递归是方法，不要将二者混为一谈。

具体要做的就是对数组分区（partition）。

对于提供的数组，我们随意从中找一个数组元素找出一个基准值（pivot），或者叫做中间值。然后通过分区函数（partition）将数组分为两部分，左边的小于等于 pivot 的部分，和右边的大于 pivot 的部分。

然后我们的分治（或者叫递归）就继续针对左侧和右侧进行同样的操作，直到区间大小小于等于 1。

实现

我们先看代码实现。

1. function quickSort(arr){
   
2.  partition(arr,0, arr.length -1);
   
3.  return arr;
   
4. }
   
5. 
   
6. function partition(arr, lo, hi){
   
7.  if(lo >= hi)return;// 递归跳出条件，能够直接求解的子问题
   
8.  const pivot = arr[hi];
   
9.  let i = lo;
   
10.  for(let j = lo; j < hi; j++){
    
11.    if(arr[j]<= pivot){
    
12.      swap(arr, i, j)// 交换
    
13.      i++;
    
14.    }
    
15.  }
    
16.  swap(arr, i, hi);
    
17.  partition(arr, lo, i -1);
    
18.  partition(arr, i +1, hi);
    
19. }
    
20. 
    
21. function swap(arr, i, j){
    
22.  let tmp = arr[i];
    
23.  arr[i]= arr[j];
    
24.  arr[j]= tmp;
    
25. }
    

核心算法就是这个 partition 算法。该算法实现得很巧妙，能够做到原地排序（不使用额外的数据结构）。

partition 接受一个数组，以及要进行分区的索引区间 [lo,hi]，注意这是个左闭右闭的闭区间。

这里维护了一个 i 指针和一个 j 指针。j 指针每次迭代都会加一。[lo,i) 这个区间则代表小于等于 pivot 的区间，这个区间是动态的，因为 i 会变化。

在遍历时，如果当前值小于等于 pivot，就会把这个值放到 [lo,i) 区间。实现上就是交换 i 和 j 上数组元素的位置，然后让 i 自增一。

需要特别注意的是，遍历是不能有 j == hi 的情况，并在遍历结束后将 pivot 请到中间。假设改为 j≤hi ，因为 i 对应的元素为大于等于 pivot 的元素，如果它比 pivot 大，i 和 pivot 就不会交换了。

为什么快排使用最广泛？

快排的平均时间复杂度是 O(n*logn)，比冒泡排序、插入排序这些时间复杂度为 O(n^2)的算法要好得多。具体的推导过程有点复杂，这里就不进行展开了。

归并排序的时间复杂度同样是 O(n*logn)。快排在极端情况下，时间复杂度会退化变成 O(n^2)

，而归并排序不会。在时间复杂度上确实归并排序要更好一些。

但是快排能够做到原地排序，节省内存空间，即空间复杂度为 O(1)，而归并排序的空间复杂度为 O(n)。

但快排也有个严重的缺点，因为交换元素的关系，快排是不稳定排序。排序后，相同的值可能和原来相同值的相对顺序不同，只是排序数组还好，但在对对象根据 id 排序的情况时，可能就会让我们困扰。

一些奇怪的快排实现

在网上我看到这样的实现。

1. var quickSort =function(arr){
   
2.  if(arr.length <=1){return arr;}
   
3.  var pivotIndex =Math.floor(arr.length /2);
   
4.  var pivot = arr.splice(pivotIndex,1)[0];
   
5.  var left =[];
   
6.  var right =[];
   
7.  for(var i =0; i < arr.length; i++){
   
8.    if(arr[i]< pivot){
   
9.      left.push(arr[i]);
   
10.    }else{
    
11.      right.push(arr[i]);
    
12.    }
    
13.  }
    
14.  return quickSort(left).concat([pivot], quickSort(right));
    
15. };
    

这个实现思想上是对的，也是分治和分区思想，但致命问题是，它不是原地排序，需要用到额外的数组。面试的时候最好别写这种实现，虽然看起来更简短一些。

快排思想并不复杂，但实现上用了很多变量，对初学者还是需要花时间去理解，如果不是很理解，可以多看几遍这篇文章。

我是前端西瓜哥，感谢您的阅读。