2

我正在尝试使用 javascript 中的合并排序算法来实现反转计数。我在这个网站上找到了描述和伪代码。我的实现如下所示：

var mergeAndCount, sortAndCount;

/*
the merging routine
@param List1 the first list to be merged
@param List2 the second list to be merged
*/

mergeAndCount = function(List1, List2) {
  var count, outputList;
  outputList = [];
  count = 0;
  while (List1.length > 0 || List2.length > 0) {
    outputList.push(Math.min(List1[0], List2[0]));
    if (List2[0] < List1[0]) {
      count += List1.length;
      List2.shift();
    } else {
      List1.shift();
    }
  }

  outputList = outputList.concat(List1.concat(List2));
  return {
    'count': count,
    'list': outputList
  };
};

/*
count inversion algorithm
@param List the sequence to be sorted
*/
sortAndCount = function(List) {
  var List1, List2, mergeOut, output1, output2;
  if (List.length < 2) {
    return {
      'count': 0,
      'list': List
    };
  } else {
    List1 = List.splice(0, List.length / 2);
    List2 = List;
    output1 = sortAndCount(List1);
    output2 = sortAndCount(List2);
    mergeOut = mergeAndCount(List1, List2);
    return {
      'count': output1.count + output2.count + mergeOut.count,
      'list': mergeOut.list
    };
  }
};

我想在这里的 Jsfiddle上对其进行测试，但它崩溃了（使用了太多内存）。不知何故，它适用于 inupt [1, 3, 2] 但不适用于其他。如果我的实现或原始伪代码是错误的，我不确定出了什么问题。

4

2 回答 2

3

错误1：无限循环

当它开始比较未定义的数字时，while 会持续很长时间。如果List1.length为 0，则比较List2[0] < List1[0]将始终为 false，导致List1.shift()which 没有任何变化。

代替：

while (List1.length > 0 || List2.length > 0) {

和：

while (List1.length > 0 && List2.length > 0) {

错误 2：操作数组

您更改数组，然后使用您期望的初始值。在每个函数开始时，您应该复制数组（使用 slice 是最快的方法）。

错误 3：忽略 sortAndCount 的输出

代替：

mergeOut = mergeAndCount(List1, List2);

和：

mergeOut = mergeAndCount(output1.list, output2.list);

正确解决方案：

var mergeAndCount, sortAndCount;

/*
the merging routine
@param List1 the first list to be merged
@param List2 the second list to be merged
*/

mergeAndCount = function(List1, List2) {
  List1 = List1.slice();
  List2 = List2.slice();
  var count = 0;
  var outputList = [];

  while (List1.length > 0 && List2.length > 0) {
    outputList.push(Math.min(List1[0], List2[0]));
    if (List2[0] < List1[0]) {
      count += List1.length;
      List2.shift();
    } else {
      List1.shift();
    }
  }
  outputList = outputList.concat(List1.concat(List2));
  return {
    'count': count,
    'list': outputList
  };
};

/*
count inversion algorithm
@param List the sequence to be sorted
*/
sortAndCount = function(List) {
  List = List.slice();
  var List1, List2, mergeOut, output1, output2;
  if (List.length < 2) {
    return {
      'count': 0,
      'list': List
    };
  } else {
    List1 = List.splice(0, Math.floor(List.length / 2));
    List2 = List;
    output1 = sortAndCount(List1);
    output2 = sortAndCount(List2);
    mergeOut = mergeAndCount(output1.list, output2.list);    
    return {
      'count': output1.count + output2.count + mergeOut.count,
      'list': mergeOut.list
    };
  }
};

console.clear();
var r = sortAndCount([1,3,4,2]);
console.log('RESULT',r.list);

演示： http: //jsbin.com/Ug ​​UYocu/2/edit

于 2013-11-19T16:23:29.633 回答
2

正如所指出的，问题是||而不是&&. 这是一个似乎可行的实现（为了让事情变得有趣，它返回一个反转列表而不是简单地计算它们）：

sort_and_count = function(L) {
    if (L.length < 2)
        return [[], L];
    var m = L.length >> 1;
    var na = sort_and_count(L.slice(0, m));
    var nb = sort_and_count(L.slice(m));
    var nc = merge_and_count(na[1], nb[1]);
    return [[].concat(na[0], nb[0], nc[0]), nc[1]];
}

merge_and_count = function(a, b) {
    var inv = [], c = [];

    while(a.length && b.length) {
        if(b[0] < a[0]) {
            a.forEach(function(x) { inv.push([x, b[0]])});
            c.push(b.shift());
        } else {
            c.push(a.shift());
        }
    }
    return [inv, c.concat(a, b)];
}

nn = sort_and_count([2, 4, 1, 3, 5])
// [[[2,1],[4,1],[4,3]],[1,2,3,4,5]]

为了完整起见，这里是二次算法：

inversions = function(L) {
    return L.reduce(function(lst, a, n, self) {
        return self.slice(n).filter(function(b) {
            return b < a;
        }).map(function(b) {
            return [a, b];
        }).concat(lst);
    }, []);
}

inversions([2, 4, 1, 3, 5])
// [[4,1],[4,3],[2,1]]
于 2013-11-19T16:45:43.137 回答