快速排序JavaScript实现遇无限递归问题求助

核心问题分析 #

1. 全局变量状态污染：flagE、flagG、flagN是全局变量，递归调用partition时不会重置，导致后续分区逻辑完全偏离预期。
2. 运算符误用：用按位与&替代逻辑与&&，条件判断逻辑彻底错误，比如N > pivot & !flagG会将布尔值转为整数计算，无法正确触发分支。
3. 未初始化指针访问：循环中直接读取arr[pointerG]或arr[pointerE]，但指针可能未被赋值（未找到对应元素时），产生undefined破坏逻辑。
4. 返回值不匹配递归需求：partition返回元素数量，但quickSort需要分区的索引位置，导致递归区间无法缩小，直接引发无限递归。
5. Pivot未正确归位：原逻辑未将pivot放到等于区域的正确位置，分区结果完全错误。

修复后的代码实现 #

基于你提供的三指针分区思路（荷兰国旗问题），重新实现正确的partition和quickSort：

const readline = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let c, arrSize;

// 三指针分区：返回[p, q]，其中arr[l..p-1] < pivot，arr[p..q] = pivot，arr[q+1..r] > pivot
function partition(arr, l, r, pivot) {
  let less = l - 1; // 小于pivot区域的最后一个索引
  let equal = l;    // 当前遍历的指针
  let greater = r + 1; // 大于pivot区域的第一个索引

  while (equal < greater) {
    if (arr[equal] < pivot) {
      less++;
      [arr[less], arr[equal]] = [arr[equal], arr[less]];
      equal++;
    } else if (arr[equal] > pivot) {
      greater--;
      [arr[equal], arr[greater]] = [arr[greater], arr[equal]];
    } else {
      // 等于pivot，直接移动遍历指针
      equal++;
    }
  }

  // 返回小于区域的最后索引和大于区域的起始索引
  return [less, greater];
}

function quickSort(arr, l, r) {
  if (l < r) {
    let x = Math.floor((l + r) / 2);
    let pivot = arr[x];
    let [less, greater] = partition(arr, l, r, pivot);
    // 递归排序小于区域和大于区域，等于区域无需排序
    quickSort(arr, l, less);
    quickSort(arr, greater, r);
  }
}

readline.on('line', input => {
  let arr;
  if (!c) {
    arrSize = Number(input);
    c = 1;
  } else if (c === 1) {
    arr = input.split(' ').map(Number);
    c++;
  }
  if (c === 2) {
    quickSort(arr, 0, arrSize - 1);
    console.log(arr.join(' '));
    readline.close();
  }
});

修复说明 #

• 移除全局变量：所有标志和指针变量都在partition内部初始化，避免递归时的状态污染。
• 修正运算符：全部替换为逻辑与&&，确保条件判断正确。
• 三指针分区逻辑：严格实现荷兰国旗分区法，将数组分为小于、等于、大于pivot的三个区域，逻辑清晰且无漏洞。
• 正确的递归区间：partition返回小于区域的最后索引和大于区域的起始索引，递归时仅处理需要排序的区域，避免无限递归。
• Pivot处理：直接基于选中的pivot进行分区，无需额外移动pivot，逻辑更简洁。

内容的提问来源于stack exchange，提问作者mhawk