堆排序算法详解与C语言实现

### 简介
堆排序是一种基于选择排序思想的高效排序算法，它利用了堆这种特殊的数据结构来优化查找最大或最小元素的过程。堆排序的时间复杂度为O(n log n)，在实际应用中表现出色。

#### 工作原理
堆排序的核心在于将待排序数组构建成一个最大堆（或最小堆），然后通过不断交换堆顶元素和堆尾元素，并重新调整堆结构，逐步完成排序过程。具体步骤如下：

1. **构建初始堆**：将待排序的元素依次存入数组中，该数组可以看作一棵完全二叉树。从最后一个非叶节点开始，逐层向上调整，使每个子树都成为最大堆，最终整个二叉树成为最大堆。
2. **交换并调整堆**：将堆顶元素（即当前最大值）与堆底元素交换，然后将新的堆顶元素下沉调整，使其再次成为最大堆。重复此过程，直到所有元素都被排序。

#### 核心函数
堆排序主要依赖两个核心函数：`HeapAdjust` 和 `HeapSort`。

```c
void HeapAdjust(int H[], int start, int end) {
// 将start到end之间的元素调整为最大堆
int temp = H[start];
int parent = start, child;
while (2 * parent <= end) {
child = 2 * parent;
if (child != end && H[child] ++child;
if (temp > H[child])
break;
else {
H[parent] = H[child];
parent = child;
}
}
H[parent] = temp;
}

void HeapSort(int H[], int L, int R) {
// 调整整个二叉树为最大堆
for (int i = (R - L + 1) / 2; i >= L; --i)
HeapAdjust(H, i, R);
// 逐步将堆顶元素移至堆底
for (int i = R; i >= L; --i) {
swap(&H[L], &H[i]);
HeapAdjust(H, L, i - 1);
}
}
```

#### 测试样例
以下是一个完整的测试样例，展示了如何使用上述函数进行堆排序。

```c
#include

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

void HeapAdjust(int H[], int start, int end) {
int temp = H[start];
int parent = start, child;
while (2 * parent <= end) {
child = 2 * parent;
if (child != end && H[child] ++child;
if (temp > H[child])
break;
else {
H[parent] = H[child];
parent = child;
}
}
H[parent] = temp;
}

void HeapSort(int H[], int L, int R) {
for (int i = (R - L + 1) / 2; i >= L; --i)
HeapAdjust(H, i, R);
for (int i = R; i >= L; --i) {
swap(&H[L], &H[i]);
HeapAdjust(H, L, i - 1);
}
}

int main() {
int A[] = {0, 1, 3, 63, 5, 78, 9, 12, 52, 8};
printf("Previous Array: ");
for (int i = 1; i <= 9; ++i)
printf("%d ", A[i]);
HeapSort(A, 1, 9);
printf("\nSorted Array: ");
for (int i = 1; i <= 9; ++i)
printf("%d ", A[i]);
printf("\n");
return 0;
}
```

#### 运行结果
运行上述代码后，输出结果如下：

```
Previous Array: 1 3 63 5 78 9 12 52 8
Sorted Array: 1 3 5 8 9 12 52 63 78
```

### 总结
堆排序通过巧妙地利用堆数据结构，实现了高效的排序算法。本文不仅详细介绍了堆排序的原理和步骤，还提供了完整的C语言代码实现，帮助读者更好地理解和掌握这一经典算法。