java 实现数组的堆排序（大顶堆）

古城微笑少年丶 2022-11-30 12:46 127阅读 0赞

话不多说先上代码如果不想看原理，直接就抄代码就行了：

/**
     * 堆排序
     * 具体的流程是 数组---》大顶堆（或者是小顶堆）---》第一个个元素和最后一个元素调换位置---》重复元素下沉，以完成排序
     */
    public class HeapSort {
    
        // 将一个数组 转化成 大顶堆 (根节点一定是比 左右子节点都大的）
        // 规则是  arr[i].left = arr[2*i+1]
        //        arr[i].right = arr[2*i+2]
        //        arr[i].super = arr[i/2]
    
        /**
         * 将一个数组 转化成 大顶堆
         * @param arr:数组
         * @param i :与左右子节点判断大小的  根节点
         * @param length : 数组的总长度
         */
        public void toMaxHeap(int[] arr,int i,int length){
    
            int temp = arr[i]; // 将操作的节点元素拿出来，用于指针
            // 主要循环判断左右子节点，由于不能只判断一层，那么就需要循环。知道当前节点的所有子节点，都比自己小为止
            // 从左节点开始判断（i*2+1），判断完之后，需要以 k 位置为根节点继续判断，即k*2+1。
            for(int k=2*i+1;k<length;k=k*2+1){
                // 需要判断左、右子节点都满足的情况下,如果右边节点比左边大，那么就直接后续用k+1 来计算
                if(k+1<length && arr[k]<arr[k+1]){
                    k++;
                }
                if(arr[k] > temp){  // 如果k位置（左节点）比 i位置（根节点）大，那么就需要换位置，
                    arr[i] = arr[k]; // 将k位置的元素放到i位置上。
                    // 已经将原i位置上的元素换成了比他大的元素。
                    // 需要记录调换之后的k位置 元素，要不容易造成多个相同的元素。
                    i=k;
                }
            }
            arr[i] = temp;  // 将原来i位置上的元素，放到 所有较大的元素换走的位置上。
    
        }
    
        public void heapSort(int[] arr){
            int length = arr.length;
    
            for(int i=length/2;i>=0;i--){
                toMaxHeap(arr,i,length);
            }
    
            for(int j=length-1;j>0;j--){
                swap(arr,0,j);
                toMaxHeap(arr,0,j);
            }
        }
    
        public void swap(int[] arr,int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        public static void main(String[] args) {
    
            HeapSort heapSort = new HeapSort();
    
            int[] arr = {4,5,3,2,6,1,7,10,8};
    
            heapSort.heapSort(arr);
    
            for(int i=0;i<arr.length;i++){
                System.out.println(arr[i]);
            }
        }
    }

*   我所理解的堆排序中的堆结构是一个比较抽象的。暂且将堆 等同于二叉树的结构。
 *  借用网上的一个博客的对堆的介绍：

1.  堆是一棵完全二叉树；
2.  堆序性 (heap order): 任意节点都**优于**它的**所有孩子**。
    
    a. 如果是任意节点都**大于**它的所有孩子，这样的堆叫**大顶堆**，Max Heap;
    
    b. 如果是任意节点都**小于**它的所有孩子，这样的堆叫**小顶堆**，Min Heap;

![format_png][]

左图是小顶堆，可以看出对于每个节点来说，都是小于它的所有孩子的，注意是**所有孩子，包括孙子，曾孙...**

1.  既然堆是用数组来实现的，那么我们可以找到每个节点和它的父母/孩子之间的关系，从而可以直接访问到它们。

![format_png 1][]

比如对于节点 3 来说，

*  它的 Index = 1，
 *  它的 parent index = 0,
 *  左孩子 left child index = 3,
 *  右孩子 right child index = 4.

可以归纳出如下规律：

*  设当前节点的 index = x,
 *  那么 parent index = (x-1)/2,
 *  左孩子 left child index = 2\*x + 1,
 *  右孩子 right child index = 2\*x + 2.

有些书上可能写法稍有不同，是因为它们的数组是从 1 开始的，而我这里数组的下标是从 0 开始的，都是可以的。

这样就可以从任意一个点，一步找到它的孙子、曾孙子，真的太方便了，在后文讲具体操作时大家可以更深刻的体会到。

其实如果理解了这个结构，那么算法也就很简单了。

1、首先将数组转化的堆结构，变成一个大顶堆（当然也可以是小顶堆）。

2、此时第一个元素肯定是最大的一个数。这时候将堆顶的元素和最后一个元素交换位置。

3、此时大顶堆的结构被破坏，所以就需要重新构建大顶堆。

4、完成之后，堆顶的数据永远是最大的。这时在将堆顶的元素和倒数第二个元素交换位置。

5、一次重复前几步，直到只剩下两个元素。此时直接交换位置就行。

6、这样，就通过大顶堆的结构将数组进行了排序（从小到大）。

*  这个算法主要难点就是构建大顶堆的过程。思路是这样的：

1、从堆顶依次向下下沉的话，只能向下交换一次，这时是不能保证堆顶是最大的。因为只能选出来最上边的三个元素中最大的。那么是不能保证他是数组数据中最大的一个。

2、所以我们选择从后边向前交换。再由之前我们的理论，左右子孩子是2\*i+1和2\*i+2。所以我们直接从 长度（length）/2开始计算。这样就可以保证堆顶一定是数组中最大的元素。

*  假设给定无序序列结构如下

![format_png 2][]

*  此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

![format_png 3][]

*  找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换。

![format_png 4][]

*  这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6。

![format_png 5][]

此时，我们就将一个无需序列构造成了一个大顶堆。

接下来就是一系列的交换啊啊、重建的过程。

[format_png]: /images/20221123/a5509516f6554206b65d0cba9df0dbc4.png
[format_png 1]: /images/20221123/c65931f357f640fb83a2ccb7cc5e33e6.png
[format_png 2]: /images/20221123/747afb91d1b64932bef4e3665950d9e8.png
[format_png 3]: /images/20221123/d6b83f69296c4012a653a0c8bf091b8c.png
[format_png 4]: /images/20221123/a89cf2d26fd04d9bb8d8d024373cece2.png
[format_png 5]: /images/20221123/7e07046e2ca048e1a4ff1e31d10f0664.png