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实现快速排序内容请搜索靠谱客的其他文章。