十大排序——堆排序
今天要讲到的呢是十大排序中的堆排序，在介绍堆排序算法之前呢，我们得先知道堆是什么？
堆是一种非常灵活的数据结构，我们可以通过堆来解决一些问题，从它的本质上来说，堆就是二叉树的数据结构，这一点从图1-1可以明显看出
图1-1
堆排序算法中还分成大顶堆和小顶堆两种方法（图1-2所示）：
图1-2
大顶堆：每个节点的值都大于或者等于其子节点的值，可理解为堆排序中的升序排序。
小顶堆：每个节点的值都小于或者等于其子节点的值，可理解为堆排序中的降序排序。
在大概了解了堆之后，我们再来看一看实现堆排序的基本思想：
堆一般存储于数组中，从头到尾按顺序扫描数组中的数，找到最小关键字或者最大关键字（按升序或降序进行选择，这里为升序排序只需找到最小关键字即可），找到最小关键字和数组中第一个数字进行交换，然后继续从无序序列中找到最小的关键字插入有序序列，每一次的排序都能找到最小的关键字，直到排序结束
详细步骤：
假设我们给出一个待排序数组A{20,12,15,17,9,8,16,10,22,6,11,7}；
一：根据无序数组创建一个堆（升序采用大顶堆，降序采用小顶堆），我们现在的堆就是一个无规则的二叉树，将序列的值从上到下，从左到右的顺序依次对二叉树进行填充（如图1-1所示）
图1-1
二：接下来对堆进行调整，使其变成大顶堆，根据大顶堆的性质，每个节点的值都大于或者等于其子节点的值，所以要对节点和子节点进行比较，从而调整他们的父子关系，如果二叉树从上往下遍历比较的话，会存在节点进行交换，而他的子节点还没遍历到，比较的次数和交换的次数会增加，从而效率更低，所以我们选择从下往上进行遍历，一层一层依次进行，先遍历第一遍会发现17 < 22,需要调整他们的父子关系（如图1-2所示）
图1-2
9 < 11，需要调整他们的父子关系（如1-3所示）
图1-3
按照以上方法，最终调整堆为大顶堆，最上层节点数大于他的子节点（如图1-4所示）
图1-4
用数组进行存储，现在就可以得到一个大顶堆的存储结构（如图1-5所示）
图1-5
三：用堆排序进行排序
根据大顶堆的性质，当前堆的顶堆就是整个序列中最大的值，找到最大关键字（或最小关键字），把最大关键字和数组最后一个元素交换，把剩下的序列重新构造成最大堆（或最小堆），一直重复此操作，最后就能得到一个有序的数组。
具体步骤：
我们目前得到的大顶堆如图1-6所示：
图1-6
根据大顶堆的性质，当前堆的顶堆就是最大关键数，我们把最大关键数和序列最后一个数进行交换（如图1-7所示）
图1-7
交换完成之后，22这个数字为有序区，不用参与之后的比较，然后将剩余的元素重新构建大顶堆，其实就是调整根节点以及其调整后影响的子节点，因为其他节点之前已经满足大顶堆性质，第一轮排序结束如图1-8所示
图1-8
继续交换20与9 扩大有序区 ，剩下的序列再次重新构造大顶堆。
一直重复此操作，直到变成有序的序列（如图1-9所示）
图1-9
详细代码：
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
int temp = *b;
*b = *a;
*a = temp;
}
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 {
//否则交换父子内容再继续子节点和孙节点比较 s
wap(&arr[dad], &arr[son]);
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--)
{
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main()
{
int arr[] = { 20,12,15,17,9,8,16,10,22,6,11,7 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
