首先来了解一下什么是堆排序
堆排序是利用二叉树（是完全二叉树）这种数据结构而设计的一种排序算法，属于选择排序的一种。先了解两个概念
大根堆：每个孩子节点的值小于等于其父节点的值。例如：
小根堆：每个孩子节点的值大于等于其父节点的值。例如：
给定一个数组，如何用完全二叉树表示呢？
这个数组对应的完全二叉树按层进行编号，其逻辑结构如下图
接下来看看堆排序的基本思想：将待排序数组构造成一个大根堆，此时，整个序列的最大值就是整个二叉树的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个二叉树，这样会得到n个元素的次大值。如此反复，便能得到一个有序序列了。
接下来看看如何完成整个排序过程：
1.假如原始序列如图所示：
2.此时从最后一个叶子节点的父节点开始进行调整，从下至上依次调整。此次调整将整个树的最大值放到了根节点。
这样就完成了一次调整，此时最大值11跑到了根节点。并且每个节点的子树都满足了大根堆的特点。
此时再将根节点的11与整个树的最后一个节点交换。
这样最大值就跑到了最后。
3.对 除去最后一个叶子节点的树重复2
因为最后一个叶子节点已经是最大，就不管他了。
调整完，10跑到了根，将其与7交换，此时次大值10与最大值11就有序了
4.继续对剩下的树排序，以下为具体过程
8到了根的位置，将与最后一个交换
这样整个数组就有序了。接下来看一下代码。
public static void adjust(int[] array,int start,int end){ int tmp =array[start]; //一次调整过程 for(int i = 2*start+1;i<=end;i=2*i+1){ //找到左右孩子的最大值 if(i < end && array[i] < array[i+1]){//i<end保证有右孩子 i++;//最大值下标 } if(array[i] > tmp){ array[start] = array[i]; start = i; } if(array[i] < tmp){ break; } } array[start] = tmp; } public static void heapSort(int[] array){ //一次调整，最大值到了根节点 for(int i = (array.length-1-1)/2;i >= 0;i--){//i相当于start adjust(array,i,array.length-1); } //最后一个值与根节点交换 int tmp = 0; for(int j = 0;j < array.length-1;j++){ tmp = array[0]; array[0] = array[array.length-1-j]; array[array.length-1-j] = tmp; adjust(array, 0, array.length-1-1-j);//调整最大的树 } }
