堆排序，使用一种称为
堆的数据结构来进行信息管理。堆不仅用在堆排序中，它还可以构造一个有效的优先队列。时间复杂度O(nlogn)
堆
（二叉）堆是一个数组，可以被看成一个近似的完全二叉树。书上的每个节点对应数组中的一个元素，除了最底层，该树是完全充满的，而且是从左到右填充。
二叉堆可以分为两种形式，最大堆和最小堆。
- 最大堆：父节点的值大于等于其子节点的值。
- 最小堆：父节点的值小于其子节点的值。
堆排序
准备
- 计算待排序数组填充为堆结构后父节点的个数
- 已知父节点在数组中的位置，求左、右子节点的位置。
- 根据数组中任意元素位置，计算其父节点所在的位置。
根据上图我们可以得出规律
java"> /**
* 根据数组长度计算父节点个数
*
* @param pos 数组长度
* @return 父节点数量
*/
private static int parent(int len) {
return len/2;
}
/**
* 根据子节点所在数组位置，计算父节点位置
*
* @param pos 子节点位置
* @return 父节点位置
*/
private static int parent(int pos) {
return (i-1)/2;
}
/**
* 根据父节点所在数组位置，计算左叶子位置
*
* @param pos 父节点位置
* @return 左子节点位子
*/
private static int left(int pos) {
return 2 * pos + 1;
}
/**
* 根据父节点所在数组位置，计算右叶子位置
*
* @param pos 父节点位置
* @return 右子节点位置
*/
private static int right(int pos) {
return 2 * pos + 2;
}
维护最大堆性质
将目光放在最小单位堆上(即数组只有三个元素，父节点、左叶子、右叶子)，对其进行维护，保持其最大堆性质。
java"> /**
* 对堆结构进行排序，将最大值作为根节点
*
* @param array 堆结构对应数组
* @param pos 排序堆根节点所在数组中的位置
* @param len 数组长度
*/
private static void maxHeap(int[] array, int pos, int len) {
//计算左右叶子位置
int l = left(pos);
int r = right(pos);
int max = pos;
if (l < len && array[l] > array[max]) {
max = l;
}
if (r < len && array[r] > array[max]) {
max = r;
}
if (max != pos) {
int temp = array[pos];
array[pos] = array[max];
array[max] = temp;
//将最大位置的堆再排序，此处是比较绕的点。
//举例说明：我们先声明二维结构描述，（parent、left、right）
//堆结构如描述（-3，20，14）（20，6，9）（14，7，8）
//此时 parent：-3需要和20做交换，交换后为(20,-3,14)(-3,6,9)(14,7,8)
//此时(-3,6,9)的结构是不对的，所以要对(-3,6,9)的堆结构排序
//结果为（20，9，14）（9，6，-3）（14，7，8）
//此时如果-3下还有子节点，还需进行排序（所以递归调用）
maxHeap(array, max, len);
}
}
建堆
能够保证最大堆性质后，我们用自底向上的方式开始建堆。即寻找到元素位置最大的父节点作为算法的开始，当元素位置到0后到达堆顶点。
java"> /**
* 将数组构建为最大堆结构
*
* @param array 数组
*/
private static void maxHeapBuild(int[] array) {
int parentSize = array.length / 2;//计算包含子节点的父节点结束位置
for (int i = parentSize; i >= 0; i--) {
maxHeap(array, i, array.length);
}
}
堆排序算法
利用
maxHeapBuild构建最大堆，此时数组最大值元素位于顶点，将尾部元素与顶点元素对换位置，然后去掉堆尾部元素，创建新堆。新堆此时对换位置后可能不满足最大堆性质，需要执行maxHeap维持最大堆，然后再与当前堆的尾部元素交换，依次循环进行。
java"> /**
* 堆排序
*
* @param array 排序数组
*/
private static void heapSort(int[] array) {
//构建最大堆结构， 构建后的array数组并不能保证是有序的
//但是每个父节点肯定是最大的
maxHeapBuild(array);
System.out.println("first build head ::: "+Arrays.toString(array));
//用来控制数组的排序范围，因为下面要将得到的最大的数值依次放到最后
int len = array.length;
for (int i = array.length - 1; i > 0; i--) {
System.out.println("root value :: " + array[0]);
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// i 位置被占用，排序数组长度-1
len--;
maxHeap(array, 0, len);
System.out.println(Arrays.toString(array));
}
}
哈哈，算法算不算入门了呢？加油，下一篇《排序算法之快速排序》
