[数据结构与算法]堆排序的理解

堆排序的关键是对最大堆的理解（或最小堆）

最大堆形成动画

以下面数组为例

int arr[10] = { 1,23,4,5,67,563,3543,4234,66,44 };

首先我们要知道父节点n的两个字节点为2*n+1和2*n+2

在第一次得到最大堆之后

我们把a[0]与a[9]换值

可以的到a[9]是大小在数组里是第一大

所以之后我们只需要对a[0]至a[8]排序

再次形成最大堆

以此类推

下面是代码

#include <iostream>
#include <cstring>
#include<cstdio>
using namespace std;
//交换a和b的值
void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void max_sort(int arr[], int start, int end) {
	int dad = start;//父节点
	int son = dad * 2 + 1;//第一个子节点
	while (son <= end) {
		//选择两个子节点中较大的那一个节点
		if (arr[son] < arr[son+1]&&son+1<=end) {
			son++;
		}
		//如果父节点比子节点小 那么交换值 并且把原来的父节点与现在的字节点比较
		if (arr[dad] < arr[son]) {
			swap(&arr[dad], &arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
		else {
			return;
		}
	}
}
void heap_sort(int arr[], int len) {
	for (int i = len / 2 - 1; i >= 0; i--) {
		max_sort(arr, i, len - 1);
	}
	//得到最大堆
	for (int i = len - 1; i > 0; i--) {
		swap(&arr[0], &arr[i]);
		max_sort(arr, 0,i - 1);
	}
	//将数组arr[0]至arr[i]中最大的数arr[0]与最后的arr[i]换位置
	//再对数组arr[0]至arr[i-1]的元素进行堆排序
}
int main() {
	int arr[10] = { 1,23,4,5,67,563,3543,4234,66,44 };//用堆排序将数字由小到大排序
	int len = sizeof(arr)/sizeof(int);//计算数组的大小；
	heap_sort(arr, len);//堆排序函数 
	for (int i = 0; i < len; i++) {//输出结果
		printf("%d ", arr[i]);
	}
	return 0;
}