快速排序有效和无效代码比较

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
}

正在工作这里唯一的变化是代替了“ end”参数，我在for循环中使用了arr.length

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)。但是，在您提到的“有效”代码中，您始终会迭代直到整个数组的最后一个元素，这就是处理案例的原因。但是永远不要那样做，因为它不会为提高复杂性做出任何贡献。