JavaScript，HeapSort -计数互换和比较
JavaScript，HeapSort -计数互换和比较
提问于 2021-09-06 22:18:37
我应该如何计算掉期和比较？，我是编程和算法方面的新手。所以，我有一个问题要计算掉期和比较，问题是我不知道如何在递归函数中保存计数器的值--有代码解释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
}回答 1
Stack Overflow用户
回答已采纳
发布于 2021-09-07 10:14:37
因为它是一个内部排序算法，所以不必真正返回数组。调用者已经传递了数组，因此他们不需要再次使用相同的数组引用。然后，您可以使用掉期数量的返回值。
附带注意：heapify函数中有一个错误:递归调用应该将largest作为最后一个参数，而不是i。我还更正了以下内容：
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);
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/69080732
复制相关文章
相似问题
腾讯云开发者
