代码之家 › 专栏 › 技术社区 › John A

快速排序中的递归

quicksort sorting algorithm javascript

John A · 技术社区 · 7 年前

我目前正试图用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();

2 回复 | 直到 7 年前

MBo 7 年前

一些错误:

if (start <= end) { start = end

怎样 for (var j = 0 当范围从开始开始时以0开始?

if (array[j] <= x) {

arunk2 7 年前

  //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();

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前