时间戳

首页 > 解决方案 > 调用堆栈超出快速排序功能

javascript - 调用堆栈超出快速排序功能

问题描述

我正在为学校做一个练习，试图编写我的第一个快速排序。它正在对一个随机整数数组进行排序。当我调用它时，我收到“超出调用堆栈”错误。有人能指出我的错误吗？

const quickSort = (unsorted) => {
    //let median = Math.floor(Math.random() * unsorted.length -1);
    let median = Math.floor(unsorted.length -1 /2);
    let greater = [];
    let lesser = [];
    let sorted = [];
    
    if(unsorted.length < 2) {
        return unsorted;
    }
    for (let i = 0; i < unsorted.length; i++) {
        const element = unsorted[i];
        const pivot = unsorted[median]
        if (element > pivot) {
            greater.push(element)
        } else {
            lesser.push(element);
        }
    }
    
    let sortedLesser = quickSort(lesser);
    let sortedGreater = quickSort(greater);
    sorted = [...sortedLesser, ...sortedGreater];
    return sorted;
}

标签： javascriptarraysalgorithmsorting

解决方案

QuickSort 的一个想法是从递归调用中排除枢轴元素。这样，您可以绝对确定递归调用将始终获得较小的数组，即使枢轴位于原始数组的最末端。

如评论中所述，您的除以 2 仅适用于 1（因为除法优先于减法），这意味着您的枢轴索引始终是数组中的最后一个索引。而且由于您没有从递归调用中排除该索引，因此您会得到一个永远不会缩短数组的递归树。

我建议进行以下更改：

const quickSort = (unsorted) => {
    let median = unsorted.length >> 1; // 1 bit shift is integer division by 2
    let greater = [];
    let lesser = [];

    if (unsorted.length < 2) {
        return unsorted;
    }
    const pivot = unsorted[median]; // Do this once only
    for (let i = 0; i < unsorted.length; i++) {
        if (i === median) continue; // exclude the pivot itself
        const element = unsorted[i];
        if (element > pivot) {
            greater.push(element)
        } else {
            lesser.push(element);
        }
    }

    let sortedLesser = quickSort(lesser);
    let sortedGreater = quickSort(greater);
    // Include the pivot here
    sorted = [...sortedLesser, pivot, ...sortedGreater];
    return sorted;
}

尽管这解决了问题，但请注意快速排序的目的不是创建额外的数组，而是重新排序原始数组。

推荐阅读