PTA-7-4 堆排序

代码如下:

#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);
	}
}