在 JavaScript 中的双元素数组上实现 MergeSort

Question

我正在尝试使用合并排序来对边缘集数组进行排序，这些边缘集本身表示为 2 元素数组，即边缘 EC ['E', 'C'] .

我尝试排序的数组是[['D', 'F'], ['A', 'D'], ['F', 'I'], ['B', 'E'], ['B', 'J'], ['A', 'C'], ['E', 'G'], ['A', 'J'], ['G', 'H']] .我希望它首先按"从"边缘排序，然后如果两条边缘具有相同的"从"边缘，则按"到"（第二个）边缘排序。

当我在Firebug中运行以下内容时，它看起来正在工作（从我正在打印到控制台的内容），但是最后它给出了['AC', 'AC', 'AC', 'AC', 'AC', ...].

Array.prototype.toString = function(){
  var s = "[";
  if(this.length > 0){
    s += this[0].toString();
    for(var i = 1; i < this.length; i++){
      s += ", " + this[i].toString();
    }
  }
  s += "]";
  return s;
}
var edges = [['D', 'F'], ['A', 'D'], ['F', 'I'], ['B', 'E'], ['B', 'J'],
             ['A', 'C'], ['E', 'G'], ['A', 'J'], ['G', 'H']];
function sortEdges(edges){
  // mergesort
  // split up
  if(edges.length < 2){
    return edges;
  } else {
    var fH = edges.slice(0, Math.floor(edges.length / 2)); // fH: firstHalf
    var sH = edges.slice(Math.floor(edges.length / 2), edges.length); // sH: firstHalf
    console.log(fH.toString());
    console.log(sH.toString());
    fH = sortEdges(fH);
    sH = sortEdges(sH);
    // merge
    var fHC = 0; // fHC: firstHalfCounter
    var sHC = 0; // sHC: secondHalfCounter
    var bothHalves = new Array();
    for(var i = 0; i < edges.length; i++){
      console.log("fHC: " + fHC + ", sHC: " + sHC + ", bothHalves: " + bothHalves.toString());
      if(fHC < fH.length && (sHC >= sH.length || fH[fHC][0] < sH[sHC][0])){ 
        // compare 'from' vertex
        bothHalves.push(fH[fHC]);
        fHC++;
      } else if(fHC < fH.length && fH[fHC][0] == sH[sHC][0]){ 
        // if tied, compare 'to' vertex
        if(fH[fHC][1] <= sH[sHC][1]){
          bothHalves.push(fH[fHC]);
          fHC++;
        } else {
          bothHalves.push(sH[sHC]);
          sHC;
        }
      } else {
        bothHalves.push(sH[sHC]);
        sHC++;
      }
    }
    return bothHalves;
  }
}
edges = sortEdges(edges);
console.log(edges.toString());

Answer 1

你省略了一个增量：

Array.prototype.toString = function(){
  var s = "[";
  if(this.length > 0){
    s += this[0].toString();
    for(var i = 1; i < this.length; i++){
      s += ", " + this[i].toString();
    }
  }
  s += "]";
  return s;
}
var edges = [['D', 'F'], ['A', 'D'], ['F', 'I'], ['B', 'E'], ['B', 'J'],
             ['A', 'C'], ['E', 'G'], ['A', 'J'], ['G', 'H']];
function sortEdges(edges){
  // mergesort
  // split up
  if(edges.length < 2){
    return edges;
  } else {
    var fH = edges.slice(0, Math.floor(edges.length / 2)); // fH: firstHalf
    var sH = edges.slice(Math.floor(edges.length / 2), edges.length); // sH: firstHalf
    console.log(fH.toString());
    console.log(sH.toString());
    fH = sortEdges(fH);
    sH = sortEdges(sH);
    // merge
    var fHC = 0; // fHC: firstHalfCounter
    var sHC = 0; // sHC: secondHalfCounter
    var bothHalves = new Array();
    for(var i = 0; i < edges.length; i++){
      console.log("fHC: " + fHC + ", sHC: " + sHC + ", bothHalves: " + bothHalves.toString());
      if(fHC < fH.length && (sHC >= sH.length || fH[fHC][0] < sH[sHC][0])){ 
        // compare 'from' vertex
        bothHalves.push(fH[fHC]);
        fHC++;
      } else if(fHC < fH.length && fH[fHC][0] == sH[sHC][0]){ 
        // if tied, compare 'to' vertex
        if(fH[fHC][1] <= sH[sHC][1]){
          bothHalves.push(fH[fHC]);
          fHC++;
        } else {
          bothHalves.push(sH[sHC]);
          sHC++;
         //  ^^ You left out this increment   <--------------HERE----------------
        }
      } else {
        bothHalves.push(sH[sHC]);
        sHC++;
      }
    }
    return bothHalves;
  }
}
edges = sortEdges(edges);
console.log(edges.toString());