C语言实现堆排序算法(含源码)

C语言实现堆排序算法(含源码)

堆排序是一种高效稳定的排序算法，它利用二叉堆数据结构实现，时间复杂度为O(nlogn)。在本文中，我们将介绍如何使用C语言实现堆排序算法，同时提供完整的源代码和相应的描述。

1. 算法原理

堆排序分为两个步骤：建立最大堆和堆排序。其中最大堆是一种完全二叉树，满足根节点的值大于其左右子节点的值。堆排序过程如下：

• 首先构建一个最大堆。
• 将堆顶元素与末尾元素交换（此时最大元素就在数组的末尾了）。
• 对剩下的n-1个元素重新构建最大堆。
• 重复第二、三步骤，直到整个数组排序完成。

2. C语言实现

下面给出完整的C语言代码实现：

#include <stdio.h>

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

// 构建最大堆
void buildMaxHeap(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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22