十大经典排序算法及其C语言实现--带动图展示-七、堆排序（Heap sort）

利用堆这种数据结构进行排序，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

7.1、动画演示

7.2、代码

// 调整堆，将以root为根的子树调整为最大堆
void heapify(int arr[], int n, int root) {
    int largest = root; // 初始化根节点为最大值
    int left = 2 * root + 1; // 左子节点
    int right = 2 * root + 2; // 右子节点

    // 如果左子节点比根节点大，则更新最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比根节点大，则更新最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，则交换根节点和最大值节点，并递归调整子树
    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 依次取出堆顶元素，调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]); // 将当前堆顶元素（最大值）与数组末尾元素交换
        heapify(arr, i, 0); // 调整堆
    }
}

7.3、评价

堆排序不稳定，但是时间复杂度稳定，适用于大规模数据。

• 堆排序通常需要随机访问数组元素，对于链式结构来说不太适用，因此在链表实现中可能效率较低。

• 如果待排序的数据分布不均匀，堆排序的性能可能会下降，因为堆排序是一种基于比较的排序算法，而数据分布不均可能导致比较次数增多。

• 相对于其他简单的排序算法（如插入排序、冒泡排序），堆排序的实现相对复杂，需要对堆的概念和操作有一定的了解。