堆是一种重要的数据结构，为一棵完全二叉树, 底层如果用数组存储数据的话，假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2。分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点。所谓堆排序就是利用堆这种数据结构来对数组排序，我们使用的是最大堆。处理的思想和冒泡排序，选择排序非常的类似，一层层封顶，只是最大元素的选取使用了最大堆。最大堆的最大元素一定在第0位置，构建好堆之后，交换0位置元素与顶即可。堆排序为原位排序(空间小), 且最坏运行时间是O(nlgn)，是渐进最优的比较排序算法。
/** * 堆排序算法 */ package sort; import java.util.Arrays; /** * @author 16026 * */ public class HeapSort { // 建初始堆(小顶堆) public static void iniHeap(int[] array, int low, int high) { int i = low; // 子树的根节点 int j = 2 * i + 1; // j为i节点的左孩子 int temp = array[i]; while (j < high) { // 沿较小值孩子节点向下筛选 if (j < high - 1 && array[j] > array[j + 1]) { j++; // j为左右孩子的较小者 } if (temp > array[j]) { // 若父母节点值较大 array[i] = array[j]; // 孩子节点中的较小值上移 i = j; j = 2 * i + 1; } else { j = high + 1; // 退出循环 } } array[i] = temp; // 当前子树的原根值调整后的位置 } public static void heapSort(int[] array) { int len = array.length; int temp; for (int i = len / 2 - 1; i >= 0; i--) { // 创建堆 iniHeap(array, i, len); } for (int i = len - 1; i > 0; i--) {// 每趟将最小关键字值交换到后面，再调整成堆 temp = array[0]; array[0] = array[i]; array[i] = temp; iniHeap(array, 0, i); } } public static void main(String[] args) { int[] array = { 58, 69, 45, 25, 69, 48, 29, 65, 47 }; heapSort(array); System.out.println(Arrays.toString(array)); } }运行结果是：
