## 前言 本文主要讲述快速排序的一些基本概念和代码的部分。 ## 概念理解 快排是比较常见的排序方法，其基本逻辑是分为以下的几个阶段。 > 1）在数据集之中，选择一个元素作为"基准"（pivot）。 2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。 3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 ## 基本的代码逻辑 ~~~ let quickSort = (arr) => { let len = arr.length if(len <= 1) { return arr } let middleIndex = Math.floor(len/2) let middle = arr.splice(middleIndex,1) let left = [] let right = [] for(let i = 0 ; i < len-1 ; i++){ if(arr[i]-middle<=0){ left.push(arr[i]) } else { right.push(arr[i]) } } return quickSort(left).concat([middle],quickSort(right)) } ~~~ - [codepen快排的案例](https://codepen.io/robinson90/pen/QVjaMB) ## 复杂度 最坏情况：需要进行n‐1 次递归调用，其空间复杂度为 O（n） 最好情况：需要logn次递归调用，其空间复杂度为O（logn）  ## 稳定性 快速排序是一种不稳定排序算法 例如：现有序列为[1, 0, 1, 3]，“基准”数字选择为第二个1 在第一轮比较之后，变成了[0, 1, 1, 3]，左序列为[0]，右序列为[1, 3]（右序列的1是此前的第一个1） 不难发现，原序列的两个1的先后顺序被破坏了，改变了先后顺序，自然就是“不稳定”的排序算法了 ## 快排进阶 ## 参考文档 - [快速排序（阮一峰）](http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html) -