JavaScript，HeapSort - 计数交换和比较

Question

我应该如何计算掉期和比较？我是程序和算法的新手。所以，我在计算交换和比较时遇到了问题，问题是我不知道如何在递归函数中保存计数器的值 有代码说明 https://levelup.gitconnected.com/heapsort-for-javascript-newbies-598d25477d55

function heapify(arr, length, i) {
let largest = i
let left = i * 2 + 1
let right = left + 1
if (left < length) {
if(arr[left] > arr[largest]) {
largest = left
}
}
if (right < length) {
if(arr[right] > arr[largest]) {
largest = right
}
}
if(largest != i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]
heapify(arr, length, i)
}
return arr
}
function heapSort(arr) {
let length = arr.length
let i = Math.floor(length / 2 - 1)
let k = length - 1

while (i >= 0) {
heapify(arr, length, i)
i--
}
while (k >= 0) {
[arr[0], arr[k]] = [arr[k], arr[0]]
heapify(arr, k, 0)
k--
}
return arr
}

Answer 1

由于它是一种就地排序算法，因此您实际上不必返回数组。调用方已经传递了数组，因此它们实际上不需要再次使用相同的数组引用。然后，您可以改用交换次数的返回值。

旁注：您的heapify函数中存在一个错误：递归调用应作为最后一个参数而不是ilargest。我也在下面更正了：

function heapify(arr, length, i) {
let largest = i;
let left = i * 2 + 1;
let right = left + 1;
if (left < length) {
if(arr[left] > arr[largest]) {
largest = left;
}
}
if (right < length) {
if(arr[right] > arr[largest]) {
largest = right;
}
}
if(largest != i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]];
// count the above swap, and those made by the recursive calls
return 1 + heapify(arr, length, largest);
}
return 0; // Nothing was swapped here
}
function heapSort(arr) {
let length = arr.length;
let i = Math.floor(length / 2 - 1);
let k = length - 1;

let swapCount = 0; // running sum
while (i >= 0) {
swapCount += heapify(arr, length, i);
i--
}
while (k >= 0) {
[arr[0], arr[k]] = [arr[k], arr[0]];
// Count the above swap and those made by heapify:
swapCount += 1 + heapify(arr, k, 0);
k--;
}

return swapCount;
}
let arr = [4, 2, 9, 7, 1, 3, 8, 0, 5, 6];
let swapCount = heapSort(arr);
console.log("sorted:", ...arr);
console.log("swaps:", swapCount);

如果要同时计算比较和交换，则需要返回具有此对的对象/数组。在这种情况下，将该对象作为可选参数传递给heapify可能更容易，然后 这将调整该对象中的计数：

function heapify(arr, length, i, counter = { comparisons: 0, swaps: 0 }) {
let largest = i;
let left = i * 2 + 1;
let right = left + 1;
if (left < length) {
counter.comparisons++; // For the next `if` condition
if(arr[left] > arr[largest]) {
largest = left;
}
}
if (right < length) {
counter.comparisons++; // For the next `if` condition
if(arr[right] > arr[largest]) {
largest = right;
}
}
if(largest != i) {
counter.swaps++;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, length, largest, counter);
}
}
function heapSort(arr) {
let length = arr.length;
let i = Math.floor(length / 2 - 1);
let k = length - 1;

let counter = {
comparisons: 0, // running sum
swaps: 0 // running sum
}
while (i >= 0) {
heapify(arr, length, i, counter);
i--;
}
while (k >= 0) {
counter.swaps++;
[arr[0], arr[k]] = [arr[k], arr[0]];
heapify(arr, k, 0, counter);
k--;
}

return counter;
}
let arr = [4, 2, 9, 7, 1, 3, 8, 0, 5, 6];
let counter = heapSort(arr);
console.log("sorted:", ...arr);
console.log("counters:", counter);