js实现快速排序的思路

分区:从数组中选择任意一个元素作为基准,所有比基准小的元素放在基准前面,比基准大的元素放在基准的后面

第二步递归:递归对基准前后的子数组进行分区

如果比16小的话我们标准成绿色,如果比16大的话我们标志成紫色.

如果遇到比基准小的元素而且比他目前选择的元素小的话我们把这个元素移到靠前的位置


挨着前面元素往前排 如动画

第一轮 排序完成
我们找到所以比基准小的元素和比基准大的元素了.

此时我们可以保证16已经在他合适的位置上了

Array.prototype.quickSort = function() {
    //创建一个递归
    const rec = (arr) => {
            if (arr.length === 1) { return arr; }
            //思考这个递归怎么写
            const left = [];
            const right = [];
            const mid = arr[0];
            for (let i = 1; i < arr.length; i += 1) {
                if (arr[i] < mid) {
                    left.push(arr[i]);
                } else {
                    right.push(arr[i]);
                }
                //此时已经完成了分区操作
                //考虑对两边的子数组进行分区操作
            }
            //排序后的left mid  right
            return [...rec(left), mid, ...rec(right)];
        }
        //把rec逐个拷贝到this上
    const res = rec(this);
    res.forEach(n, i) => { this[i] = n };
};

const arr = [5, 4, 3, 2, 1, ];
arr.quickSort();

最后

以上就是粗心蜜粉为你收集整理的js实现快速排序的思路的全部内容，希望文章能够帮你解决js实现快速排序的思路所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。