选择排序（堆排序~大根堆~升序——C++实现）

选择排序（堆排序~大根堆~升序——C++实现）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma warning(disable:4996)
using namespace std;

//建堆：
//编号<=n/2的所有节点依次“下坠”调整（自底向上处理各分支节点）
//调整规则：小元素逐层“下坠”（与关键字更大的孩子交换）
//排序：
//将堆顶元素加入有序子序列（堆顶元素与堆底元素交换）
//堆底元素换到堆顶后，需要进行“下坠”调整，恢复“大根堆”的特性
//上述过程重复n-1趟

//堆排序（大根堆）升序
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len)
{
	A[0] = A[k];//A[0]暂存子树的根节点
	for (int i = 2 * k; i <= len; i *= 2) {//沿key较大的子节点向下筛选
		if (i < len && A[i] < A[i + 1]) {
			i++;//取key较大的子节点的下标
		}
		if (A[0] >= A[i])break;//筛选结束
		else {
			A[k] = A[i];//将A[i]调整到双亲结点上
			k = i;//修改k值，以便继续向下筛选
		}
	}
	A[k] = A[0];//被筛选节点的值放入最终位置
}
//建立大根堆
void BuildMaxHeap(int A[], int len) 
{	//数组是从A[1]开始存储的
	for (int i = len / 2; i > 0; i--) {//从后往前调整所有非终端节点
		HeadAdjust(A, i, len);
	}
}
//堆排序的完整逻辑
void HeapSort(int A[], int len)
{
	BuildMaxHeap(A, len);//初始建堆
	for (int i = len; i > 1; i--) {//n-1趟的交换和建堆过程
		swap(A[i], A[1]);//堆顶元素和堆底元素交换
		HeadAdjust(A, 1, i - 1);//把剩余的待排序元素整理成堆
	}
}

int main()
{
	printf("输入数组元素个数：");
	int n;
	scanf("%d", &n);
	printf("输入数组元素：");
	int nums[1000];
	int num;
	for (int i = 1; i <= n; i++) {//A[0]不放元素
		scanf("%d", &num);
		nums[i] = num;
	}
	//堆排序（大根堆）升序
	HeapSort(nums, n);
	//排序后结果
	printf("排序后结果为：");
	for (int i = 1; i <= n; i++) {
		printf("%d ", nums[i]);
	}

	printf("n");
	system("pause");
	return 0;
}