快速排序的3个基本步骤：

  1. 从数组中选择一个元素作为基准点；
  2. 所有比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去；
  3. 最后利用递归，将摆放在左边的数组和右边的数组在重复上述的1和2操作。

image.png
我们根据上面这张图，来用文字描述一下

  1. 选择右边的元素为7为基准数；
  2. 将小于7的放在左边，大于7的放在右边，然后将基准数放到中间；
  3. 然后再重复操作从左边的数组选择一个基准点2；
  4. 3比2大则放到基准树的右边；
  5. 右边的数组也是一样选择12作为基准数，15比12大所以放到了12的右边；
  6. 最后出来的结果就是从左到右 2 ，3，7，12，15了；

以上就是快速排序基本的一个实现思想。

实现

  1. function quickSort(arr=[2,5,2,1,6,3,9]) {
  2.     if (arr.length <= 1) return arr;
  3.     let pivotIndex = Math.floor(arr.length / 2); //得到中位数索引
  4.     let pivot = arr.splice(pivotIndex, 1)[0]; //把中位数从数组中删除，并且拿到删除的值
  5.     // console.log(pivot,arr) //1 [ 2, 5, 2, 6, 3, 9 ]
  6.     let left = [];  //存放比基准值小的
  7.     let right= [];  //存放比基准值大的
  9.     for (let i = 0; i < arr.length; i++) {
  10.         (arr[i]<centerValue?left:right).push(arr[i])
  11.     }
  12.     return [...quickSort(left),centerValue,...quickSort(right)];
  13. }
  15. console.log(quickSort())

以上代码的实现方式是，选择一个中间的数字为基准点，用两个数组分别去保存比基准数小的值，和比基准数大的值，最后递归左边的数组和右边的数组，用concat去做一个数组的合并。
对于这段代码的分析：
缺点：

  • 获取基准点使用了一个splice操作，在js中splice会对数组进行一次拷贝的操作，而它最坏的情况下复杂度为O(n)，而O(n)代表着针对数组规模的大小进行了一次循环操作。
  • 首先我们每次执行都会使用到两个数组空间，产生空间复杂度。
  • concat操作会对数组进行一次拷贝，而它的复杂度也会是O(n)
  • 对大量数据的排序来说相对会比较慢

优点：