关于快速排序算法的一个问题
发布于 8 个月前 作者 qxl1231 922 次浏览 来自 问答
//快速排序优化=>基于冒泡+二分查找
const quickSort = (arr) => {
    if (arr.length <= 1) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    let midNum = arr.splice(mid, 1)[0];
    // let midNum=arr[mid];//这里为什么要用splice?如果用下面这种,会循环递归,死循环报错,用上面的方式就会执行结束
    console.log(mid);
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midNum) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    // console.log(left,right)
    return quickSort(left).concat(midNum, quickSort(right))

};
let arr = [5, 7, 2, 9, 3, 8, 4, 17, 1, 11];

console.log(quickSort(arr));

代码在上面,如果使用注释的那种方式获取中间值,则会死循环,值一直是1,但是用splice就会自动终止. 这是为什么?

4 回复

splice会改变原数组

1.快速排序空间上是原址排序 上面的算法中间划分的时候生成了两个数组,合并的时候又生成新的,所以其实本质不属于快速排序 2.你的注释会导致返回的数组里midNum项重复了一次

1楼正解,确实是因为splice之后 改变了最后一次的arr的长度, 本来是left/right中肯定有一个空数组,经过splice之后变成了1,所以递归的 基本条件满足,就退出了

回到顶部