堆排序原理及实现

作者：测吧(北京)科技有限公司

2022 年 9 月 29 日
北京
本文字数：1746 字
阅读完需：约 6 分钟

前言

经常听到研发面试基础题或者说基本功都包括算法题目，那常用的算法都有哪些？

小白们也很熟悉的：冒泡，归并，简单选择，归并，堆排序。

那它们区别是什么呢？需要好好梳理一下了。今天咱们就先瞅瞅感觉比较抽象的堆算法吧。

堆排序基本思想

什么是堆？堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右子结点的值，称为小顶堆。

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个(0…n-1)序列重新构造成一个堆，这样就会得到 n 个元素中的次小值。如此反复执行，便能得到一个有序序列了。

问

好了简单介绍之后，也没觉得有啥记忆的功能啊？

答

其实堆是有记忆功能的，就是因为他自身的结构，每个结点的值都大于或等于其左右孩子结点的值（这是大顶堆，小顶堆则是每个结点的值都小于或等于其左右孩子结点的值），这就是记忆！当你将整个序列构建成一个堆之后，那么结点元素是比左右孩子大或者小的，这就是记忆！如果还是晕的，那么恭喜你，我在学习的过程中这个阶段的时候也是没想明白的，先看看实现吧！

堆排序实现

先看看核心代码

/*** 堆排序** @paramarr*/public void sort(int[] arr) {
    System.out.println("初始序列状态: " + Arrays.toString(arr) + "\n");    intlen = arr.length;    //构建初始大顶堆    for (inti = len / 2 - 1; i&gt;= 0; i--) {
        System.out.println("构建初始大顶堆: " + i);        heapAdjust(arr, i, len - 1);    }
    //交换堆顶元素和未排序序列的最后一个元素,并重新构建大顶堆    for (inti = len - 1; i&gt; 0; i--) {        swap(arr, 0, i);                // 元素交换        heapAdjust(arr, 0, i - 1);    }}/*** 将arr[pos...off]构建成大顶堆** @paramarr* @parampos* @param off*/public void heapAdjust(int[] arr, intpos, int off) {    int j, temp = arr[pos];
    System.out.println("--此次循环的堆顶: " + temp);
    intinit_j = pos * 2 + 1;
    for (j = init_j; j &lt;= off; j = j * 2 + 1) {
        System.out.println("---循环索引值: " + j + " 数值: " + arr[j]);        if (j &lt; off &amp;&amp;arr[j] &lt;arr[j + 1]) {            System.out.println("---左右子节点对比: 左 " + arr[j] + " 小于右 " + arr[j + 1]);            ++j;        }        // 节点不小于左右孩子节点        if (temp &gt;= arr[j]) {            System.out.println("---此次循环的堆顶: " + temp + " 大于左右子节点!");            break;        }
        int exchange = arr[j];
        arr[pos] = arr[j];        pos = j;        arr[pos] = temp;        System.out.println("---交换位置: " + arr[pos] + " 和 " + exchange);    }    arr[pos] = temp;
    System.out.println("--当前序列状态: " + Arrays.toString(arr) + "\n");}