大根堆排序c语言算法演示
时间: 2024-09-26 08:01:03 浏览: 16
大根堆排序是一种基于比较的排序算法,它利用了大顶堆的数据结构特性来进行操作。大顶堆是一个完全二叉树,每个节点都大于或等于其子节点的值(对于最大堆)。下面是大根堆排序的基本步骤:
1. **建立大根堆**:
- 首先将待排序数组构建成一个大根堆。从最后一个非叶子节点开始,自底向上调整堆,保证每个节点都是最大的。
2. **交换并调整堆顶元素**:
- 将堆顶的最大元素(即当前未排序序列中的最大值)与最后一个元素交换位置。
- 移除最后一个元素,然后将新的堆顶(原最后一个元素)下沉到满足大根堆性质的位置。
3. **重复**:
- 对剩余的n-1个元素再次构建大根堆。
- 又将堆顶元素与倒数第二个元素交换,并下沉堆顶,直到整个序列有序。
以下是简单的C语言伪代码演示:
```c
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);
}
}
```