关于前端:快速排序算法

疾速排序

原文链接：https://note.noxussj.top/?source=sifo

什么是疾速排序（quickSort）？

次要分成两局部实现，分区、递归操作。

分区

从数组中任意抉择一个 “ 基准 ”，所有比基准小的元素放在基准后面，比基准大的元素放在根本前面。

递归

递归地对基准前后的子数组进行分区

算法步骤

1. 首先获取数组的第一个值（作为基准）
2. 遍历以后数组，从第二个值开始，比基准元素小的 push 到 left 数组，比基准元素大的 push 到 right 数组。
3. 别离对 left 和 right 数组进行疾速排序（递归）
4. 直到以后进行快排的数组长度为 1
5. 开始合并，返回排列好的数组
6. 实现排序

动画演示链接

https://visualgo.net/zh/sorting

示意图

根底案例

• 工夫复杂度：O (n * logn)
• 空间复杂度：O (1)

    Array.prototype.quickSort = function () {const rec = (arr) => {if (arr.length <= 1) return arr
    
            const mid = arr[0]
            const left = []
            const right = []
    
            for (let i = 1; i < arr.length; i++) {if (arr[i] < mid) {left.push(arr[i])
                } else {right.push(arr[i])
                }
            }
    
            return [...rec(left), mid, ...rec(right)]
        }
    
        const res = rec(this)
    
        res.forEach((n, i) => {this[i] = n
        })
    }
    
    const arr = [5, 4, 3, 2, 1]
    
    arr.quickSort() // [1, 2, 3, 4, 5]

上方代码中递归的复杂度是 O (logn)，只有是波及到分成两半的都是 logn。分区操作的工夫复杂度为 O (n)，因为循环遍历了 arr 数组。所以整体的工夫复杂度为 O (n * logn)。空间复杂度为 O (1)，因为没有线性增长的变量。

原文链接：https://note.noxussj.top/?source=sifo