JAVA算法起步之堆排序实例_java

学习堆排序,首先需要明白堆的概念,堆是一个数组。可以近似当做完全二叉树的数组存储方式。但是跟他还有其他的性质,就是类似于二叉排序树。有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小堆的是根节点的值小于其子节点的值。堆排序一般用的是最大堆,而最小堆可以构造优先队列。堆里面有一个方法是用来维护堆的性质,也就是我们下面代码中的maxheap方法,这是维护最大堆性质的方法,第一个参数就是堆也就是数组,第二个参数是调整堆的具体节点位置,可能这个节点的值不符合最大堆的性质,那么这个值得位置就作为参数,而size其实是堆内实际存储的有效元素个数。可能数组的长度就是堆内实际存储的元素个数,但是不一定所有的数据我们都需要进行构建最大堆。算法导论中说的得到左子结点是2xi但是我们数组是从0开始计数的,所以左子结点就成了2xi+1,buildheap就是构建一个最大堆,我们去2分之长度的原因是,这些点的子节点都是叶子节点,所以我们通过从下向上进行排序来构建一个最大堆。保证了我们堆内所有节点都满足最大堆性质。最后堆排序就是把第一个节点取出来,将剩下的节点再进行堆排序,再取出根节点。这样保证我们每次取出都是最大值。

复制代码 代码如下:

public class HeapSort {
 private int getLeft(int i){
  return 2*i+1;
 }
 private int getRight(int i){
  return 2*i+2;
 }
 public void maxheap(int[] heap,int loc,int size){
  int l=getLeft(loc);
  int r=getRight(loc);
  int largest=loc;
  if(l<size&&heap[l]>heap[loc]){
   largest=l;
  }
  if (r<size&&heap[r]>heap[largest]) {
   largest=r;
  }
  if(largest!=loc){
   int cache=heap[loc];
   heap[loc]=heap[largest];
   heap[largest]=cache;
   maxheap(heap, largest, size);
  }
 }
 public void buildheap(int[] heap){
  for(int i=heap.length/2;i>=0;i--){
   maxheap(heap, i, heap.length);
  }
 }
 public void sort(int[] heap){
  buildheap(heap);
  for(int i=heap.length-1;i>1;i--){
   int cache=heap[0];
    heap[0]=heap[i];
    heap[i]=cache;
   maxheap(heap, 0,i );
  }
  int cache=heap[0];
   heap[0]=heap[1];
   heap[1]=cache;

 }

 public static void main(String[] args) {
  int[] heap=new int[]{4,1,5,3,7,12,65,7};
  HeapSort hs=new HeapSort();
  hs.sort(heap);
  for (int i = 0; i < heap.length; i++) {
   System.out.println(heap[i]);
  }
 }
}

时间: 2024-11-16 03:14:29

JAVA算法起步之堆排序实例_java的相关文章

JAVA算法起步之快速排序实例_java

快速排序一听这个名字可能感觉很快,但是他的算法时间复杂度最坏情况却跟插入排序是一样的.之所以成为快速排序是因为他的平均效率比堆排序还要快,快速排序也是基于分治思想与归并排序差不多,但是快速排序是原址的,直接在原数组操作不需要再开辟新的存储空间.快速排序的思想很简单,就是选定一个关键字k将原数组分成两份g1与g2,g1中所有的元素都比k小或者相等,而g2中所有的数据都比k大或者等于,这样对g1与g2分别进行快速排序,最终我们得到的就是一个有序的数组.代码中的sort方法就是对刚才语句的描述.而关键

算法起步之堆排序

原文:算法起步之堆排序          学习堆排序,首先需要明白堆的概念,堆是一个数组.可以近似当做完全二叉树的数组存储方式.但是跟他还有其他的性质,就是类似于二叉排序树.有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小堆的是根节点的值小于其子节点的值.堆排序一般用的是最大堆,而最小堆可以构造优先队列.堆里面有一个方法是用来维护堆的性质,也就是我们下面代码中的maxheap方法,这是维护最大堆性质的方法,第一个参数就是堆也就是数组,第二个参数是调整堆的具体节点位置,可能这个节

java之Object类用法实例_java

本文实例讲述了java中Object类用法.分享给大家供大家参考.具体如下: 1.Object类是所有java类的基类 如果在类的声明中未使用extends关键字指明其基类,则默认基类为Object类,ex: public class Person{ ~~~~~ } 等价于 public class Person extends Object{ ~~~~~ } 2.Object类之equals方法 ①.Object类中定义有: public boolean equals(Object obj)方

JAVA 内部类详解及实例_java

JAVA 内部类 一.什么是内部类? 一个类的定义放在另一个类的内部,这个类就叫做内部类 二.内部类有那些特性? 1.内部类仍然是一个独立的类,在编译之后内部类会被编译成独立的.class文件,但是前面冠以外部类的类名和$符号 . 2.内部类不能用普通的方式访问.内部类是外部类的一个成员,因此内部类可以自由地访问外部类的成员变量,无论是否是private的 . 3.内部类声明成静态的,就不能随便的访问外部类的成员变量了,此时内部类只能访问外部类的静态成员变量 . 三.内部类有哪几种? 1.成员内

Java算法之递归算法计算阶乘_java

本文为大家分享的java算法计算阶乘,在学习Java课程时经常会遇到求阶乘问题,今天接跟大家一起探讨一下 代码如下: package com.xu.main; import java.util.Scanner; public class P9 { static long fact(int n) { if(n <= 1) { return 1; } else { return n * fact(n - 1); } } public static void main(String[] args) {

java自定义拦截器用法实例_java

本文实例讲述了java自定义拦截器及其用法.分享给大家供大家参考.具体如下: LoginInterceptor.java文件如下: package com.tq365.util; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpSession; import org.apache.struts2.ServletActionContext; import com.opensymphony.xwo

Java实现的并发任务处理实例_java

本文实例讲述了Java实现的并发任务处理方法.分享给大家供大家参考,具体如下: public void init() { super.init(); this.ioThreadPool = new ThreadPoolExecutor(50, 50, Long.MAX_VALUE, TimeUnit.SECONDS, new java.util.concurrent.LinkedTransferQueue<Runnable>(), new ThreadFactory() { AtomicLon

java针对电话号码正则匹配实例_java

本文实例讲述了java针对电话号码正则匹配的方法.分享给大家供大家参考.具体如下: public interface RegExpConst { /** * 手机号码 * 移动:134[0-8],135,136,137,138,139,150,151,157,158,159,182,187,188 * 联通:130,131,132,152,155,156,185,186 * 电信:133,1349,153,180,189 */ String MOBILE = "^1(3[0-9]|5[0-35-

JAVA时间日期处理类实例_java

本文实例讲述了JAVA时间日期处理类,主要用来遍历两个日期之间的每一天.分享给大家供大家参考.具体如下: /** * * 文 件 名: AccountDate.java * * 创建时间: 2008-11-18 * * Email : **@163.com */ import java.text.DecimalFormat; import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.A