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