Java算法之堆排序代码示例
堆是一种特殊的完全二叉树，其特点是所有父节点都比子节点要小，或者所有父节点都比字节点要大。前一种称为最小堆，后一种称为最大堆。
比如下面这两个：
那么这个特性有什么作用？既然题目是堆排序，那么肯定能用来排序。想要用堆排序首先要创建一个堆，如果对4 3 6 2 7 1 5这七个数字做从小到大排序，需要用这七个数创建一个最大堆，来看代码：
public class HeapSort {
private int[] numbers;
private int length;
public HeapSort(int[] numbers) {
this.numbers = numbers;
this.length = numbers.length;
}
/**
* 调整二叉树
* 如果父节点编号为x, 那么左子节点的编号是2x, 右子节点的编号是2x+1
* 节点编号从1开始, 对应数组中的索引是编号-1
* @param nodeId 节点编号, 从1开始
*/
public void adjust(int nodeId) {
int swapId;
int flag = 0; //是否需要继续向下调整
while(nodeId * 2 <= this.length && flag == 0) {
//首先判断它和左子节点的关系, 并用swapId记录值较小的节点编号(最大堆是记录较大的)
int index = nodeId - 1; //节点对应数组中数字的索引
int leftChild = nodeId * 2 - 1; //左子节点对应数组中数字的索引
int rightChild = nodeId * 2; //右子节点对应数组中数字的索引
if(numbers[index] < numbers[leftChild]) {
swapId = nodeId * 2;
} else {
swapId = nodeId;
}
//如果有右子节点, 再与右子节点比较
if(nodeId * 2 + 1 <= this.length) {
if(numbers[swapId - 1] < numbers[rightChild])
swapId = nodeId * 2 + 1;
}
//如果最小的节点编号不是自己, 说明子节点中有比父节点更小的
if(swapId != nodeId) {
swap(swapId, nodeId);
nodeId = swapId;
} else {
flag = 1;
}
}
}
/**
* 交换两个节点的值
* @param nodeId1
* @param nodeId2
*/
public void swap(int nodeId1, int nodeId2) {
int t = numbers[nodeId1 - 1];
numbers[nodeId1 - 1] = numbers[nodeId2 - 1];
numbers[nodeId2 - 1] = t;
}
/**
* 创建最大堆
*/
public void createMaxHeap() {
//从最后一个非叶节点到第一个节点依次向上调整
for(int i = this.length / 2; i >= 1; i--) {
adjust(i);
}
}
public static void main(String[] args) {
int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };
for(int x = 0; x < numbers.length; x++) {
System.out.print(numbers[x] + " ");
}
System.out.println();
HeapSort heap = new HeapSort(numbers);
heap.createMaxHeap();
}
}
对本例中的数列，从this.length / 2到1，共执行了三轮循环。
第一轮：
第二轮：
第三轮：
调整完成后，当前的二叉树已经符合最大堆的特性，可以用来从小到大排序。堆排序的原理是，交换堆顶和最后一个节点的数字，即把最大的数字放到数组最后，然后对除了最大数的前n-1个数从新执行调整过程，使其符合最大堆特性。重复以上过程直到堆中只剩下一个数字。
public void sort() {
while(this.length > 1) {
swap(1, this.length);
this.length--;
adjust(1);
}
for(int x = 0; x < numbers.length; x++) {
System.out.print(numbers[x] + " ");
}
}
堆排序的时间复杂度和快速排序的平均时间复杂度一样，是O(nlogn)。
总结
以上就是本文关于Java算法之堆排序代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：java实现的各种排序算法代码示例、Java遗传算法之冲出迷宫等，有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！
相关推荐
-
Java数据结构及算法实例：考拉兹猜想 Collatz Conjecture
/** * 考拉兹猜想:Collatz Conjecture * 又称为3n+1猜想.冰雹猜想.角谷猜想.哈塞猜想.乌拉姆猜想或叙拉古猜想, * 是指对于每一个正整数,如果它是奇数,则对它乘3再加1, * 如果它是偶数,则对它除以2,如此循环,最终都能够得到1. */ package al; public class CollatzConjecture { private int i = 1; public static void main(String[] args) { long l = 9
-
Java数据结构及算法实例：选择排序 Selection Sort
/** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements
-
Java数据结构及算法实例：插入排序 Insertion Sort
/** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert
-
Java创建树形结构算法实例代码
在JavaWeb的相关开发中经常会涉及到多级菜单的展示,为了方便菜单的管理需要使用数据库进行支持,本例采用相关算法讲数据库中的条形记录进行相关组装和排序讲菜单组装成树形结构. 首先是需要的JavaBean import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Date; import j
-
java实现Fibonacci算法实例
本文实例讲述了java实现Fibonacci算法的方法.分享给大家供大家参考.具体如下: package com.yenange.test2; import java.util.Scanner; public class Fibonacci { private static Scanner input = new Scanner(System.in); public static void main(String[] args) { System.out.println("-----------
-
Java数据结构及算法实例：快速计算二进制数中1的个数(Fast Bit Counting)
/** * 快速计算二进制数中1的个数(Fast Bit Counting) * 该算法的思想如下: * 每次将该数与该数减一后的数值相与,从而将最右边的一位1消掉 * 直到该数为0 * 中间循环的次数即为其中1的个数 * 例如给定"10100",减一后为"10011",相与为"10000",这样就消掉最右边的1 * Sparse Ones and Dense Ones were first described by Peter Wegner i
-
Java实现二分查找算法实例分析
本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合
-
Java数据结构及算法实例：冒泡排序 Bubble Sort
/** * 冒泡排序估计是每本算法书籍都会提到的排序方法. * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列. * 第1趟将最大的元素排在序列尾部,第2趟将第2大的元素排在倒数第二的位置, * 即每次把未排好的最大元素冒泡到序列最后端. * 该排序方法实际上分为两重循环,外层循环:待排元素从数组的第1个元素开始. * 内层循环:待排元素从数组的第1个元素开始,直到数组尾端未排过的元素. * 在内循环中,如果遇到前面元素比其后的元素大就交换这两个元素的位置. * 由此可见冒泡排序的复杂
-
Java算法之堆排序代码示例
堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor
-
Java语言字典序排序算法解析及代码示例
字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的
-
Go Java算法之同构字符串示例详解
目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &
-
java tostring方法重写代码示例
当需要将一个对象输出到显示器时,通常要调用他的toString()方法,将对象的内容转换为字符串.java中的所有类默认都有一个toString()方法 默认情况下 System.out.println(对象名)或者System.out.println(对象名.toString())输出的是此对象的类名和此对象对应内存的首地址 如果想自定义输出信息必须重写toString()方法 注意事项 1.必须被声明为public 2.返回类型为String 3.方法的名称必须为toString,且无参数
-
Java中Switch用法代码示例
一.java当中的switch与C#相比有以下区别 注:在java中switch后的表达式的类型只能为以下几种:byte.short.char.int(在Java1.6中是这样), 在java1.7后支持了对string的判断 还有一点要注意的是:在java中如果switch的case语句中少写了break;这个关键字,在编译的时候并没有报错.但是在执行的时候会一直执行所有case条件下的语句并不是去判断,所以会一直执行直到遇到break关键字跳出或者一直执行到defaut语句. 还有就是如果
-
Java编程异常简单代码示例
练习1 写一个方法void triangle(int a,int b,int c),判断三个参数是否能构成一个三角形.如果不能则抛出异常IllegalArgumentException,显示异常信息:a,b,c "不能构成三角形":如果可以构成则显示三角形三个边长.在主方法中得到命令行输入的三个整数,调用此方法,并捕获异常. 两边之和大于第三边:a+b>c 两边之差小于第三边:c-a package 异常; import java.util.Arrays; import java
-
java编程队列数据结构代码示例
队列是一种特殊的线性表,只允许在表的前端进行删除,在表的后端进行插入,表的前端称为(front)队头,表的后端称为(rear)队尾. 所以队列跟生活的场景很是相似,在电影院买电影票,人们排成一排,第一个人进入队尾最先到达队头后买票进入影院,后面排队的人按照排队的次序买到票后进入影院. 所以 队列是一种先进先出的数据结构(FIFO). 编程实现对循环链队列的入队和出队操作. ⑴根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列(循环链队列),并且只设一个尾指针来指向尾结点,然后输出
-
java自定义类加载器代码示例
如果要使用自定义类加载器加载class文件,就需要继承java.lang.ClassLoader类. ClassLoader有几个重要的方法: protectedClassLoader(ClassLoaderparent):使用指定的.用于委托操作的父类加载器创建新的类加载器. protectedfinalClass<?>defineClass(Stringname,byte[]b,intoff,intlen):将一个byte数组转换为Class类的实例. protectedClass<
-
Java动态编译执行代码示例
在某些情况下,我们需要动态生成java代码,通过动态编译,然后执行代码.JAVAAPI提供了相应的工具(JavaCompiler)来实现动态编译.下面我们通过一个简单的例子介绍,如何通过JavaCompiler实现java代码动态编译. 一.获取JavaCompiler JavaCompiler compiler = ToolProvider.getSystemJavaCompiler(); 获取JDK提供的java编译器,如果没有提供编译器,则返回null: 二.编译 //获取java文件管理
-
Java递归算法遍历部门代码示例
递归是一个非常有用的知识点.写点实例帮助自己记忆 中间有过程代码 首先一个javapojo类 package com.qcf.po; import java.util.HashSet; import java.util.Set; public class Depart { private long id; private String name; private String destion; //用户 Set<User> users=new HashSet<User>(); //