堆排序非常简单

来源百度百科:

堆排序（Heapsort）是指使用堆树（heap）的数据结构设计的排序算法，这是一种选择性排序. 您可以使用数组的特征快速定位具有指定索引的元素. 堆分为大根堆和小根堆，这是一个完整的二叉树.

我已经有一篇关于二叉树入门的文章. 当时，我在谈论二进制搜索树. 上面提到的完整的二叉树是哪种二叉树？ ？完整的二叉树是什么样的二叉树？ ？甚至还有完整的二叉树？ ？

下面的图片来讨论它:

参考:

简单来说: 堆排序是一种将数据视为完整的二叉树并根据完整的二叉树的特征进行排序的算法

这里我们讨论最大堆: 每个父节点当前都大于子节点

完整的二叉树具有一个特征: 左子节点的位置=当前父节点的两倍+ 1，右子节点的位置=当前父节点的两倍+ 2

现在我们有了一个完整的二叉树: 左子树和右子树都满足最大堆-> parent> child

但是我们会发现根元素的数量不匹配，显而易见的是: 1小于7

我们将交换它. 交换之后，我们会发现: 正确的子树不再匹配〜

因此二叉排序树 堆，正确的子树变为:

最后，我们还将右子编号的最大值交换到右子树的根元素

因此我们的第一个堆构建操作已完成！

可以发现，一旦建立了堆，我们的最大值就在堆的根节点上

然后替换堆顶部和数组最后一个元素的最大值，我们完成了一次旅行.

接下来，剩余的数字将继续建立二叉排序树 堆，并且交换可以完成我们的堆排序.

.........建立一个堆，交换...建立一个堆，交换...建立一个堆，交换...建立一个堆，交换...

比较当前父节点是否大于子节点，如果大于，则将交换当前父节点，直到堆构造完成为止.

    /**
     * 建堆
     *
     * @param arrays          看作是完全二叉树
     * @param currentRootNode 当前父节点位置
     * @param size            节点总数
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {
        if (currentRootNode < size) {
            //左子树和右字数的位置
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;
            //把当前父节点位置看成是最大的
            int max = currentRootNode;
            if (left < size) {
                //如果比当前根元素要大，记录它的位置
                if (arrays[max] < arrays[left]) {
                    max = left;
                }
            }
            if (right < size) {
                //如果比当前根元素要大，记录它的位置
                if (arrays[max] < arrays[right]) {
                    max = right;
                }
            }
            //如果最大的不是根元素位置，那么就交换
            if (max != currentRootNode) {
                int temp = arrays[max];
                arrays[max] = arrays[currentRootNode];
                arrays[currentRootNode] = temp;
                //继续比较，直到完成一次建堆
                heapify(arrays, max, size);
            }
        }
    }

值得注意的是，当我们在上面遇到堆排序时，我们的条件是左子树和正确数量的子代已经有一个parent>子代.

    /**
     * 完成一次建堆，最大值在堆的顶部(根节点)
     */
    public static void maxHeapify(int[] arrays, int size) {
        // 从数组的尾部开始，直到第一个元素(角标为0)
        for (int i = size - 1; i >= 0; i--) {
            heapify(arrays, i, size);
        }
    }

完成第一个堆构建后，我们将发现最大值位于数组的顶部:

接下来，连续构建堆，然后将数组的最后一位与当前堆的顶部（数组的第一位）交换以进行排序:

    for (int i = 0; i < arrays.length; i++) {
        //每次建堆就可以排除一个元素了
        maxHeapify(arrays, arrays.length - i);
        //交换
        int temp = arrays[0];
        arrays[0] = arrays[(arrays.length - 1) - i];
        arrays[(arrays.length - 1) - i] = temp;
    }

堆排序比其他排序要困难一些. 他使用了诸如完整的二叉树之类的功能来进行排序，并且代码实现也比其他排序更为复杂.

参考:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-226137-1.html