支持“快速排序”算法

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]);

- JakubGamer

Answer 1

你只想跳过与当前索引匹配的“pivotIndex”元素。我改为使用“for（let i = 0，index ......）”方法来跟踪相同条件。你目前正在跳过所有值与“pivot”匹配的项目，这意味着如果在数组中有重复的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]);

- Lakshya Thakur

---

非常感谢！我一定是忽略了那个漏洞。祝你有美好的一天！ - JakubGamer

Answer 2

item !== pivot 为假时会发生什么？你似乎跳过了该项。

- Kristof Neirynck

---

请参见上面的回复。 - JakubGamer

Answer 3

你需要明确你的代码在 item === pivot 时应该做什么。 目前你的代码只是忽略了这些值，因为它没有插入到更大的数组和更小的数组中。 添加一个 else 语句来解决这个问题。

- Viviane Costa