用c++实现堆排序算法
时间: 2024-10-19 21:00:36 浏览: 7
堆排序是一种基于比较的、利用堆这种数据结构所设计的一种排序算法。它通过构建最大堆(大根堆)或最小堆(小根堆),然后将堆顶元素与最后一个元素交换,再对剩余的元素调整堆,直到整个序列有序。以下是C++实现堆排序的基本步骤:
1. **建立堆**:首先,从数组的最后一个非叶子节点开始,自下而上地调整每个节点,使其满足堆的性质(即父节点的值大于(小于)其所有子节点的值)。
```cpp
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);
}
}
```
2. **排序过程**:不断地将堆顶元素(当前未排序部分的最大或最小值)与末尾元素交换,并调整剩余元素为新的堆,直到堆只有一个元素,排序完成。
```cpp
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);
}
}
```
阅读全文