什么是堆排序算法？详述堆排序算法的原理？用C语言实现堆排序算法。内附完整代码。

大家好，我是贤弟！本文简单一下堆排序算法。堆排序与冒泡排序一样都是最常用的算法之一。

一、什么是堆排序算法？

堆排序算法是一种基于二叉堆数据结构的排序算法。

它的主要思想是将待排序的元素构建成一个二叉堆，然后将堆顶元素与堆底元素交换，使得最大（或最小）元素排在堆底，然后重新调整堆，再将堆顶元素与堆底元素交换，如此往复，直到所有元素都排好序。

二、堆排序算法的原理

堆排序算法的原理如下：

1. 将待排序的元素构建成一个二叉堆（大根堆或小根堆），使得每个节点的值都大于（或小于）它的左右子节点的值。

2. 将堆顶元素与堆底元素交换，使得最大（或最小）元素排在堆底。

3. 调整堆，使得堆仍然满足二叉堆的性质。

4. 重复第2步和第3步，直到所有元素都排好序。

三、代码示例

下面是用C语言实现堆排序算法的代码：

```c#include #include

// 调整堆void adjustHeap(int arr[], int i, int n) { int j = 2 * i + 1; // 左子节点 int temp = arr[i]; // 当前节点 while (j < n) { if (j + 1 < n && arr[j] j++; } if (temp < arr[j]) { // 如果当前节点小于子节点 arr[i] = arr[j]; // 子节点上移 i = j; j = 2 * i + 1; } else { break; } } arr[i] = temp; // 当前节点下移}

// 堆排序void heapSort(int arr[], int n) { // 构建堆 for (int i = n / 2 - 1; i >= 0; i--) { adjustHeap(arr, i, n); } // 排序 for (int i = n - 1; i >= 1; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; adjustHeap(arr, 0, i); }}

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