java的堆排序是什么意思?-创新互联
本篇文章给大家带来的内容是java中什么是堆排序?堆排序介绍。有一定的参考价值,有需要的朋友可以参考一下,希望对你们有所帮助。
成都创新互联专注于企业网络营销推广、网站重做改版、泰山网站定制设计、自适应品牌网站建设、HTML5建站、商城开发、集团公司官网建设、成都外贸网站制作、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为泰山等各大城市提供网站开发制作服务。堆排序介绍:
堆排序可以分为两个阶段。在堆的构造阶段,我们将原始数组重新组织安排进一个堆中;然后在下沉排序阶段,我们从堆中按顺序取出所有元素并得到排序结果。
1.堆的构造,一个有效的方法是从右到左使用sink()下沉函数构造子堆。数组的每个位置都有一个子堆的根节点,sink()对于这些子堆也适用,如果一个节点的两个子节点都已经是堆了,那么在该节点上调用sink()方法可以把他们合并成一个堆。我们可以跳过大小为1的子堆,因为大小为1的不需要sink()也就是下沉操作,有关下沉和上浮操作可以参考我写的优先队列那篇。
2.堆的排序,我们通过第一步操作构造了一个堆,在这个堆中,根节点永远是大值的节点,所以我们把根节点的值与数组最后的值进行交换,在使用sink()下沉来维护堆的结构即可。具体代码实现:
public class PQSort{ public static void main(String[] args){ int[] a = {9,1,7,5,3,9,12,56,21,45}; sort(a); for(int i=0;i=0;k--){ sink(a,k,N); } //通过不断把堆中大值放到数组的后面来排序 while(N>0){ exch(a,0,N--); sink(a,0,N); } } //下沉函数 private static void sink(int[] a, int i, int n){ while(2*i+1<=n){ int j = 2*i+1; if(j a[j]) break; exch(a,i,j); i=j; } } //交换函数 private static void exch(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } }
运行结果:
以上就是java中什么是堆排序?堆排序介绍的详细内容,更多请关注创新互联成都网站设计公司其它相关文章!
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章题目:java的堆排序是什么意思?-创新互联
本文地址:http://myzitong.com/article/ccchhj.html