使用合并排序算法的反演计算的JavaScript实现 [英] Javascript implementation of the inversion-counting with merge-sort algorithm
问题描述
我想在JavaScript中使用合并排序算法实现反向计数。我发现说明和伪代码 on此网站。
我的实现看起来像这样：
var mergeAndCount，sortAndCount;
/ *
合并例程
@param List1要合并的第一个列表
@param List2要合并的第二个列表
* /
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
};
};
/ *
计数反演算法
@param列出要排序的序列
* /
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]，但不适用于其他。
错误1：无限循环
当它开始与未定义的数字进行比较时，会持续很长时间。如果 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：操作数组
更改数组，然后使用您期望的初始值。在每个函数的开始，你应该复制数组（使用slice是最快的方式）。
错误3：忽略sortAndCount的输出 / p>
替换：
mergeOut = mergeAndCount（List1，List2）;
有：
code> mergeOut = mergeAndCount（output1.list，output2.list）;
正确的解决方案：
var mergeAndCount，sortAndCount;
/ *
合并例程
@param List1要合并的第一个列表
@param List2要合并的第二个列表
* /
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
};
};
/ *
计数反演算法
@param列出要排序的序列
* /
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）;
DEMO： http://jsbin.com/UgUYocu/2/edit
i am trying to implement the inversion-counting using merge sort algorithm in javascript. I found description and pseudo-code on this site. My implementation looks like this:
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
};
}
};
I wanted to test it on Jsfiddle here, but it crashes (too much memory used). Somehow it works for the inupt [1, 3, 2] but not for other. I am not sure what is going wrong, if my implementation or the original pseudocode is false.
Error 1 : infinite loop
The while goes on for a very long time when it starts to compare numbers with undefined. If List1.length is 0, the comparison List2[0] < List1[0] will always be false, resulting in List1.shift() which changes nothing.
Replace:
while (List1.length > 0 || List2.length > 0) {
With:
while (List1.length > 0 && List2.length > 0) {
Error 2 : manipulating arrays
You alter the arrays and then use what you expect to be their initial values. At the begining of each function you should copy the arrays (using slice is the fastest way).
Error 3 : ignoring output of sortAndCount
Replace:
mergeOut = mergeAndCount(List1, List2);
With:
mergeOut = mergeAndCount(output1.list, output2.list);
Correct solution:
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);
DEMO: http://jsbin.com/UgUYocu/2/edit
这篇关于使用合并排序算法的反演计算的JavaScript实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
