在我的快速排序中递归

Question

我目前正在尝试对 javascript 中的数组实施快速排序。我有总体布局，但由于某种原因递归不起作用。它似乎适用于代码的第二次迭代，但在那之后，它似乎就搞砸了。不确定我做错了什么。

function main() {
  var type = "quicksort"
  var testArray = [9, 6, 5, 0, 8, 2, 4, 7];

  quickSort(testArray, 0, testArray.length - 1);
  for (var i = 0; i < testArray.length; i++) {
    console.log(testArray[i]);
  }

}

function quickSort(array, start, end) {
  var type = "quicksort"
  var pIndex;

  if (start <= end) {
    pIndex = partition(array, start, end);
    quickSort(array, start, pIndex - 1);
    quickSort(array, pIndex + 1, end);
  }


}

function partition(array, start, end) {
  var x = end;
  console.log(start);
  var i = start - 1;
  var temp;

  for (var j = 0; j < end - 1; j++) {
    if (array[j] <= x) {
      i++;
      temp = array[j];
      array[j] = array[i];
      array[i] = temp;
      temp = 0;


    }
  }

  temp = array[i + 1];
  array[i + 1] = array[x];
  array[x] = temp;
  temp = 0;

  return i + 1;
}

main();

Answer 1

一些错误：

if (start <= end) {没有必要处理病例start = end

当range从start开始时，for (var j = 0如何从0开始？

if (array[j] <= x) {你比较索引和项目价值？

Answer 2

错误是

@function 快速排序

  //if (start <= end)  
  // should be 
  if (start < end)

@函数分区

//for (var j = 0; j <= end - 1; j++) {
// if (array[j] <= x) {
// Should be
for (var j = start; j <= end - 1; j++) {
  if (array[j] <= array[x]) {

以下代码应该可以工作。

function main() {
  var type = "quicksort"
  var testArray = [9, 6, 5, 0, 8, 2, 4, 7];

  quickSort(testArray, 0, testArray.length - 1);
  for (var i = 0; i < testArray.length; i++) {
    console.log(testArray[i]);
  }

}

function quickSort(array, start, end) {
  var type = "quicksort";
  var pIndex;

  if (start < end) {
    pIndex = partition(array, start, end);
    quickSort(array, start, pIndex - 1);
    quickSort(array, pIndex + 1, end);
  }


}

function partition(array, start, end) {
  var x = end;
  console.log(start);
  var i = start - 1;
  var temp;

  for (var j = start; j <= end - 1; j++) {
    if (array[j] <= array[x]) {
      i++;
      temp = array[j];
      array[j] = array[i];
      array[i] = temp;
      temp = 0;
    }
  }

  temp = array[i + 1];
  array[i + 1] = array[x];
  array[end] = temp;
  temp = 0;

  return i + 1;
}

main();

希望对您有所帮助！

在我的快速排序中递归

recursion in my quicksort

javascript

sorting

algorithm

quicksort