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

因为它是一种 inplace 排序算法，所以您实际上不必 return 数组。调用者已经传递了数组，所以他们真的不需要再次引用相同的数组。然后，您可以使用 return 值作为交换次数。

旁注：您的 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);

如果你想同时计算比较和交换，那么你需要 return 和 object/array 这对。在这种情况下，将该对象作为可选参数传递给 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);

JavaScript, HeapSort - 计数交换和比较

JavaScript, HeapSort - count swaps and comparisons

javascript

algorithm

sorting

counter

heapsort