基于最大堆的堆排序算法

素颜马尾好姑娘i 2022-05-22 03:45 261阅读 0赞

**堆排序**

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

**堆**

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。  
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子![这里写图片描述][70]  
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]

小顶堆：arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\]  
**堆排序基本思想及步骤**  
**堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了**  
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

a.假设给定无序序列结构如下![这里写图片描述][70 1]2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。![这里写图片描述][70 2]4.找到第二个非叶节点4，由于\[4,9,8\]中9元素最大，4和9交换。![这里写图片描述][70 3]这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中6最大，交换4和6![这里写图片描述][70 4]  
　　此时，我们就将一个无需序列构造成了一个大顶堆。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换![这里写图片描述][70 5]b.重新调整结构，使其继续满足堆定义![这里写图片描述][70 6]c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.![这里写图片描述][70 7]后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序![这里写图片描述][70 8]再简单总结下堆排序的基本思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。  
　　**代码实现：**

package cn.DataStructures.Sort;
    /** * 堆排： * 最大堆需要满足两个条件： * 1、堆的树结构是完全二叉树 * 2、堆中的每个节点的元素值不小于该节点的孩子节点的值 * 思想：分为2大步： * 1.对给出的数组构建最大堆 * 1）先比较父亲节点的左孩子与右孩子节点的大小，在比较左孩子与右孩子最大的值与父亲节点比较， * 将如果大于父亲节点则与父亲节点互换，然后再进行最大堆的调整 * 2.对构建的最大堆的第一个元素和最后一个元素进行排序，再对乱的堆进行调整成为最大堆 * * @author Administrator * */
    public class HeapSort11 { 
        public static void main(String[] args) {
            int []arr={
       12,20,5,16,15,1,2,100,30,45,23,9};
            System.out.println("排序前：");
            printSort(arr);
            System.out.println("排序后：");
            heapSort(arr);
            printSort(arr);
        }
        public static void heapSort(int []arr){
            //构建最大堆
            for(int i=arr.length/2-1;i>=0;i--){
       //从倒数第一个非叶子节点开始从右至左，从下到上进行遍历
                buildHeap(arr,i,arr.length);
            }
            //将最大堆的第一个元素与最后一个元素互换并且重新调整成为最大堆
            for(int j=arr.length-1;j>0;j--){
       //j>0为了保证有两个元素可以比较
                swap(arr,0,j);//交换第一个元素和最后一个元素
                buildHeap(arr,0,j);//初始情况下root节点为最后一个元素的值
            }
        }
        //构建最大堆（每个父亲节点的值要大于其孩子节点）
        public static void buildHeap(int []arr,int parent,int length){
       //length、为数组的长度，不是索引
            int child=2*parent+1;//parent的左孩子
            int temp=arr[parent];//把父亲节点的值赋值给临时变量
            for(;child<length;child=2*child+1){
                if(child+1<length&&arr[child]<arr[child+1])//比较左孩子与右孩子的大小
                    child++;//右孩子大，指向右孩子
                if(arr[child]>temp){
       //孩子节点与父亲节点比较
                    arr[parent]=arr[child];//把孩子索引的值赋值给父亲节点
                    parent=child;//把父亲节点索引指向孩子节点的索引，此时孩子的节点的索引暂时变为parent
                }
                //arr[child]<=temp的情况下，满足最大堆的条件，跳出循环
                else
                    break;
    
            }
            arr[parent]=temp;//把临时变量赋值给此时孩子的节点（此时孩子节点的索引变为parent）
        }
        //交换元素
        public static void swap(int []arr ,int a,int b){
            int temp=arr[a];
            arr[a]=arr[b];
            arr[b]=temp;
    
        }
        //打印数组
        public static void printSort(int []arr){
            StringBuilder res=new StringBuilder();
            res.append("[");
            for(int i=0;i<arr.length;i++){
                if(i==arr.length-1)
                    res.append(arr[i]+"]");
                else
                    res.append(arr[i]+",");
            }
            System.out.println(res.toString());
        }
    }

结果显示：  
![这里写图片描述][70 9]

[70]: /images/20220522/f524546ac5624e08b0259c49a4e682ec.png
[70 1]: https://img-blog.csdn.net/20180614111206992?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwcTEyMDE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180614111247431?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwcTEyMDE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: https://img-blog.csdn.net/20180614111319190?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwcTEyMDE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: /images/20220522/028d0df0cc2d4bbd997486e68b127dd9.png
[70 5]: https://img-blog.csdn.net/20180614111438846?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwcTEyMDE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 6]: https://img-blog.csdn.net/20180614111511628?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwcTEyMDE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 7]: https://img-blog.csdn.net/20180614111546239?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xwcTEyMDE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 8]: /images/20220522/90b00147199b49329e96b0998481eb7a.png
[70 9]: /images/20220522/17e6743f94714ee1bed45f7f44dc92fd.png