javascript-实现-堆排序

堆排序是一种基于完全二叉树的排序算法，它的时间复杂度为 O(nlogn)。下面是 JavaScript 实现堆排序的代码：

function heapSort(array) {
    // 构建大顶堆
    for (let i = Math.floor(array.length / 2) - 1; i >= 0; i--) {
        heapify(array, i, array.length);
    }

    // 交换堆顶和堆底元素，并重新构建大顶堆
    for (let i = array.length - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, 0, i);
    }

    return array;
}

function heapify(array, i, length) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    // 找出当前结点、左子节点、右子节点中最大的一个
    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    // 如果当前节点不是最大值，则交换当前节点和最大值，并继续向下构建大顶堆
    if (largest !== i) {
        swap(array, i, largest);
        heapify(array, largest, length);
    }
}

function swap(array, i, j) {
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

在这段代码中，我们首先构建了一个大顶堆，然后逐步将堆顶元素和堆底元素交换，并重新构建大顶堆，最终得到一个有序数组。heapify 函数用于构建大顶堆，它的作用是将当前结点和它的子节点中最大的一个交换位置，并继续向下构建大顶堆。swap 函数用于交换数组中的两个元素。