时间戳

首页 > 解决方案 > 快速排序工作和不工作代码比较

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

问题描述

我有两个快速排序的实现，只是做了一点小改动，但我无法理解为什么其中一个有效而另一个无效。

不工作 

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

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 参数。谢谢！

标签： algorithmsortingquicksort

解决方案

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

推荐阅读