快速排序是一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序基于冒泡、递归分治。他在大数据情况下是最快的排序算法之一，平均事件复杂度很低而且前面的系数很小，在大量随机输入的情况下最坏情况出现的概率是极小的。

最坏时间复杂度：O() 当选择的基准值为最大值或最小值时

稳定性：不稳定

平均时间复杂度：O(n*n)

设计思想

快排有一个很形象的概念：挖坑填数 + 分治法，分三个步骤实现：

• 从数组中取出一个数作为基准(pivot)。
• 在原数组中进行移动，将大于基准的数放到基准右边，小于基准的数放到基准左边，在基准左右形成两个子数组。
• 在左右子数组中反复执行步骤1、2，直到所有子数组只剩下一个数。

动图演示

阮一峰版

好吧，印象中以前看快排的时候有两种写法，最近学习的时候特地搜了一下，原来有一版是阮一峰写的，不过这版好像在网上争议挺大的（咱废渣也不敢问，还是老实学（bei）吧（shu）。

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

阮一峰的写法很明确也很符合上述思路，构造两个空数组，将比基准大的放到右数组，比基准小的放到左数组，然后递归执行。

总结一下网上对阮一峰版的快排争议点主要是：

1. 空间复杂度的问题
2. 每次都需要开辟出两个新数组以及splice的复杂度（这又扯到1上面了）
3. 没有遵循原地(in-place)快排
4. 代码执行的时间比较长？？？

好吧，鉴于个人能力问题，此处不谈--。不过第四点好像每次执行的时间都不一样，差距还挺大的（500ms-2000ms）。

正常版

function customQuickSort(arr,leftIndex,rightIndex){
    let pivot = arr[leftIndex];
    let i = leftIndex;
    let j = rightIndex;
    if(i < j){
        while(i < j && arr[j] >= pivot){
            j--
        }
        if(i < j){
            arr[i++] = arr[j]
        }
        while(i < j&&arr[i] <= pivot){
            i++
        }
        if(i < j){
            arr[j--] = arr[i]
        }
        arr[i] = pivot;
        customQuickSort(arr, leftIndex, i - 1)
        customQuickSort(arr, i + 1, rightIndex)
        return arr
    }
}

参考

前端十大经典算法