排序算法---堆排序

原创不易，转载请注明出处。欢迎点赞收藏~

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法。它将待排序的元素构建成一个最大堆（或最小堆），然后逐步将堆顶元素与堆的最后一个元素交换位置，并重新调整堆，使得剩余未排序部分继续满足堆的性质。通过不断重复这个过程，最终将得到一个有序的序列。

具体步骤如下：
1. 构建初始堆：首先将待排序序列看作是完全二叉树，从最后一个非叶子节点开始，逐个向上调整节点，使得以每个节点为根的子树都满足堆的性质。
2. 排序：将堆顶元素与待排序序列的最后一个元素交换位置，然后将剩下的 n-1 个元素重新调整为堆。重复这个过程，直到堆中只剩下一个元素，即完成排序。

堆排序的关键操作是堆的调整，有两种方式可以实现：
1. 自顶向下调整（Down-Heapify）：从根节点开始，不断将根节点与其左右子节点中较大（或较小）的交换，直到满足堆的性质。
2. 自底向上调整（Up-Heapify）：从最后一个非叶子节点开始往上逐个调整，将每个节点与其左右子节点中较大（或较小）的交换，直到满足堆的性质。

堆排序的时间复杂度为O(nlogn)，其中n是待排序元素的个数。堆的构建过程需要O(n)的时间，每次调整堆的操作需要O(logn)的时间，共需要进行n-1次调整。所以总体时间复杂度是O(nlogn)。

堆排序的空间复杂度为O(1)，它是一种原地排序算法，不需要额外的存储空间。

堆排序具有以下特点：

稳定性：堆排序是一种不稳定的排序算法，即相同元素的相对位置可能会发生改变。
适应性：堆排序适用于大规模数据的排序，因为它的时间复杂度不会随数据规模增大而增加，且不需要额外的存储空间。
不适应性：堆排序不适用于小规模数据的排序，因为它的常数因子较大，且堆的构建过程需要较多的比较和交换操作。

需要注意的是，堆排序对于相同元素的排序可能会打乱它们的原始相对顺序，这是由于堆本身的性质所决定的。如果要保持相同元素的相对顺序不变，可以采用稳定的排序算法来代替堆排序。

以下是一个使用C语言实现堆排序的示例代码：

#include <stdio.h>

// 交换两个元素的值
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整最大堆，使根节点为最大值
void max_heapify(int arr[], int n, int i)
{
    int largest = i;       // 初始化最大值为根节点
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

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

    // 如果右子节点大于当前最大值，更新最大值为右子节点
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点，则交换根节点和最大值
    if (largest != i)
    {
        swap(&arr[i], &arr[largest]);

        // 递归调整交换后的子树
        max_heapify(arr, n, largest);
    }
}

// 堆排序函数
void heap_sort(int arr[], int n)
{
    // 构建最大堆（初始状态）
    for (int i = n / 2 - 1; i >= 0; i--)
        max_heapify(arr, n, i);

    // 逐个将堆顶元素移至末尾，并重新调整堆
    for (int i = n - 1; i > 0; i--)
    {
        // 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换
        swap(&arr[0], &arr[i]);

        // 对剩余元素进行调整，使其满足最大堆性质
        max_heapify(arr, i, 0);
    }
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    heap_sort(arr, n);

    printf("\n排序后的数组: \n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    putchar('\n');

    return 0;
}

这个示例中实现了堆排序算法。代码首先定义了两个辅助函数：swap用于交换两个元素的值，max_heapify用于调整最大堆。

max_heapify函数接收一个数组、堆的大小n和要调整的节点索引i作为参数。该函数首先将最大值初始化为当前节点（根节点），然后比较左子节点和右子节点的值，更新最大值。如果最大值不是根节点，则将其与根节点交换，并递归调用max_heapify来保持堆的性质。

heap_sort函数首先构建最大堆（通过循环调用max_heapify），然后逐个将堆顶元素（最大值）移动到未排序部分的末尾，并重新调整堆。在每次迭代中，通过swap操作将最大值放在数组的末尾，并对剩余元素进行调整，使其满足最大堆的性质。

最后，main函数创建一个包含一些无序元素的数组，并调用heap_sort函数对数组进行排序。排序后，打印出排序后的数组。

请注意，这只是一个简单的堆排序示例，实际应用中可能需要考虑更多的边界情况和错误处理。

运行如上代码，你可以看到以下输出：