排序算法（八）堆排序

堆排序算是里面最比较难懂的算法了，因为堆排序需要二叉树的基础。不过虽然说靠的是二叉树但是实际上并没有生成一个二叉树而是利用了顺序存储二叉树，来构造大顶堆和小顶堆来实现的。

堆排序的基本介绍

名字	平均时间复杂度	最好时间复杂度	最差时间复杂度	空间复杂度	是否流弊
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	是

我感觉这个算法牛不牛逼已经是不言而喻的了。时间复杂度是交换法的巅峰，空间复杂度还是O(1)，这个算法实在是神奇。赶紧如果是学会了这个算法就可以去装逼了。别人排个序是好几秒，你排个序是几毫秒。关键是你们用的还是同样的内存，这谁能顶得住啊！不过，要说明的是，堆排序是一种不稳定的算法。

堆排序的基本思路

上面也提到了，堆排序是用顺序存储二叉树来实现的。那什么是顺序存储二叉树呢？

且看下图

我们大多数时候所了解到的二叉树都是上面的链式结构的二叉树，直观而且容易理解和操作。但是二叉树也可以用数组来表示。可以说一个数组就对应了一个二叉树。右面的图展示的是非完全二叉树的顺序存储，这里是我们不需要的。因为堆排序的时候要构造大顶堆(从小到大排序)。如果要是从小到大排序的话就要构造小顶堆。大/小顶堆就是一种完全二叉树。所谓完全二叉树所有的叶子节点(也就是没儿子的节点)都必须出现在最后两层，而且叶子节点在左面要连续。

按照上面的顺序存储的关系，上面的大顶堆可以转换成为一个数组来表示。

观察这个数组和二叉树，我们可以得出如下的结论。arr[n]的左子结点是arr[2n+1]，右子节点是arr[2n+2]，父节点是arr[(n-1/2)]

大顶堆的每个一个节点的值都大于他的左子结点和右子节点。但是左右节点之间的大小是不用限制的。

根据大顶堆的定义我们就可以知道大顶堆的根节点的值一定是所有节点当中最大的。如果我们把根节点去掉，然后利用剩下的节点再构造一个大顶堆。我们又可以找到第二大的节点，如此循环。我们就可以让数组变得有序。但是，如何构造大顶堆呢？

看到上面的动图其实是有一点儿傻眼的，这不是数组排序吗？为什么搞这个一个二叉树在这？其实我们实际上并没有构造这个一个二叉树，只是把数组想象为一个完全二叉树罢了。要想把一个二叉树变成大顶堆，首先我们要看他的非叶子节点，因为叶子节点没有子节点，对于构造大顶堆是没有意义的。对于一个顺序存储二叉树，他的叶子节点是哪几个呢？答案是从0到arr.length/2-1。蛤？为什么是这几个节点啊？如果你仔细观察的话，叶子节点的个数永远是比非叶子节点多一个的，一棵树要么是叶子节点，要么是非叶子节点，所以非叶子节点个数 arr.length/2个。而非叶子节点都是存储在数组的前面的，所以说非叶子节点的下标是0到arr.length-1。

对于一个非叶子节点来说，要满足大顶堆的条件，就要使他大于他的子节点。而所有的非叶子节点都大于他们的子节点的话，这棵树就是一个二叉树了。

堆排序的代码实现

将数组调整为大顶堆代码实现

    /**
     *  将一个数组（二叉树）调整成一个大顶堆
     * @param arr 待排序数组
     * @param i 非叶子节点在数组中的索引
     * @param length 数组的大小(逐渐减小的)
     */
    private static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //：2*i+1 左子节点的索引       2*i+2 右子节点的索引
        for (int k = 2*i+1; k < length; k=2*k+1) {
            if (k+1<length && arr[k] < arr[k+1]) {
                k++;
            }
            if (arr[k] > temp) { //：子节点大于父节点， 两者交换位置
                arr[i] = arr[k];
                i = k; // 继续循环比较
            }else {
                break; //：为什么break？ 以i为父节点的下面的都已经排序过了，都是大顶堆了
            }
        }
        arr[i] = temp;
    }

代码说明：

for循环里面的k, temp是干什么的 ?

k的初始值是给定的非叶子节点的左子结点。每次循环都要到下一个左子结点。arr[k] < arr[k+1]就是比较左右子节点哪个大。k++就是定位到右子节点，因为一开始k是指向左子结点的，右子节点的下标比左子结点大1。

temp保存的是给定的非叶子节点中的值。 arr[k] > temp 说明左右子节点中较大的那个要比他要大，那么就把他赋给当前给定的非子节点。

为什么 i = k。为什么要循环比较？

非叶子节点不是只有叶子节点，他们的子节点也会有子节点。假定我们让子节点的值变成非叶子节点的那个值，而非叶子节点的值又是很小的。那么那个子节点构成的岂不是大顶堆了？所以还是要递归下去继续构造大顶堆。

为什么else break？

其实这个问题应该在第二个问题的前面的。我们构造大顶堆其实是从下往上构造的。也就是说从arr.length/2-1到0这个顺序来构造的。也就是说我们在构造非叶子节点i的过程中就知道他的左子树和右子树其实都是大顶堆。如果我们没有进行交换也就没有破坏左子树和右子树的大顶堆结构，如果进行交换了就有可能破环了他们的大顶堆结构了。毕竟如果交换了，说明非叶子节点的值要小一点嘛。你不能确保他比子节点的子节点的值要大。

arr[i] = temp 是什么意思？

你或许发现了，我们始终没有说交换，这就有点像移位法的味道了。我们只是给i找到合适的位置，（第二个问题中的i = k 就是在做这个事情）当for循环退出了，意味着i的位置就找到了，这时给之前保存好的temp安上去就行了。

堆排序代码

public static void heapSort(int[] arr) {
        int temp = 0;
        // 将其变成大顶堆
        for (int i = arr.length/2-1; i >=0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        // ：将大顶堆上面的元素交换到末尾，然后对大顶堆最上面的元素排序
        for (int j = arr.length-1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
    }

代码说明：

第一个for循环?

其实第一个for循环就是我们上面说过的，大顶堆是从下往上构造的。只有这样我们才能确保要构造的非叶子节点的左子树和右子树都是大顶堆。

第二个for循环？

将构造好的大顶堆的根的值(arr[0])放到数组的最后面，然后把数组最后面的元素移动到根处。并且还要将要进行构造大顶堆的 length-1，因为已经最大的那个数已经不用再去构造大顶堆了，安心在数组后面躺着吧。

adjustHeap(arr, 0, j)，这次构造大顶堆为什么没有循环了，而一开始需要循环？

因为一开始的数组对应的二叉树的根节点的子树不是大顶堆。而此时，将一个大顶堆的根节点移走，然后取他的一个叶子节点作为新的根，这个新的二叉树虽然不再是大顶堆，但是根节点的左右子树依然是大顶堆。所以说不用再循环了。

堆排序的测试

测试环境及工具：我的电脑 Huawei MateBook 13+JDK1.8+Eclipse

测试手段：随机生成80000个和8,000,000个[0,800000）的整数的数组进行排序，观察所花费的时间

测试代码：

    public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        heapSort(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");
    }

80,000数据时：

Time : 9ms

Time : 0ms

Time : 15ms

8,000,000数据时：

Time : 1686ms

Time : 1703ms

Time : 1672ms

总结

什么这个0ms你是认真的吗？我测试了几次，有好几次0ms，但是全写0ms有点太高调了，所以还是让你大一点，防止你骄傲。不过说实话处理八百万个数据的时候，堆排序处理的并不快。毕竟是空间复杂度O(1)的算法，对于海量数据的处理还是略显疲软。不过这并不然掩盖这个算法的光辉之处，能想到这样的排序算法，图灵奖获得者——弗洛伊德是真的牛逼。这个人好像写了不少有名的算法。QwQ

排序算法（八）堆排序