快速排序工作和不工作代码比较

Question

我有两个快速排序的实现，只是稍作改动，但我不明白为什么其中一个有效而另一个无效。

不工作

function quickSort(arr, left = 0, right = arr.length){
  console.log(arr,left,right)
  if (left < right){
    let middle = pivot(arr, left, right)
    console.log(middle)
    quickSort(arr, left, middle-1)
    quickSort(arr, middle+1, right)
  }
  return arr
}


function pivot(arr, start = 0, end = arr.length)
// returns the correct index
{
 function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  let pivot = arr[start];
  let index = start;
  for (let i = start + 1; i < end; i++){
    if(pivot > arr[i]){
      index++
      swap(arr,i,index)
    }
  }
  swap(arr,index, start)
  return index
}

工作这里唯一的变化是我在 for 循环

中使用 arr.length 而不是使用 "end" 参数

function quickSort(arr, left = 0, right = arr.length){
  console.log(arr,left,right)
  if (left < right){
    let middle = pivot(arr, left, right)
    console.log(middle)
    quickSort(arr, left, middle-1)
    quickSort(arr, middle+1, right)
  }
  return arr
}


function pivot(arr, start = 0, end = arr.length)
// returns the correct index
{
 function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  let pivot = arr[start];
  let index = start;
  for (let i = start + 1; i < arr.length; i++){
    if(pivot > arr[i]){
      index++
      swap(arr,i,index)
    }
  }
  swap(arr,index, start)
  return index
}

两种逻辑完全相同，我找不到区别。理想情况下，我想在我的代码中重用 end 参数。谢谢！

Answer 1

观察你的代码，我知道 quickSort(arr, left, right) 将对 [left, right) 的范围进行排序。意味着您不在排序算法中包括 arr[right] 。因此，当您递归调用 quickSort(arr, left, middle-1) 时，arr[middle-1] 将永远不会包含在您的排序算法中。所以，它不起作用。你应该做到 quickSort(arr, left, middle)。但是，在您提到的 "working" 代码中，您总是迭代到整个数组的最后一个元素，这就是处理这种情况的原因。但永远不应该那样做，因为它对提高复杂性没有任何贡献。

快速排序工作和不工作代码比较

Quick sort working and not-working code comparison

sorting

algorithm

quicksort