Java实现堆排序算法-详细分析

怼烎@ 2022-11-13 06:22 163阅读 0赞

## 前言 ##

**堆排序**  
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。子节点与父节点的关系决定了这个堆是最小堆还是最大堆，分别可以用来做升序和降序。是一种原地、时间复杂度为*nlogn*的排序算法。  
***堆的性质：***  
1.Complete Binary Tree(完全二叉树-生成节点的特点是从上到下，从左到右)；  
![完全二叉树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dRSF9Cb3Nz_size_16_color_FFFFFF_t_70_pic_center]  
2.parent >children（父节点的值大于子节点的值）；  
![堆][20210326091537990.png_pic_center]  
具备以上两点便可实现一个堆。

## 如何具体实现一个堆，具体思路如下： ##

**堆操作**  
从树变成堆的过程就叫做堆操作（heapify），具体过程可以理解为从下到上从右到左不断比较然后交换位置。  
对于一个乱的完全二叉树来说，我们只需要有序的不断做heapify，最终便可以得到一个堆（大顶堆/小顶堆）。  
![从第n-1层开始，从下到上依次做堆操作][n-1]  
对于一个整理好的堆来说，我们可以从给它的每个节点依次加一个index下标：  
![标索引][20210326092849219.png_pic_center]

然后便很容易得出结论：  
![结论][20210326093204267.png_pic_center]

**综上所诉**  
利用堆得这些性质与结论，正好符合一维数组的不变性与连续性，所以我们可以用在数组上从而实现数组的排序。

## 代码实现 ##

这里主要使用java代码实现

public class Heap1 { 
        //parent=(i-1)/2;
       //c1=2*i+1;
       // c2=2*i+2;
    
    
        //交换
        static void swap(int tree[],int i,int j){ 
            int temp=tree[i];
            tree[i]=tree[j];
            tree[j]=temp;
        }
    
        //堆操作（将树转为完全二叉树）
        static void heapify(int tree[],int n,int i){ 
            if (i >= n) { 
                return;
            }
    
            int c1=2*i+1;
            int c2=2*i+2;
            int max=i;
            //比较并判断是否出界
            if (c1<n && tree[c1]>tree[max]){ 
                max=c1;
            }
            if (c2<n && tree[c2]>tree[max]) { 
                max=c2;
            }
    
            if (max != i) { 
                swap(tree,max,i);
                heapify(tree, n, max);
            }
        }
    
        //创建堆
        static void build_heap(int tree[],int n){ 
            int last_node=n-1;
            int parent=(last_node-1)/2;
    
            for (int i = parent; i >=0 ; i--) { 
                heapify(tree,n,i);
            }
        }
    
        //排序
        static void heap_stor(int tree[],int n){ 
            build_heap(tree, n);
    
            for (int i =n-1; i >=0 ; i--) { 
                swap(tree,i,0);
                heapify(tree,i,0);
            }
        }
    
        public static void main(String[] args) { 
            int tree[]={ 5,6,8,2,1,9,7};
            int n=tree.length;
    
            //heapify(tree,n,0);
            //build_heap(tree,n);
            heap_stor(tree,n);
    
            for (int i = 0; i <n ; i++) { 
                System.out.println(tree[i]);
            }
        }
    }

到此小编的分享也就结束了，希望可以帮到你们，谢谢！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dRSF9Cb3Nz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/dc627c6d83ee43179788312663d4a5aa.png
[20210326091537990.png_pic_center]: /images/20221022/d82670fcb9a042e6bc9240d13332c665.png
[n-1]: /images/20221022/0a92eaf7352f4d4d97712b32e35905ee.png
[20210326092849219.png_pic_center]: https://img-blog.csdnimg.cn/20210326092849219.png#pic_center
[20210326093204267.png_pic_center]: https://img-blog.csdnimg.cn/20210326093204267.png#pic_center