JavaScript实现HeapSort时如何统计递归函数中的交换与比较次数

你提供的原有heapify函数存在逻辑错误：递归调用时传入的索引参数应为largest而非i，否则无法完成堆的下沉调整，会导致排序失效，修改代码时会同步修复该问题。

计数实现思路 #

• 利用JavaScript引用类型的特性，将交换次数、比较次数存放在一个对象中，作为参数传递给heapify函数，所有递归调用修改的都是同一个对象的属性值，自动完成计数累计，不需要额外处理递归返回值的计数合并。
• 比较计数的统计节点：每次父子节点、兄弟节点间的大小比较操作执行时，计数+1
• 交换计数的统计节点：每次数组元素位置交换操作执行时，计数+1

修改后的完整代码 #

function heapify(arr, length, i, counters) {
    let largest = i
    let left = i * 2 + 1
    let right = left + 1

    if (left < length) {
        counters.compareCount++ // 左子节点和当前最大节点比较，计数+1
        if(arr[left] > arr[largest]) {
            largest = left
        }
    }

    if (right < length) {
        counters.compareCount++ // 右子节点和当前最大节点比较，计数+1
        if(arr[right] > arr[largest]) {
            largest = right
        }
    }

    if(largest != i) {
        counters.swapCount++ // heapify内部交换元素，计数+1
        [arr[i], arr[largest]] = [arr[largest], arr[i]]
        heapify(arr, length, largest, counters) // 修复原有参数错误，传入largest
    }
    return arr
}

function heapSort(arr) {
    // 初始化计数器，使用对象存储以支持引用传递
    const counters = {
        swapCount: 0,
        compareCount: 0
    }
    let length = arr.length
    let i = Math.floor(length / 2 - 1)
    let k = length - 1
    
    while (i >= 0) {
        heapify(arr, length, i, counters)
        i--
    }

    while (k >= 0) {
        counters.swapCount++ // 堆顶和未排序区间末尾元素交换，计数+1
        [arr[0], arr[k]] = [arr[k], arr[0]]
        heapify(arr, k, 0, counters)
        k--
    }

    // 同时返回排序后的数组和统计结果
    return {
        sortedArr: arr,
        swapCount: counters.swapCount,
        compareCount: counters.compareCount
    }
}

调用示例 #

// 测试用例
const result = heapSort([3,1,4,1,5,9,2,6])
console.log('排序后数组：', result.sortedArr)
console.log('总交换次数：', result.swapCount)
console.log('总比较次数：', result.compareCount)

内容的提问来源于stack exchange，提问作者Wordllban