合并排序算法的倒置计数的Javascript实现

Question

我正在尝试使用 javascript 中的合并排序算法实现倒置计数。我找到了描述和伪代码 on this site .我的实现如下所示:

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 here 上测试它，但它崩溃了(使用了太多内存)。它以某种方式适用于 inupt [1, 3, 2] 但不适用于其他。如果我的实现或原始伪代码是错误的，我不确定出了什么问题。

Answer 1

错误 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:操作数组

您更改数组，然后使用您期望的初始值。在每个函数的开头，您应该复制数组(使用切片是最快的方法)。

错误 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