堆排序是一种高效的排序算法，通过构建最大堆或最小堆来实现排序。它的时间复杂度为O(nlogn)，适用于大规模数据的排序。

一、堆排序的原理

堆是一种特殊的完全二叉树，它有以下特点：

最大堆：任意节点的值都大于或等于其子节点的值。

最小堆：任意节点的值都小于或等于其子节点的值。

堆排序的基本思想是利用堆的性质，将待排序的序列构建成一个堆，然后每次从堆顶取出最大（或最小）的元素放到已排序的序列中，再将剩余元素重新构建成一个堆，循环执行这个过程，直到排序完成。

堆排序的具体步骤如下：

构建最大堆或最小堆：从最后一个非叶子节点开始，依次向上调整每个节点，使其满足堆的性质。

取出堆顶元素：将堆顶元素与最后一个元素交换，然后将堆的大小减1。

重新构建堆：对交换后的堆顶元素进行向下调整操作，使其满足堆的性质。

重复执行步骤2和步骤3，直到堆的大小为1。

二、堆排序的实现

堆排序的实现可以分为两个部分：堆的构建和堆的调整

堆的构建

堆的构建是将一个无序的序列构建成一个堆的过程。从最后一个非叶子节点开始，对每个节点进行向下调整操作，使其满足堆的性质。

以构建最大堆为例，具体实现步骤如下：

从最后一个非叶子节点开始，依次向上调整每个节点。

对于每个节点，比较其与左右子节点的大小，如果大于左右子节点的值，则不需要调整；否则，将该节点与左右子节点中较大的节点交换位置，并继续向下调整交换后的节点，直到满足堆的性质。

构造堆

在构造有序堆时，我们开始只需要扫描一半的元素（n/2-1 ~ 0）即可，因为(n/2-1)~0的节点才有子节点，n=8,(n/2-1) = 3  即3 2 1 0这个四个节点才有子节点

所以代码4~6行for循环的作用就是将3 2 1 0这四个节点从下到上，从右到左的与它自己的子节点比较并调整最终形成大顶堆，过程如下：

第一次for循环将节点3和它的子节点7 8的元素进行比较，最大者作为父节点（即元素60作为父节点）

第二次for循环将节点2和它的子节点5 6的元素进行比较，最大者为父节点（元素80作为父节点）

第三次for循环将节点1和它的子节点3 4的元素进行比较，最大者为父节点（元素70作为父节点）

第四次for循环将节点0和它的子节点1 2的元素进行比较，最大者为父节点（元素80作为父节点）

注意，元素20和元素80交换后,20所在的节点还有子节点，所以还要再和它的子节点5 6的元素进行比较，这就是28行代码 i = j 的原因

有序堆已构造好

调整堆

下面进行while循环

堆顶元素80和尾40交换后-->调整堆

堆顶元素70和尾30交换后-->调整堆

堆顶元素60尾元素20交换后-->调整堆

其他依次类推，最终已排好序的元素如下：

堆的调整是将堆顶元素与最后一个元素交换后，对堆顶元素进行向下调整操作的过程。

以调整最大堆为例，具体实现步骤如下：

将堆顶元素与最后一个元素交换位置。

对交换后的堆顶元素进行向下调整操作，与左右子节点中较大的节点交换位置，直到满足堆的性质。

动图演示

算法步骤

1. 创建一个堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。

代码实现

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
 int temp = *b;
 *b = *a;
 *a = temp;
}

void max_heapify(int arr[], int start, int end) {
 // 建立父節點指標和子節點指標
 int dad = start;
 int son = dad * 2 + 1;
 while (son <= end) { // 若子節點指標在範圍內才做比較
 if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
 if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
 return;
 else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(&arr[dad], &arr[son]);
 = son;
 = dad * 2 + 1;
 }
 }
}

void heap_sort(int arr[], int len) {
 int i;
 // 初始化，i從最後一個父節點開始調整
 for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
 // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
 for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
 }
}

int main() {
 int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
 int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
 int i;
 for (i = 0; i < len; i++)
 printf("%d ", arr[i]);
 printf("\n");
 return 0;
}

三、堆排序的优化

堆排序的性能主要受到两个因素的影响：构建堆的过程和调整堆的过程。

构建堆的优化：

构建堆的过程中，可以选择从最后一个非叶子节点开始，直接进行向下调整操作，而不是每个节点都向上调整。这样可以减少调整的次数，提高构建堆的效率。

调整堆的优化：

调整堆的过程中，可以使用堆的性质进行剪枝。即，在每次向下调整时，只与左右子节点中较大的节点进行比较交换，而不是与每个子节点都进行比较。这样可以减少比较和交换的次数，提高调整堆的效率。

同时，可以使用大顶堆和小顶堆相结合的方式进行排序。即，先构建一个大顶堆，然后将堆顶元素与最后一个元素交换，然后对交换后的堆顶元素进行向下调整操作得到小顶堆，再将堆顶元素与倒数第二个元素交换，重复执行这个过程，直到排序完成。这样可以减少每次调整堆的时间。

四、总结

堆排序是一种高效的排序算法，通过构建最大堆或最小堆来实现排序。它的时间复杂度为O(nlogn)，适用于大规模数据的排序。实现堆排序主要包括堆的构建和堆的调整两个过程，可以根据具体情况进行优化，提高排序的效率。同时，堆排序也可以与其他排序算法相结合，以达到更好的排序效果。

部分引用参考：https://www.runoob.com/