文章来源：https://www.toymoban.com/news/detail-791483.html
代码如下:文章来源地址https://www.toymoban.com/news/detail-791483.html
#include<iostream>
using namespace std;
void change(int arr[], int n, int i);
int main()
{
int n,i,end,arr[1000];
cin >> n;
for (i = 0; i < n; i++)
{
cin >> arr[i];
}
//进行一次排序,把最大值放到顶端
for (i = n/2-1; i >= 0; i--)
{
change(arr, n, i);
}
for (i = 0; i < n; i++)
{
cout << arr[i]<<' ';
}
cout << endl;
end = n - 1;
while (end > 0)
{
//交换首尾的值
int m;
m = arr[0];
arr[0] = arr[end];
arr[end] = m;
//进行一次排序,将(除上一次找出的)最大值放到顶端
change(arr, end, 0);
//遍历元素减一
end--;
for (i = 0; i < n; i++)
{
cout << arr[i]<<' ';
}
cout << endl;
}
return 0;
}
void change(int arr[], int n, int i)
{
//max记录主干的下标,left,right记录树叶的下标
int max = i, left = i * 2 + 1, right = i * 2 + 2;
//如果树叶下标在数组范围内并且比主干大,将max更新为最大的树叶下标
if (right < n && arr[right] > arr[max])
max = right;
if (left < n && arr[left] > arr[max])
max = left;
//如果max与主干下标i的值不相等,交换,并且以被交换的树叶为新的主干,向下检查,保证每个主干的值大于树叶
if (max != i)
{
int m;
m = arr[i];
arr[i] = arr[max];
arr[max] = m;
change(arr, n, max);
}
}到了这里，关于PTA-7-4 堆排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
