用Javascript实现了带有合并排序算法的反转计数

Javascript implementation of the inversion-counting with merge-sort algorithm

本文关键字：算法 排序 合并 实现 Javascript      更新时间：2023-09-26

我正在尝试使用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
    };
  }
};

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

错误1：无限循环

当它开始比较未定义的数字时，while会持续很长一段时间。如果List1.length为0，则比较List2[0] < List1[0]将始终为假，从而导致List1.shift()什么都不改变。

替换：

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/UgUYocu/2/edit

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

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]]
相关文章：