用c语言写一个堆排序代码
时间: 2023-08-31 09:23:09 浏览: 70
### 回答1:
#include<stdio.h>
int main()
{
int n, temp;
printf("输入数组大小: ");
scanf("%d", &n);
int arr[n];
printf("输入 %d 个数: \n", n);
for(int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
// 堆排序
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
// 将根节点和最后一个节点交换
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新 heapify 根节点
heapify(arr, i, 0);
}
// 打印排序结果
printf("排序结果: \n");
for (int i=0; i<n; ++i)
printf("%d ",arr[i]);
return 0;
} // 堆排序算法
void heapify(int arr[], int n, int i)
{
int largest = i; // 初始化最大值为根
int l = 2*i + 1; // 左子节点
int r = 2*i + 2; // 右子节点
// 如果左子节点大于根
if (l < n && arr[l] > arr[largest])
largest = l;
// 如果右子节点大于最大值
if (r < n && arr[r] > arr[largest])
largest = r;
// 如果最大值不是根节点
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调用调整子节点
heapify(arr, n, largest);
}
}
### 回答2:
堆排序是一种基于二叉堆的排序算法,使用数组来实现堆的操作。下面是一个用C语言实现堆排序的代码:
```c
#include <stdio.h>
// 交换两个元素的位置
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 调整堆使其满足堆的性质
void 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]);
heapify(arr, n, largest);
}
}
// 堆排序函数
void heapSort(int arr[], int n) {
// 构建最大堆,自底向上调整堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 依次将最大值放到数组末尾,并调整堆
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
// 打印数组
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组:");
printArray(arr, n);
heapSort(arr, n);
printf("排序结果:");
printArray(arr, n);
return 0;
}
```
这个代码实现了使用堆排序算法对一个整型数组进行排序。首先,使用`heapify`函数将数组转换为最大堆;然后,利用`heapSort`函数将最大值逐个放到数组末尾并调整堆,最终得到排序结果。运行该程序,输出结果为:
```
原始数组:12 11 13 5 6 7
排序结果:5 6 7 11 12 13
```
这就是堆排序的实现代码。
### 回答3:
下面是使用C语言编写的堆排序代码:
```c
#include <stdio.h>
// 调整堆,使其成为最大堆
void maxHeapify(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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// 继续向下调整交换后的节点
maxHeapify(arr, n, largest);
}
}
// 堆排序函数
void heapSort(int arr[], int n) {
// 构建最大堆,从最后一个非叶子节点向上调整
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
// 依次取出最大元素并调整堆
for (int i = n - 1; i > 0; i--) {
// 将根节点(最大元素)与最后一个元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆,使其重新成为最大堆
maxHeapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
heapSort(arr, n);
printf("排序后的数组:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
该代码实现了堆排序的功能。其中,`maxHeapify`函数用于调整堆,使其成为最大堆;`heapSort`函数用于对数组进行堆排序。在`main`函数中,我们传入一个数组,并对其进行堆排序操作。最终输出排序后的数组。