先简单分析一下什么是堆排序。
堆排序就是建立一个大顶堆（小顶堆）。假设一开始整个堆的元素都是待排序元素，然后把这个待排序的堆的最顶部元素和堆底元素互换，和堆底互换的元素就是这个待排序堆的最值。然后让待排序堆的长度-1，就相当于把互换过去的那个最值给排除在外，剩下的又是一个待排序的堆，并且由于堆底的元素跑到了堆顶，所以这里需要再次进行顶堆的构造。构造完成后，重复 2 3 步，直到待排序堆里面只有一个元素的时候，就可以退出了，因为一个元素自然有序，这时候的元素序列就是有序的了。如果想要降序就建立小顶堆，如果想要升序，就建立大顶堆。大顶堆可以想象成一个完全二叉树，这个二叉树的根节点大于左右子树，然后左右子树也满足大顶堆这个性质，那么这个完全二叉树就是一个大顶堆。（小顶堆同理）
代码思路：
首先要进行建立大顶堆或者小顶堆。然后对堆顶和堆底元素进行不断的互换。互换完了后要对剩下的待排序堆再次重新建立新的大顶堆或者小顶堆。如此反复，直到待排序堆只剩下一个元素位置。代码如下： 下面展示一些 内联代码片。
import java.util.Arrays; /** * 1. 首先建立一个大顶堆或者小顶堆。 * 2. 根据顶堆的性质，取第一个元素后堆底互换， * 使得待排序序列的最值依次往后排，已经排过的值不算在待排序序列里面。 * 3. 交换了堆底元素到堆顶后，再次进行顶堆调整。 * 4. 调整完后，重复 2 3，直到只剩下一个元素，即有序。 * * @date 2020/10/19 0019 * @time 12:04 */ public class 堆排序 { public static void main(String[] args) { int[] arr = {543,55,43,873,15,14,54687,318,41354,13,5}; HeapSort(arr); System.out.println(Arrays.toString(arr)); } // 1. 初始堆：这里以小顶堆为例 // 传入参数：一个数组 // 无返回值，因为数组是引用类型，会跟着变 private static void BuildMinHeap(int[] arr){ // 因为顶堆是一个完全二叉树，所以分支节点只有n/2向下取整那么多 // 只需要从下往上依次判断自己的左右孩子和自己的比较后，是否符合顶堆要求 for (int i=arr.length/2; i>=0; i--){ HeapAdjust(arr,i, arr.length); } // 这里输出查看原数组顺序，便于观察效果 System.out.println(Arrays.toString(arr)); } // 2. 堆调整 // 传入参数：一个数组，调整的长度(这个长度指的是待排序的范围) // 无返回值，因为数组是引用类型，会跟着变 private static void HeapAdjust(int[] arr, int k,int len){ // i指的是当前k节点的左孩子 for (int i=2*k+1; i<len; i=k*2+1) { if (i+1 < len) { // 判断右孩子是否存在 if (arr[i + 1] < arr[i]) { // 如果左孩子大于右孩子，则让i++，走向右孩子的位置 i++; } // 不管i是否++，都是指向的小的那个 // 然后判断小的这个和当前节点谁比较小 // 如果当前节点小，则直接退出 } if (arr[k]<=arr[i]) break; // 如果当前节点不比左右孩子中小的那个小，则互换位置 int temp = arr[i]; arr[i] = arr[k]; arr[k] = temp; k=i; // 让目标位置移动到小的位置 // 互换完位置后，此时目标节点已经移动到自己的较小的孩子位置处了 // 进行下一层的判断 } } // 3. 堆排序 // 传入参数：一个已经是顶堆的数组 // 无返回值。 private static void HeapSort(int[] arr){ BuildMinHeap(arr); for (int i=0; i<arr.length-1; i++){ // 这里是从头向尾依次交换的，这里小于是少比较了依次，因为最后一次只有一个元素，自然有序 // 先进行交换 int temp = arr[0]; arr[0] = arr[arr.length-1-i]; arr[arr.length-1-i] = temp; // 然后对新的头进行调整 HeapAdjust(arr,0, arr.length-i-1); } } }以上是我写的时候，自己做的一些笔记，大家如果有不懂的或者想要讨论的，欢迎评论区见。 ~ . ~
