本文主要介绍了web前端入门到精通---JavaScript实现快速排序算法 ，通过具体的内容向大家展现，希望对大家前端开发Javascript的学习有所帮助。

JavaScript实现经典排序算法—快排

快速排序算法的性能比之前的冒泡、选择排序都要好，和归并排序一样，是一个可以用于实战的算法，听说chrome用的就是快排

又听说前端面试会考，那你实现一个快排吧！

一、快速排序的算法思路

还是在这里看一下快排是啥意思

快速排序算法动图

1、快速排序的特点就是随机设置一个基准点，比如是数组的第一个元素，然后数组的其他元素就跟这个基准线进行对比，比基准线大的放在左边，比基准线小的放在右边

2、再设置一个基准线，再这样小的放左边，大的放右边，递归。

二、编码实现

详细分析写在注释里了

Array.prototype.quickSort = function() {

    const rec = (arr) => {

        // 递归都是要有尽头的，不然会无限进行下去

        // 直到Maximum call stack size exceeded

        // 别问我为什么知道

        // 而且注意，这里要有小于1，不然也会报错

        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，赋值到this也就是当前数组本身

    res.forEach((item, key) => {

        this[key] = item;

    })

}

const arr = [1, 5, 9, 3, 18, 6, 2, 7]

arr.quickSort()

console.log(arr);

三、算法时间复杂度

1、这种劈成两半递归，时间复杂度一般是O(logn)

2、递归里面，for循环对比，时间复杂度是O(n)

所以时间复杂度是O(nlogn)

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评