堆排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。
我们可以很容易的定义堆排序的过程：
1. 由输入的无序数组构造一个最大堆，作为初始的无序区
2. 把堆顶元素（最大值）和堆尾元素互换
3. 把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
4. 重复步骤2，直到堆的尺寸为1
#include <stdio.h> // 交换函数 void swap (int a[], int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } // 打印数组 void printA (int *a, int len) { int i; for (i = 0; i < len; i++) { printf ("M", a[i]); } printf ("\n"); } // a 代表一个数组 // i 代表要调整的结点的下标 // len 数组的长度 void heapify(int *a, int i, int len) { int left = 2 * i + 1; // 左孩子结点下标 int right = 2 * i + 2; // 右孩子结点下标 int max = i; // 三个节点中最大元素的下标 if (left < len && a[left] > a[max]) max = left; if (right < len && a[right] > a[max]) max = right; if (max != i) // 当前父节点不是所有结点中最大的元素，需要做调整 { swap (a, i, max); heapify (a, max, len); // 调整被交换的结点 } } void heapSort (int *a, int len) { // 建堆 int i; for (i = len/2 - 1; i >= 0; i--) { heapify (a, i, len); } // 排序 for (i = len-1; i > 0; i--) { swap (a, 0, i); // 拿堆顶元素与队尾元素进行交换 len--; // 找到一个最大元素以后堆大小减1 heapify (a, 0, len); // 调整堆顶元素 } } int main() { int a[10] = {9,6,8,0,3,5,2,4,7,1}; int len = sizeof(a) / sizeof(a[0]); heapSort(a, len); printA (a, len); return 0; }
