快速排序没有输出

Question

我正在尝试在 JavaScript 中实现快速排序功能：

function partition(l, low, high) {
  l[0] = l[low];
  var pivotkey = l[low];
  while (low < high) {
    while (low < high && pivotkey <= l[high]) {
      --high;
    }
    l[low] = l[high];
    while (low < high && l[low] <= pivotkey) {
      ++low;
    }
    l[high] = l[low];
  }
  l[low] = l[0];
  return low;
}

function qsort(l, low, high) {
  var pivotloc;
  if (low < high) {
    pivotloc = partition(l, low, high);
    qsort(l, low, pivotloc - 1);
    qsort(l, pivotloc + 1, high);
  }
  return;
}

function quickSort(l) {
  qsort(l, 1, l.length - 1);
  return l;
}

console.log(quickSort([0, 1, 4, 3]));

但是这个程序在终端中没有输出任何东西（node qsort.js）。也许我错过了什么。谁能指出我正确的方向？如何调试此类问题？

Answer 1

我认为您的算法存在几个问题。但是我能立即注意到的一个与您在 partition 函数中使用 l.low 和 l.high 有关。我假设 l 是一个数组，在这种情况下，这两个都旨在访问 low 和 high 处的索引。如果是这样，那么这些应该是 l[low] 和 l[high].

由于您似乎正在尝试执行快速排序的就地版本，请查看此处可用的内容：In Place Quick Sort

Answer 2

所以正如你所说，数组的第一个元素将用作临时变量，它只对算法的执行有用，一开始并不清楚！

您的算法运行良好，但打印结果时遇到问题！

要得到你想要的东西，你需要通过在 quickSort() 块中添加 shift() 函数来摆脱第一个元素，这样它就变成了：

function quickSort(l) {
  qsort(l, 1, l.length - 1);
  l.shift(); // add this function
  return l;
}

如果你想使用 splice() 函数，还有另一种解决方案，它也删除第一个元素，并且具有以下形式：

array.splice(indexToRemove, numberToRemove);

所以要获得所需的结果，请将上面的指令添加到您的 quickSort() 函数中，如下所示：

function quickSort(l) {
  qsort(l, 1, l.length - 1);
   l.splice(0, 1); //add this line
  return l;
}

这是我猜测的两种解决方案。希望对您有所帮助！！

快速排序没有输出

No output in quicksort

javascript

algorithm

sorting

quicksort