堆排序
堆排序
堆排序顾名思义，就是使用堆这种数据结构进行排序，什么是堆呢，堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆总是满足下列性质： 堆中某个结点的值总是不大于或不小于其父结点的值； 堆总是一棵完全二叉树。 将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
使用堆排序，第一步是将无序序列结构转变为一个大顶堆或者小顶堆，然后将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复，直到排列完成。
代码
void max_heapify(int arr[], int start, int end)
{
//获得父节点下标和子节点下标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子节点下标在范围内才做比较，子节点下标不能大于数组最大下标
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
return;
else //否则交换父子内容再继续子节点和孙节点比较
{
int temp = arr[son];
arr[son] = arr[dad];
arr[dad] = temp;
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len)
{
int i;
//初始化，i从最后一个父节点开始调整
for (i = len / 2 - 1; i >= 0; i--) {
max_heapify(arr, i, len - 1);
}
//先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
for (i = len - 1; i > 0; i--)
{
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 8,4,7,1,5,3,0,9 };
heap_sort(arr, 8);//数组和长度
return 0;
}分析代码
1.如何算出最后一个父节点（len/2-1为什么是最后一个父节点）。
观察在最左边的数，0，1，3，7，不难发现，后一个数等于前一个数*2+1
所以当父节点为n时，子节点应为2n+1 和2n+2两个。
设数组长度为n，最后一个非叶子节点为i。
分两种情况： ①只有左孩子，则n-1为左孩子节点下标，有n-1 = 2i + 1，得i = [(n-1)-1]/2 = n/2-1。
②有左孩子和右孩子，则n-2为左孩子节点下标，n-1为右孩子节点下标， 有 n-2 = 2i+1，得i = [(n-2)-1]/2 = (n-1)/2 -1。 有 n-1 = 2i+2，得i = [(n-1)-2]/2 = (n-1)/2 -1。
当数组长度为偶数时，符合第一种情况，父节点为n/2-1。 当数组长度为奇数时（这个奇数一定比第一种情况的偶数大），符合第二种情况，父节点为(n-1)/2 -1，但是由于强类型语言的特征，除不整，将向下取整，(n-1)/2 -1将等于n/2-1。
举个例子：
8/2-1 = 3 9/2-1 = 3
所以，图中的堆，最后一个父节点为3，之后的2，1，0，分别对应之后的父节点，下面的代码分别是遍历3，2，1，0四个父节点进行操作，转变为大顶堆或者小顶堆。
for (i = len / 2 - 1; i >= 0; i--) {
max_heapify(arr, i, len - 1);
}2.分析代码中max_heapify()函数找到父节点之后，如何找到交换元素
//拿图中所示的堆举例
//获得父节点下标和子节点下标，最后一个父节点是3
int dad = start; //3
int son = dad * 2 + 1; //7 只考虑左孩子，因为左孩子一定存在
while (son <= end) //若子节点下标在范围内才做比较，子节点下标不能大于数组最大下标
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//如果son + 1小于等于数组最大下标，说明有右孩子，且判断左右两个孩子大小，如果右孩子比左孩子大，则将子节点改为右孩子。
son++;
if (arr[dad] > arr[son]) //判断最大孩子和父节点的大小，如果父节点大，则返回
return;
else //否则交换父子内容，然后再继续比较
{
int temp = arr[son];
arr[son] = arr[dad];
arr[dad] = temp;
//再继续子节点和孙节点比较，直到son不满足<=end
dad = son;
son = dad * 2 + 1;
}
}