C++ 程序使用堆排序算法对包含 10 个元素的数组进行排序
c++programmingserver side programming
堆排序基于二叉堆数据结构。在二叉堆中，最大堆的情况下，父节点的子节点小于或等于父节点；最小堆的情况下，父节点的子节点大于或等于父节点。
下面是一个解释堆排序所有步骤的示例。
排序前包含 10 个元素的原始数组为 −
| 20 | 7 | 1 | 54 | 10 | 15 | 90 | 23 | 77 | 25 |
此数组使用 max-heapify 构建到二进制最大堆中。这个最大堆用数组表示如下。
| 90 | 77 | 20 | 54 | 25 | 15 | 1 | 23 | 7 | 10 |
提取最大堆的根元素并放置在数组的末尾。然后调用 max heapify 将其余元素转换为最大堆。如此反复，直到最终获得排序后的数组，如下所示 −
| 1 | 7 | 10 | 15 | 20 | 23 | 25 | 54 | 77 | 90 |
对一个使用堆排序算法得到的包含 10 个元素的数组如下所示。
示例
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int temp;
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) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int temp;
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(arr, i, 0);
}
}
int main() {
int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
int n = 10;
i nt i;
cout<<"给定数组为:"<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\n排序后的数组为: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
}
输出
给定数组为: 20 7 1 54 10 15 90 23 77 25 排序后的数组为: 1 7 10 15 20 23 25 54 77 90
在上面的程序中，函数 heapify() 用于将元素转换为堆。此函数是一个递归函数，它从调用它的元素(即本例中的 i)开始创建一个最大堆。演示此操作的代码片段如下。
void heapify(int arr[], int n, int i) {
int temp;
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) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
函数 heapSort() 使用堆排序对数组元素进行排序。它从非叶节点开始，并在每个节点上调用 heapify()。这会将数组转换为二进制最大堆。如下所示 −
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
此后，函数 heapSort() 在 for 循环的每次迭代中获取根元素并将其放在数组的末尾。然后调用 heapify() 以确保其余元素是最大堆。最终，使用此方法将所有元素从最大堆中取出，并获得排序数组。如下所示。
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
在函数 main() 中，首先显示数组。然后，调用函数 heapSort() 对数组进行排序。以下代码片段给出了该示例。
cout<<"给定数组是:"<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<&" & ";; cout<<endl; heapSort(arr, n);
最后，显示排序后的数组。如下所示。
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
