支持“快速排序”算法

Question

我的快速排序算法实现(使用递归)有问题。当我在带有重复号的数组上使用函数时，在最终结果中忽略了这些数字，我不知道为什么。有人知道我做错了什么吗？(JavaScript)

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

let quickSort = (arr) => {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[getRandomInt(arr.length)]
    let smallerArr = [];
    let greaterArr = [];
    
    for (let item of arr) {
        if (item !== pivot) {
            if (item > pivot) {
                greaterArr.push(item);
                continue
            }
            smallerArr.push(item);
        }
        
    }
    let sorted = quickSort(smallerArr);
    sorted = sorted.concat([pivot],quickSort(greaterArr));
    console.log(sorted);
    return sorted;
}
quickSort([5,7,6,23,6]);

Answer 1

您只想跳过其pivotIndex与当前index匹配的元素。我转而使用for(let i = 0,index......)方法来跟踪相同的信息。您当前要做的是跳过所有与匹配的项，这意味着如果pivot元素在数组中有重复的，也将从考虑的复制项中删除。

​

function getRandomInt(max) {
  return Math.floor(Math.random() * Math.floor(max));
}

let quickSort = (arr) => {
    if (arr.length <= 1) return arr;
    
    const pivotIndex = getRandomInt(arr.length);
    const pivot = arr[pivotIndex];
    let smallerArr = [];
    let greaterArr = [];
    for(let index = 0;index<arr.length;index++)
    {
            if(index===pivotIndex)
               continue;
            const item = arr[index];   
            if (item > pivot) 
            greaterArr.push(item);
            else 
            smallerArr.push(item);
    }
    let sorted = quickSort(smallerArr);
    sorted = sorted.concat(pivot,quickSort(greaterArr));
    console.log(sorted);
    return sorted;
}
quickSort([5,7,6,23,6,6,6,6]);

​

Answer 2

如果item !== pivot是假的，会发生什么？你好像跳过那件事了。

Answer 3

您需要清楚地说明在项目===支点时您的代码应该做什么。现在，您的代码只是忽略了这些值，因为它没有在greaterArr和smallerArr上插入。添加一个else语句来解决这个问题。