堆的定义: 堆是这样一种表,其中每个元素均包含一个键值,表中位置k的元素键值至少与位置2k+1的元素(如果存在)或位置2k+2的元素(如果存在)的键值一样大。
构建堆的时间复杂度O(n)
调整堆的时间复杂度O(log2n)
堆排序时间复杂度O(nlog2n)
堆排序不稳定
public class HeapSort { private void heapify(int arr[],int low, int high){ int largeIndex; int temp=arr[low]; largeIndex=2*low+1; while(largeIndex<=high){ if(largeIndex<high){ if(arr[largeIndex]<arr[largeIndex+1]) largeIndex=largeIndex+1; } if(temp>arr[largeIndex])break; else{ arr[low]=arr[largeIndex]; low=largeIndex; largeIndex=2*low+1; } arr[low]=temp; } } private void buildHeap(int arr[]){ int index; int length=arr.length; for(index=length/2-1;index>=0;index--){ heapify(arr, index, length-1); } } public void heapSort(int arr[]){ int lastOutOfOrder; int temp; int length=arr.length; buildHeap(arr); for(lastOutOfOrder=length-1;lastOutOfOrder>=0;lastOutOfOrder--){ temp=arr[lastOutOfOrder]; arr[lastOutOfOrder]=arr[0]; arr[0]=temp; heapify(arr, 0, lastOutOfOrder-1); } } public static void main(String[] args) { HeapSort hs=new HeapSort(); int arr[] = { 2, 568, 34, 46, 9, 23, 89, 43, 572, 684, 783, 543 }; hs.heapSort(arr); for (int i = 0; i < 12; i++) { System.out.print(arr[i] + ","); } // 2,9,23,34,43,46,89,543,568,572,684,783, } }
堆排序的步骤:
1.构建堆
假定length表示表的长度,令index=length/2-1,那么arr[index]是最后一个非叶节点,
元素arr[index+1]…arr[legth-1]都是叶节点。
将包含根节点arr[index]的子树转换为一个堆,然后将包含根节点arr[index-1]的子树转换为一个堆,
直至把包含根节点arr[0]的数转换成一个堆
2.堆排序
图解:
相关推荐
06-Java基础(数组-内存图解)
JavaSE基础篇——jdk配置,数组及其应用,栈和堆内存图解,java实现源码,更多内容请见http://blog.csdn.net/zhongkelee
Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解教程Java图解...
数组知识梳理
java设计模式-图解-附代码
Java设计模式-图解-附代码,举例子的方式剖析所有设计模式,更容易理解。
小樱桃格式的Java初级篇格式,如果需要小樱桃软件的可以私聊我,不需要关注哦,私聊即可
基于MATLAB的图解粒度参数计算.pdf
Java设计模式 图解 附代码
非常好的Java入门图解教程 非常好的Java入门图解教程
图解java4 很好表达java语言与概念。
java高并发解决方案(图解).xmind,仅用学习使用,不可用于商业用途,如有版权问题,请联系删除!
Java图解教程.rarJava图解教程.rarJava图解教程.rarJava图解教程.rarJava图解教程.rarJava图解教程.rarJava图解教程.rar
全书内容浅显易懂,利用大量且丰富的图示与范例, 详解复杂的抽象理论,从最基本的数据结构概念开始 说明,再以Java工具加以诠释阵列结构、堆栈、链表 、队列、排序、查找等重要的概念,引领读者抓住重 点轻松进入...
很好的java设计模式文档,很详细,内附代码
java-设计模式+部分图解
Java设计模式-图解-附代码
2023年java工程师面试宝典(附BAT大厂真题),400MB的真题祝你早日进入大厂 本套面宝典包括了: 1. Java基础知识的汇总 2.设计模式的常见面试题汇总 3.消息队列常见面试题 4.RockMQ从入门到实战 5.图解操作系统 6....