堆排序算法C++实现

#include
#include
using namespace std;

//要排序的数组
int A[] = { 12,1,3,46,5,0,-3,12,35,16 };
int len = sizeof(A) / sizeof(A[0]);//数组元素个数

//交换函数
void swap(int arr[], int a, int b) {
	int temp = A[a];
	A[a] = A[b];
	A[b] = temp;
}

//A:待排序数组 i:树根
void max_heapify(int A[], int i) {
	int l = i * 2 + 1;//左孩子下标（下标从0开始）
	int r = i * 2 + 2;//右孩子下标
	
	int largest = i;//保存较大值
	if (l < len && A[l] > A[i]) {
		largest = l;
	}
	if (r < len && A[r] > A[largest]) {
		largest = r;
	}
	if (largest != i) {
		swap(A,i,largest);//交换较大值与树根
		max_heapify(A, largest);//再处理改动过的下标的子树
	}
}

//建立大顶堆
void build_max_heap(int A[]) {
	for (int i = len / 2; i >= 0; i--) {
		max_heapify(A, i);
	}
}

//堆排序
void heapsort(int A[]) {
	build_max_heap(A);
	for (int i = len - 1; i > 0; i--) {
		swap(A,0,i);
		len--;
		max_heapify(A, 0);
	}
}

int main() {
	for (int i = 0; i < len; i++) {
		cout << A[i] << " ";
	}
	cout << endl;
	cout << len << endl;
	heapsort(A);
	int n = sizeof(A) / sizeof(A[0]);
	for (int i = 0; i < n; i++) {
		cout << A[i] << " ";
	}
	return 0;
}