数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学使用堆排序算法对10个元素的数组进行排序的C++程序
堆排序基于二叉堆数据结构。在二叉堆中，对于最大堆，父节点的子节点小于或等于父节点；对于最小堆，父节点的子节点大于或等于父节点。
以下是一个解释堆排序所有步骤的例子。
排序前包含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<<"Given array is: "<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
}输出
Given array is: 20 7 1 54 10 15 90 23 77 25 Sorted array is: 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<<"Given array is: "<<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]<<" ";
更新于：2020年2月12日
2K+ 次浏览
广告