手写堆排序

问题

手写实现堆排序算法。

解答

堆排序利用堆这种数据结构进行排序。堆是一个近似完全二叉树的结构，满足子节点的值总是小于（或大于）父节点。

算法步骤

1. 将待排序数组构建成大顶堆（初始无序区）
2. 将堆顶元素与最后一个元素交换，得到新的无序区和有序区
3. 对新的堆顶进行调整，使无序区重新满足堆的性质
4. 重复步骤 2-3，直到无序区只剩一个元素

代码实现

// 堆排序
function heapSort(array) {
    if (!Array.isArray(array)) return;
    
    const len = array.length;
    
    // 构建大顶堆（从最后一个非叶子节点开始）
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(array, i, len);
    }
    
    // 排序：将堆顶与末尾元素交换，然后重新调整堆
    for (let i = len - 1; i > 0; i--) {
        [array[0], array[i]] = [array[i], array[0]];
        heapify(array, 0, i);
    }
    
    return array;
}

// 调整堆
function heapify(array, index, heapSize) {
    let largest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    
    if (left < heapSize && array[left] > array[largest]) {
        largest = left;
    }
    
    if (right < heapSize && array[right] > array[largest]) {
        largest = right;
    }
    
    if (largest !== index) {
        [array[index], array[largest]] = [array[largest], array[index]];
        heapify(array, largest, heapSize);
    }
}

// 测试
const arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log(heapSort(arr)); // [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]

关键点

• 堆排序分两步：构建堆和排序，构建堆从最后一个非叶子节点开始（Math.floor(len / 2) - 1）
• heapify 函数用于调整堆，确保父节点大于子节点（大顶堆）
• 时间复杂度稳定在 O(nlogn)，不受数据分布影响
• 空间复杂度 O(1)，原地排序
• 不稳定排序算法