堆排序是将给定的序列看成完全二叉树的顺序存储结构来进行排序。
在学习堆排序之前，先了解一下完全二叉树的一个性质：
给定一颗完全二叉树bt，采用顺序存储结构来进行存储，那么如何表示父结点与左右孩子结点之间的关系呢？
下面分两种情况：
(a).如果从下标为0的位置开始存储，那么对于下标为i的结点，其左孩子的下标为2i+1，右孩子的下标为2i+2，父结点的下标为(i-1)/2
(b).如果从下标为1的位置开始存储，那么对于下标为i的结点，其左孩子的下标为2i，右孩子的下标为2i+1，父结点的下标为i/2
为了满足我们从下标为0开始存储的习惯，这里采用第一种方式。由此，可以定义堆：给定一个序列K0、K1、...、Kn-1，如果满足Ki ≤ K2i+1且Ki ≤ K2i+2，
则称之为小根堆；如果满足Ki ≥ K2i+1且Ki ≥ K2i+2，则称之为大根堆。
上面所述为堆的基本概念和相关知识，现在我们讨论大根堆的排序。
对于一个大根堆而言，其根结点便是最大元素，选择出最大元素，将其与序列的最后一个元素进行交换，这样最大的元素便成功归位。但是此时堆的结构
遭到了破坏，需要重新调整元素的位置，使其再次满足堆的性质。所以，对于堆排序来说，堆的调整算法是其核心和本质。
堆的调整算法：
#include <stdio.h> #include <stdlib.h> void Adjustment(int A[], int s, int t) { int i, j, temp; i = s; j = 2*i+1; // j为左孩子的下标 temp = A[i]; // 辅助变量temp保存父结点的值 while(j <= t) { if(j < t && A[j] < A[j+1]) j++; // 如果右孩子大于左孩子，则让j保存右孩子的下标 if(temp < A[j]) // 如果父结点的值小于孩子结点的值 { A[i] = A[j]; // 则将让孩子结点交换到父结点的位置 i = j; j = 2*i + 1; } else break; // 满足大根堆的性质，跳出循环 } A[i] = temp; // 将保存的原父结点的值插入到适当的位置 }
在建立初始堆的时候，需要从最后一个非叶子结点开始由后向前进行调整，直到整个序列都满足堆的性质。此时，根结点为最大元素，将根结点与最后一个叶子结点
交换位置，使最大元素归位，但是破坏了堆的结构，因此需要在剩下的n-1个元素调用堆的调整算法进行调整，如此反复，直到元素都有序。
堆排序算法实现如下：
void HeapSort(int A[], int n) { int i, temp; for(i=n/2-1; i>=0; i--) // 从最后一个非叶子结点开始调整，因此i初始为n/2-1 Adjustment(A, i, n-1); // 调用堆的调整算法 for(i=n-1; i>=1; i--) // 进行n-1趟排序 { temp = A[0]; // 辅助变量temp用来保存根结点的值 A[0] = A[i]; // 将根结点值与叶子结点交换 A[i] = temp; Adjustment(A, 0, i-1); // 此时最大元素归位，对剩下的n-1个元素调用堆的调整算法，重新调整为大根堆 } }
堆排序的时间复杂度为O(nlog2n)，空间复杂度为O(1)，是一种不稳定的排序算法。
原文：http://www.cnblogs.com/greedyco/p/7152708.html