深入理解快速排序

#算法/排序

快速排序

一句话总结 `快排排序`

一句话总结了归并排序：
- 先把左半边数组排好序
  - base case：lo === hi
- 再把右半边数组排好序
  - base case：lo === hi
- 然后把两半数组合并
  - merge 两个有序数组
那么，一句话总结 快排 呢？
- 先将一个元素排好序，
- 然后再将剩下的元素排好序。如何理解？如下图：

`快速排序`的过程是一个 `构造二叉搜索树`的过程

看下图就明白了：

最后，可不就是一个二叉搜索树吗？如下图

构造时，如果运气特别不好，构造出一个特别不平衡的二叉树 ，如下图，解决方案是：构造前洗牌数组先。

如何理解快速排序是 `二叉树前序遍历` ?

看动图，这不就是 二叉树的前序遍历 吗？

再看代码框架

上面代码 p 、 p-1 、 p+1 分别都有具体含义的！

实现方式1：js的简易实现

// 1、找基准值，然后分成两个数组
// 2、与该基准点数据比较，如果比它小，放左边；反之，放右边。
// 3、左右分别用一个空数组去存储比较后的数据。
// 4、最后递归执行上述操作，直到数组长度 <= 1
const quickSort1 = arr => {
    if (arr.length <= 1) {
        return arr;
    }
    // 取基准点
    const midIndex = Math.floor(arr.length / 2);
    // 取基准点的值，splice(index,1) 则返回的是含有被删除的元素的数组。
    const midIndexVal = arr.splice(midIndex, 1)[0];
    const left = []; // 存放比基准点小的数组
    const right = []; // 存放比基准点大的数组
    // 遍历数组，进行判断分配
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midIndexVal) {
            left.push(arr[i]); //比基准点小的放在左边数组
        } else {
            right.push(arr[i]); //比基准点大的放在右边数组
        }
    }
    //递归执行以上操作，对左右两个数组进行操作，直到数组长度为 <= 1
    return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
const array2 = [5, 4, 3, 2, 1];
console.log('quickSort1 ', quickSort1(array2));

使用 splice 就行分割，然后最后递归，遍历

另外，该实现没有完全参考上面的代码模板，使用了JavaScript 一些语言特性，但是，没有解决前序遍历构造二叉树搜索树时，运气特别差的场景。