合并排序算法的反转计数的 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 上测试它，但它崩溃了(使用了太多内存)。不知何故，它适用于输入 [1, 3, 2]，但不适用于其他。如果我的实现或原始伪代码是错误的，我不确定出了什么问题。

Answer 1

错误1:无限循环

当 while 开始与未定义的数字进行比较时，会持续很长时间。如果List1.length为0时，比较List2[0] < List1[0]将始终为 false，导致 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