时间戳

首页 > 解决方案 > 是否可以在快速排序中使用 slice()？

javascript - 是否可以在快速排序中使用 slice()？

问题描述

我正在学习快速排序，下面是代码：

const pivot1 = (arr, low = 0, high = arr.length -1) => {
    let pivot = arr[low];
    let index = low;

    for(let i = low + 1; i <= high; i++){
        if(pivot > arr[i]){
            index++;
            [arr[index], arr[i]] = [arr[i], arr[index]]; 
        }
    }
    [arr[low], arr[index]] = [arr[index], arr[low]];

    return index;
}

const quickSort1 = (arr, low = 0, high = arr.length - 1) => {
    if(low < high){
        let pivot = pivot1(arr, low, high); 
        quickSort1(arr, low, pivot - 1);
        quickSort1(arr, pivot + 1, high);
    }
    return arr;
}

console.log(quickSort1([5,2,1,8,4,7,6,3]));  // [1,2,3,4,5,6,7,8]

但是，如果我不想设置low和high参数，并尝试slice()在quickSort2函数表达式中使用，那么排序似乎有问题，我不知道（递归不能按预期工作）。有人能告诉我为什么会这样吗？如果我像骡子一样固执slice()，我是否仍然可以让这个功能工作？

ps，我把pivot改成pivot2函数表达式的最后一个元素，所以pivot2和pivot1.

const pivot2 = (arr) => {
    let pivot = arr[arr.length - 1];
    let index = -1;

    for(let i = 0; i < arr.length - 1; i++){
        if(pivot > arr[i]){
            index++;
            [arr[index], arr[i]] = [arr[i], arr[index]];
        }
    }
    [arr[arr.length - 1], arr[index + 1]] = [arr[index + 1], arr[arr.length - 1]];

    return index + 1;
}

const quickSort2 = (arr) => {
    if(0 < arr.length - 1){
        let pivot = pivot2(arr);
        let left = arr.slice(0, pivot);
        let right = arr.slice(pivot + 1);
        quickSort2(left);
        quickSort2(right);
    }
    return arr;
}

console.log(quickSort2([5,2,1,8,4,7,6,3]));  // [2,1,3,8,4,7,6,5]

标签： javascriptslicequicksort

解决方案

您不应该使用 slice，因为它不会改变下面的数组。您可以传递左右索引，也可以保存两个递归快速排序的结果并合并数组。

const left_array = quickSort2(left);
const right_array = quickSort2(right);
arr = [...left_array, ...right_array];

右切片也将具有枢轴作为参数而不是枢轴+ 1，因为切片不包括结束索引。

切片 MDN 参考

推荐阅读