算法的运行时间——哈克插入排序问题

Question

任务是输出对数组进行排序所需的移位数。我的代码：

function runningTime(arr) {
var count=0;
var temp;
for(var i=1 ; i<arr.length; i++){
for(var j=0 ; j<i; j++){
if(arr[j]>arr[i]){
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
count++;
}
}
}
return count;
}
console.log(runningTime([4, 4, 3, 4]));

它没有通过这个抽样测试：4 4 3 4。预期产量为2，矿井返回1，为什么它应该返回2？我哪里错了？

这是问题的链接：插入排序破解问题

Answer 1

您的代码不是插入排序。插入排序的想法是尝试搜索j，它是在i之前的最后一个位置，并且不小于i，然后交换它们。每一个大于i的值都是一次移位。试试这个。

function runningTime(arr) {
var count = 0;
var temp;
for (var i = 0; i < arr.length; i++) {
let pos = i;
for (var j = i; j >= 0; j--) {
if (arr[j] > arr[i]) {
pos = j;
count++;
}
}
var temp = arr[pos];
arr[pos] = arr[i];
arr[i] = temp;
}
return count;
}