堆排序原理（java实现）

浅浅的花香味﹌ 2022-06-10 12:26 152阅读 0赞

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。（摘自百度百科）  
　　  
　　想知道什么是堆排序，就得先知道什么是堆，堆分为两种，大根堆和小根堆，什么是大根堆小根堆呢？那你得先知道完全二叉树，什么是完全二叉树？完全二叉树，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。要是问什么是二叉树（自己去百度吧……），把完全二叉树理解了之后，就可以看大根堆小根堆了，大根堆的要求是每个节点的值都不大于其父节点的值，小根堆则相反，所以说，如果我构造出来一个大根堆，那么最上面的根节点一定是最大的  
　　  
　　堆排序的原理就是这样，先构造出来大根堆（假设从小到大排序），然后取出堆顶元素（也就是最大的元素），放到数组的最后面，然后再将剩余的元素构造大根堆，再取出堆顶元素放到数组倒数第二个位置，依次类推，知道所有的元素都放到数组中，排序就完成了，仔细看代码吧，光看字是很难懂的  
　　  
　　下面是Java代码实现：

class Demo
    {
        public static void main(String[] args)
        {
            //定义整型数组
            int[] arr = {
       1,5,6,8,7,2,3,4,9};
            //调用堆排序数组
            HeapSort(arr);
            //输出排序后的数组
            for(int i=0;i<arr.length;i++)
            {
                System.out.print(arr[i]+" ");
            }
        }
        //堆排序函数
        public static void HeapSort(int[] arr)
        {
            int n = arr.length-1;
            for(int i=(n-1)/2;i>=0;i--)
            {
                //构造大顶堆，从下往上构造
                //i为最后一个根节点，n为数组最后一个元素的下标
                HeapAdjust(arr,i,n);
            }
            for(int i=n;i>0;i--)
            {
                //把最大的数，也就是顶放到最后
                //i每次减一，因为要放的位置每次都不是固定的
                swap(arr,i);
                //再构造大顶堆
                HeapAdjust(arr,0,i-1);
            }
        }
    
        //构造大顶堆函数，parent为父节点，length为数组最后一个元素的下标
        public static void HeapAdjust(int[] arr,int parent,int length)
        {
            //定义临时变量存储父节点中的数据，防止被覆盖
            int temp = arr[parent];
            //2*parent+1是其左孩子节点
            for(int i=parent*2+1;i<=length;i=i*2+1)
            {
                //如果左孩子大于右孩子，就让i指向右孩子
                if(i<length && arr[i]<arr[i+1])
                {
                    i++;
                }
                //如果父节点大于或者等于较大的孩子，那就退出循环
                if(temp>=arr[i])
                {
                    break;
                }
                //如果父节点小于孩子节点，那就把孩子节点放到父节点上
                arr[parent] = arr[i];
                //把孩子节点的下标赋值给parent
                //让其继续循环以保证大根堆构造正确
                parent = i;
            }
            //将刚刚的父节点中的数据赋值给新位置
            arr[parent] = temp;
        }
    
        //定义swap函数
        //功能：将跟元素与最后位置的元素交换
        //注意这里的最后是相对最后，是在变化的
        public static void swap(int[] arr,int i)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
        }
    }