快速排序的基本原理

采用“分治”的思想，对于一组数据，选择一个基准元素，通常选择第一个或最后一个元素，通过第一轮扫描，比基准小的元素都在base左边，比基准大的元素都在基准右边，再有同样的方法递归排序这两部分，直到序列中所有数据均有序为止。它与其他排序算法相比，它具有较好的性能。

简单来说，快速排序可以包含三步骤：

拾取：选择一个基准。
拆分：拆分问题集，将较小的部分移到基准的左侧，将较大的部分移到右侧。
重复递归查找：重复步骤并组合之前已排序的数组。

图文详解

让我们看一个例子来更好地理解快速排序算法。（如下图所示）包含未排序的值，我们将使用快速排序对其进行排序。

选择基准

该过程首先从列表中选择一个元素（我们称它为pivot）；当然了，这可以是任何元素，对于本例，我们将使用最后一个元素4作为我们的轴心。

处理数组

然后我们来简化一下这个例子：

从7开始的每个元素都将与基准（4）进行比较。第二个指针将被放置在7，因为7大于4。
下一个元素，即元素2，现在将与基准进行比较。由于2小于4，它将被之前发现的更大的数字7所取代。
数字7和2互换。现在，将基准与小于4的下一个元素1进行比较。
然后，7将再次与1交换。
该过程继续进行，直到到达倒数第二个元素，然后在结束时用第二个指针替换基准元素。此处，编号4（基准）将替换为编号6。

由于元素2、1和3小于4，因此它们位于基准的左侧。元素可以是任何顺序：“1”、“2”、“3”或“3”、“1”和“2”，“3”和“1”。唯一的要求是所有元素都必须小于基准。类似的在右侧，无论其顺序如何，所有组件都应大于基准。

简单来说，该算法搜索每一个小于基准的值。小于pivot的值将放置在左侧，而大于pivot值的值将放在右侧。重新排列值后，它将把基准设置在其排序位置。

区分数组

一旦我们划分了数组，我们就可以把这个问题分解成两个部分。首先，将数组的比基准小的到基准的左侧，然后将数组比基准大的到基准的右侧。

与我们在步骤2中重新排列元素的方式相同，我们将为每个左右子部分分别选择一个基准元素。
现在，我们将重新排列子列表，使所有元素都小于向左的基准点。例如，元素3是三个元素中最大的，满足条件，因此元素3处于其排序位置。
以类似的方式，我们将再次处理子列表并对元素2和1进行排序。当我们在最后得到一个元素时，我们将停止这个过程。
对右侧的子列表重复相同的过程。子数组被细分，直到每个子数组只包含一个元素。
现在，数组已经排序好了:)

代码示例

Array.prototype.quickSort = function() {
    const rec = (arr) => {
        if(arr.length <= 1) return arr;
        let left = [];
        let right = [];
        const base = arr[0];
        // 因为基准线是arr[0]，所以从下标是1也就是第二个开始
        for(let i = 1; i < arr.length; i += 1) {
            if(arr[i] < base) {
                left.push(arr[i])
            } else {
                right.push(arr[i])
            }
        }
        return [...rec(left), base, ...rec(right)];
    }
    const res = rec(this);
    res.forEach((item, key) => {
        this[key] = item;
    })
}

const arr = [1, 5, 9, 3, 18, 6, 2, 7]
arr.quickSort()
console.log(arr);