本篇文章主要用图片的形式讲解了堆排序流程，之后用java代码实现堆排序并且分析时间复杂度，具有一定参考价值，感兴趣的朋友可以了解一下。
一、引言二、图解堆排序（heapsort）三、java代码实现及时间复杂度分析四、总结
一、引言 优先队列可以用于以o(nlogn)时间排序，正如上一篇的求解topk问题中用到的思想一样，这种思想就是堆排序(heapsort)。
二、图解堆排序（heapsort） 算法思想：通过将数组元素进行buildheap进行堆序化（构建大顶堆）；再对堆进行n-1次deletemax操作。这里有个技巧，如果使用新的数组来存储，需要o(n)的空间；但每次deletemax会空出一个位置，并将尾端的节点进行下滤操作，那我们就可以将deletemax的数据放到尾端。堆排序过程：对二叉堆不了解的可以看看图解优先队列（堆）
三、java代码实现及时间复杂度分析 我们从数组下标0开始，不像二叉堆从数组下标1开始。
代码实现
public class heapsort { public static void main(string[] args) { integer[] integers = {7, 1, 13, 9, 11, 5, 8}; system.out.println("原序列：" + arrays.tostring(integers)); heapsort(integers); system.out.println("排序后：" + arrays.tostring(integers)); } public static <t extends comparable<? super t>> void heapsort(t[] a) { if (null == a || a.length == 0) { throw new runtimeexception("数组为null或长度为0"); } //构建堆 for (int i = a.length / 2 - 1; i >= 0; i--) { percdown(a, i, a.length); } //deletemax for (int i = a.length - 1; i > 0; i--) { swapreferences(a, 0, i); percdown(a, 0, i); } } /** * 下滤的方法 * * @param a：待排序数组 * @param i：从哪个索引开始下滤 * @param n ：二叉堆的逻辑大小 * @param <t> */ private static <t extends comparable<? super t>> void percdown(t[] a, int i, int n) { int child; t tmp; for (tmp = a[i]; leftchild(i) < n; i = child) { child = leftchild(i); if (child != n - 1 && a[child].compareto(a[child + 1]) < 0) { child++; } if (tmp.compareto(a[child]) < 0) { a[i] = a[child]; } else { break; } } a[i] = tmp; } private static int leftchild(int i) { return 2 * i + 1; } /** * 交换数组中两个位置的元素 * * @param a：目标数组 * @param index1 ：第一个元素下标 * @param index2 ：第二个元素下标 * @param <t> */ private static <t> void swapreferences(t[] a, int index1, int index2) { t tmp = a[index1]; a[index1] = a[index2]; a[index2] = tmp; }}//输出结果//原序列：[7, 1, 13, 9, 11, 5, 8]//排序后：[1, 5, 7, 8, 9, 11, 13]
时间复杂度：buildheap使用o(n)的时间，元素下滤需要o(logn)，需要下滤n-1次，所以总共需要o(n+(n-1)logn) = o(nlogn)。从过程可以看出，堆排序，不管最好，最坏时间复杂度都稳定在o(nlogn)。
空间复杂度：使用自身存储，无疑是o(1)。
四、总结 本篇通过画图，说明堆排序的过程，清晰明了知道堆排序先经过堆序化，再通过deletemax进行排序。其空间复杂度是o(1)，时间复杂度稳定在o(nlogn)。
以上就是java学习之堆排序流程图解以及代码讲解的详细内容。