上文我们曾经说过选择排序是将整个数组从头到尾全部扫描一遍，然后选择最小的与第一位进行交换，接着再在剩下的元素中进行扫描，直到扫描完毕，最终，得到一个有序数列。我们通过观察可以发现，选择排序适合长度比较小的数组，如果一个数组太长，一般的选择排序明显不能满足。那么我们就需要一种排序来解决这种问题，那么堆排序就出现了。下面我们就先简单介绍一下堆排序：
堆排序：
堆排序是指利用堆积树（一种二叉树）这种数据结构所设计的一种排序算法，它是选择排序升级版。可以利用数组的特点快速定位指定索引的角标。堆分为大根堆和小根堆，是完全二叉树。
大顶堆：
大顶堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大顶堆，因为根据大顶堆的要求可知，最大的值一定在堆顶。如图：
小顶堆：
与大顶堆恰好相反，小顶堆的要求是每个节点的值都不小于其父节点的值，即A[PARENT[i]] <= A[i]。在数组的降序排序中，需要使用的就是小顶堆，因为根据小顶堆的要求可知，最小的值一定在堆顶。如图：
对于二叉树说起来大家可能有点迷糊，那么我们就先简单了解一下二叉树吧！
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。大概是这么个结构：
关于二叉树的介绍以及一些相关知识，可以去看看：【程序员怎能不会二叉树系列】，里面对于二叉树的类型，遍历方式，以及二叉树结构都有详细的文字说明。文尾会附上链接。
为了便于大家理解，下面我们先贴上我已经写好的大顶堆排序代码，根据代码进行讲解。
代码如下：
public static void main(String[] args) { int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int len = arr.length; long startTime = System.nanoTime(); // 获取排序开始时间 // 初始建堆 for (int i = (len - 2) / 2; i >= 0; i--) { maxHeapfy(arr, i, len); } //建堆完成 arr[len - 1] = arr[0] ^ arr[len - 1]; // 交换 arr[0] = arr[0] ^ arr[arr.length - 1]; arr[len - 1] = arr[0] ^ arr[len - 1]; for (int i = 1; i < len - 1; i++) { // 初始建堆之后还要排a.length-2次 maxHeapfy(arr, 0, len - i); arr[len - 1 - i] = arr[0] ^ arr[len - 1 - i]; // 交换 arr[0] = arr[0] ^ arr[len - 1 - i]; arr[len - 1 - i] = arr[0] ^ arr[len - 1 - i]; } long endTime = System.nanoTime(); // 获取排序结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); } static void maxHeapfy(int[] a, int i, int heapSize) { // 数组a，第i个结点，heapSize是数组实际要排序的元素的长度 // 有的时候能够递归到叶子结点，叶子结点无后继，下面两个if都注意到了这一点 int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < heapSize && a[left] > a[largest]) { // largest = left; } if (right < heapSize && a[right] > a[largest]) { largest = right; } if (largest != i) { // 把最大值给父节点 a[largest] = a[largest] ^ a[i]; a[i] = a[largest] ^ a[i]; a[largest] = a[largest] ^ a[i]; maxHeapfy(a, largest, heapSize); // 发生交换之后还要保证大根堆性质 } }
打印结果：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：5400ns
首先，我们第一步是初始化一个堆，代码如下：
for (int i = (len - 2) / 2; i >= 0; i--) { maxHeapfy(arr, i, len); }
创建一个堆之后，将我们的数据进行大顶堆排序操作，maxHeapfy方法是整个排序的核心，代码如下：
static void maxHeapfy(int[] a, int i, int heapSize) { // 数组a，第i个结点，heapSize是数组实际要排序的元素的长度 // 有的时候能够递归到叶子结点，叶子结点无后继，下面两个if都注意到了这一点 int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < heapSize && a[left] > a[largest]) { // largest = left; } if (right < heapSize && a[right] > a[largest]) { largest = right; } if (largest != i) { // 把最大值给父节点 a[largest] = a[largest] ^ a[i]; a[i] = a[largest] ^ a[i]; a[largest] = a[largest] ^ a[i]; maxHeapfy(a, largest, heapSize); // 发生交换之后还要保证大根堆性质 } }
我们对着上面的代码进行讲解一下：我们先把左子节点进行排序，再将右子节点进行排序，将最大值传递给父节点，递归操作一下，整个逻辑就完成了。
总结：
整个堆排序的主要原理就是比较交换，父子节点的相互比较，根据大小顶堆排序规则进行交换。可能有的同学理解起来比较困难，但是相信多看几遍，多敲几遍，还是能够理解的。想要理解代码，其实只有一个字，敲。敲多了自然会去思考。不然终究是纸上谈兵。
