快速排序

快速排序的时间复杂度为 O(NlogN)
判断条件：会用到for循环，只要有for循环，那就肯定有个N，N的执行次数就是执行递归的次数。每次递归都是将数组分为左树和右树，相当于折半，所以是logN，最后总结起来快速排序的时间复杂度为O(NlogN)。

快速排序是目前已知的 '交换排序' 最快的排序方法。

O(NlogN) => 约等于2的1.3次方 - 1.4次方

快速排序的缺点：快速排序是个不稳定的排序。不稳定的因素在于快速排序的第一步初始化一个标识符pivot。因为你不知道pivot是多少，无法平衡左树和右树的数量。

快速排序： 二叉树 + 递归的思想

• 1.初始化一个标识符
• 2. 初始化一个左树，一个右树
• 3. for循环遍历该数组中剩下的元素进行比较，小的放左树，大的放右树
• 4.把左侧和右侧的内容进行递归调用
• 5.设置判断条件 当arr的长度小于等于1的时候，没有必要继续比较（跳出递归）

let arr = [5, 2, 3, 1, 7, 9, 4, 10, 6, 8, 10]
        // 快速排序
        // 二叉树
        let quickSort = (arr) => {
            // 5.设置判断条件 当arr的长度小于等于1的时候，没有必要继续比较
            if (arr.length <= 1) return arr
            // 1.初始化一个标识符
            // 队列方法：shift unshift 往前加数据，往前删数据
            // 栈方法：push pop 先进后出
            let pivot = arr.shift() // 使用队列方法获取第一个值，不仅得到一个返回值，还会对原数组进行删除
            // 2. 初始化一个左数，一个右数
            let left = [],
                right = []
            // 3. for循环遍历该数组中剩下的元素进行比较，小的放左树，大的放右树
            for (let i = 0; i < arr.length; i++) {
                if (arr[i] < pivot) {
                    left.push(arr[i])
                } else {
                    right.push(arr[i])
                }
            }
            // 4.把左侧和右侧的内容进行递归调用
            return [...quickSort(left), pivot, ...quickSort(right)]
        }

        console.log(quickSort(arr));
// 结果：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10

快速排序改良： 二叉树 + 递归 + filter方法

• 1. 解构赋值，将第一个值赋值给pivot，剩下的部分赋值给newArr
• 2.用filter方法过滤出左树和右树
• 3.设置递归跳出条件

let arr = [5, 2, 3, 1, 7, 9, 4, 10, 6, 8, 10]
        // 快速排序
        let quickSort = (arr) => {
            if (!arr.length) return []
            // 1.将第一个值赋值给pivot，剩下的部分赋值给newArr
            let [pivot, ...newArr] = arr,
            // 2.用filter方法过滤出左树和右树    
            left = newArr.filter(e => e < pivot),
                right = newArr.filter(e => e > pivot);

            return [...quickSort(left), pivot, ...quickSort(right)]
        }

        console.log(quickSort(arr));
// 结果：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10

Array.prototype.sort()

Array.prototype.sort源码用两种排序方法
插入排序（10个和10个数据以下）
快速排序（10个以上数据）