JavaScript快速排序出现最大调用栈溢出问题排查：是算法缺陷还是硬件限制？

嘿，我来帮你捋清楚这个问题：这绝对不是旧电脑的硬件限制导致的，完全是你写的递归版快速排序在处理大规模数据时触发了调用栈溢出。

为什么会出现栈溢出？ #

你当前的快速排序实现每次固定选择区间的最后一个元素作为基准值（pivot）。如果你的85000个对象数组本身接近有序（或者逆序），每次分区后，其中一个子区间的长度会几乎和原区间一样大，这会导致递归调用的层数达到**O(n)**级别——简单说就是要递归调用几万次，而JavaScript引擎的调用栈上限一般只有几千层，自然就触发了Maximum call stack size exceeded错误。

而3500个元素时，递归层数刚好没超过栈上限，所以能正常运行。

怎么修复这个问题？ #

这里给你几个可行的方案，按推荐程度排序：

方案1：直接用JavaScript内置的Array.sort() #

如果是原型开发，完全没必要自己手写排序！JS内置的sort()采用的是Timsort算法，经过了大量优化，性能、稳定性都远超手写的递归快排，还能轻松处理多属性排序：

// 实现多属性排序：先按partido，再按nome_parlamentar，最后按id_documento
gastos.sort((a, b) => {
  // 先比较partido
  const partidoCompare = a.partido.localeCompare(b.partido);
  if (partidoCompare !== 0) return partidoCompare;
  
  // partido相同则比较nome_parlamentar
  const nomeCompare = a.nome_parlamentar.localeCompare(b.nome_parlamentar);
  if (nomeCompare !== 0) return nomeCompare;
  
  // 最后比较id_documento（数字类型直接相减）
  return a.id_documento - b.id_documento;
});

直接替换掉原来的quickSort2调用就行，一行导入代码都不用改。

方案2：优化基准值的选择（修复递归版快排） #

如果你坚持要自己实现快排，那首先要改掉固定选最后一个元素当pivot的逻辑，换成更优的策略，比如随机选择pivot或者选首、中、尾的中位数，这样能把递归深度降到O(log n)级别（85000个元素的话，递归层数大概只有17层，完全不会溢出）。

修改后的递归快排代码：

import { gastos } from './cota-parlamentar-282-mil.mjs';

function quickSort2(vetor, listaPropriedadesOrdenacao) {
  quickSort(vetor, listaPropriedadesOrdenacao[0]);
}

function quickSort(vetor, propriedadeOrdenacao, ini = 0, fim = vetor.length - 1) {
  if (fim > ini) {
    // 随机选择pivot，交换到当前区间的末尾，保持原有分区逻辑
    const randomPivotIndex = Math.floor(Math.random() * (fim - ini + 1)) + ini;
    [vetor[randomPivotIndex], vetor[fim]] = [vetor[fim], vetor[randomPivotIndex]];
    
    const pivot = fim;
    let div = ini - 1;
    for (let i = ini; i < fim; i++) {
      if (vetor[i][propriedadeOrdenacao] < vetor[pivot][propriedadeOrdenacao]) {
        div++
        if (i !== div) {
          [vetor[i], vetor[div]] = [vetor[div], vetor[i]]
        }
      }
    }
    div++
    if (vetor[pivot][propriedadeOrdenacao] < vetor[div][propriedadeOrdenacao]) {
      [vetor[pivot], vetor[div]] = [vetor[div], vetor[pivot]]
    }
    quickSort(vetor, propriedadeOrdenacao, ini, div - 1)
    quickSort(vetor, propriedadeOrdenacao, div + 1, fim)
  }
}

quickSort2(gastos, ['partido', 'nome_parlamentar', 'id_documento']);

方案3：改用迭代版快排 #

彻底抛弃递归，用数组模拟栈来实现快排，完全避免调用栈溢出的问题：

import { gastos } from './cota-parlamentar-282-mil.mjs';

function quickSort2(vetor, listaPropriedadesOrdenacao) {
  quickSortIterative(vetor, listaPropriedadesOrdenacao[0]);
}

function quickSortIterative(vetor, propriedadeOrdenacao) {
  // 用数组模拟调用栈，存储每个待处理的区间
  const stack = [{ ini: 0, fim: vetor.length - 1 }];

  while (stack.length > 0) {
    const { ini, fim } = stack.pop();
    if (fim <= ini) continue;

    // 随机选pivot
    const randomPivotIndex = Math.floor(Math.random() * (fim - ini + 1)) + ini;
    [vetor[randomPivotIndex], vetor[fim]] = [vetor[fim], vetor[randomPivotIndex]];
    
    const pivot = fim;
    let div = ini - 1;
    for (let i = ini; i < fim; i++) {
      if (vetor[i][propriedadeOrdenacao] < vetor[pivot][propriedadeOrdenacao]) {
        div++;
        if (i !== div) {
          [vetor[i], vetor[div]] = [vetor[div], vetor[i]];
        }
      }
    }
    div++;
    if (vetor[pivot][propriedadeOrdenacao] < vetor[div][propriedadeOrdenacao]) {
      [vetor[pivot], vetor[div]] = [vetor[div], vetor[pivot]];
    }

    // 先压入较大的区间，再压入较小的区间，优化栈空间占用
    stack.push({ ini: div + 1, fim });
    stack.push({ ini, fim: div - 1 });
  }
}

quickSort2(gastos, ['partido', 'nome_parlamentar', 'id_documento']);

额外提醒 #

你的quickSort2目前只用到了排序属性列表的第一个元素，如果需要实现多属性排序（比如先按partido排序，相同partido的再按nome_parlamentar排序），不管用哪种方案，都要调整比较逻辑——上面的内置sort()示例已经完整实现了这个逻辑。

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