插入法堆的java代码的简单介绍
如何根据一个数组建立最大堆
最大堆:根结点的键值是所有堆结点键值中最大者的堆。 最小堆:根结点的键值是所有堆结点键值中最小者的堆。 而最大-最小堆集结了最大堆和最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿子属于最大层。 以最大(小)层结n点为根结点的子树保有最大(小)堆性质:根结点的键值为该子树结点键值中最大(小)项。 主要操作不失一般性,只讨论根结点为最小层的情况。插入 只需要将节点插在二叉树的最后一个叶子结点位置,然后比较它对它父亲节点的大小,如果大则停止;如果小则交换位置,然后对父亲节点递归该过程直至根节点。复杂度为O(log(n))。 一般来说,插入的位置可以不是最后一个叶子节点,可以作为任意中间节点的孩子节点插入,将这个叶子节点变为中间节点后,按上文所说的方法调整节点顺序以保证维持堆特性不变。删除 要从堆中删除一个节点,用最后一个节点替换掉根节点,然后调整节点顺序以维持堆特性。建堆既可以用堆调整方法将原数组调整为一个堆,也可以借助往堆中插入元素的方法从无到有的建立一个堆。两种方法比较:(1)借助堆调整建堆的时间复杂度为O(n)。借助插入法建堆的时间复杂度为O(nlgn) ,书上第二问要求证明这个复杂度,但是我认为插入法的复杂度也是O(n),因为它和堆调整的区别在于针对每个节点i,堆调整是自上向下进行调整,插入法是自下向上进行调整。(2)对于同样的输入两个方法建立的堆可能不同。因为堆调整时,是i要跟它的两个子女进行比较,选出最大(小)的,但是插入x时,x只跟它的父节点进行比较。比如输入为2、3、4,堆调整建堆为4、3、2,插入法建堆为4、2、3。插入法建最大堆代码如下:
西城ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联公司的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:18982081108(备注:SSL证书合作)期待与您的合作!
public static void split(String source,int num) throws Exception{ int k=0; String temp="";
Java面向对象
1. super()与this()的区别?
This():当前类的对象,super父类对象。
Super():在子类访问父类的成员和行为,必须受类继承规则的约束
而this他代表当前对象,当然所有的资源都可以访问.
在构造函数中,如果第一行没有写super(),编译器会自动插入.但是如果父类没有不带参数的构造函数,或这个函数被私有化了(用private修饰).此时你必须加入对父类的实例化构造.而this就没有这个要求,因为它本身就进行实例化的构造.
而在方法中super和this使用的方法就差不多了.只不过super 要考虑是否能访问其父类的资源.
2. 作用域public,protected,private,以及不写时的区别?
Public:不同包、 同一包、 类内都可用
Private: 类内
Protected:不同包的子类、同一包、 类内都可用
不写时: 同一包内、类内
3. 编程输出如下图形。
* * * * *
* * * *
* * *
* *
*
代码如下:
public class Print {
publicstatic void main(String[] args) {
for(int i = 0; i 5; i++) {
for(int j = 5; j i; j--) {
System.out.print("*");
}
System.out.println();
}
}
}
4. JAVA的事件委托机制和垃圾回收机制
Java事件委托机制的概念,一个源产生一个事件并将它送到一个或多个监听器那里。在这种方案中,监听器简单的等待,直到它收到一个事件。一旦事件被接受,监听器将处理这个事件,然后返回。
垃圾回收机制垃圾收集是将分配给对象但不再使用的内存回收或释放的过程。如果一个对象没有指向它的引用或者其赋值为null,则次对象适合进行垃圾回收
5. 在JAVA中,如何跳出当前的多重嵌套循环?
用break; return 方法。
6. 什么是java序列化,如何实现java序列化?(写一个实例)
序列化:处理对象流的机制,所谓对象流也就是将对象的内容进行流化。可以对流化后的对象进行读写操作,也可将流化后的对象传输于网络之间。序列化是为了解决在对对象流进行读写操作时所引发的问题。
序列化的实现:将需要被序列化的类实现Serializable接口,该接口没有需要实现的方法,implementsSerializable只是为了标注该对象是可被序列化的,然后使用一个输出流(如:FileOutputStream)来构造一个ObjectOutputStream(对象流)对象,接着,使用ObjectOutputStream对象的writeObject(Object obj)方法就可以将参数为obj的对象写出(即保存其状态),要恢复的话则用输入流。
7. 一个".java"源文件中是否可以包括多个类(不是内部类)?有什么限制?
可以。如果这个类的修饰符是public,其类名与文件名必须相同。
8. 排序都有哪几种方法?请列举。用JAVA实现一个快速排序?
排序的方法有:插入排序(直接插入排序、希尔排序),交换排序(冒泡排序、快速排序),选择排序(直接选择排序、堆排序),归并排序,分配排序(箱排序、基数排序)
快速排序的伪代码。
9. Overload和Override的区别。Overloaded的方法是否可以改变返回值的类型?
重写Override,子类覆盖父类的方法,将子类传与父类的引用调用的还是子类的方法。
重载Overloading 一个类多个方法,名称相同,参数个数类型不同。
两者都是Java多态性的不同表现。
Overloaded的方法是可以改变返回值的类型。
1, public class Ctest(){
Public static void main(){
System.out.prinln(8+8+”88”+8+8);
}
} 168888
(方法的重写Overriding和重载Overloading是Java多态性的不同表现。重写Overriding是父类与子类之间多态性的一种表现,重载Overloading是一个类中多态性的一种表现。如果在子类中定义某方法与其父类有相同的名称和参数,我们说该方法被重写 (Overriding)。子类的对象使用这个方法时,将调用子类中的定义,对它而言,父类中的定义如同被“屏蔽”了。如果在一个类中定义了多个同名的方法,它们或有不同的参数个数或有不同的参数类型,则称为方法的重载(Overloading)。
Overloaded的方法是可以改变返回值的类型。)
10. Final类有什么特点?
属性常量 方法不可以overridding 类不可以继承
11. 继承时候类的执行顺序问题,一般都是选择题,问你将会打印出什么?
答:父类:
package test;
public class FatherClass {
public FatherClass() {
System.out.println("FatherClassCreate");
}
}
子类:
package test;
import test.FatherClass;
public class ChildClass extends FatherClass{
public ChildClass() {
System.out.println("ChildClassCreate");
}
public static void main(String[] args) {
FatherClass fc = new FatherClass();
ChildClass cc = new ChildClass();
}
}
输出结果:
C:java test.ChildClass
FatherClass Create
FatherClass Create
ChildClass Create
12. 内部类的实现方式?
package test;
public class OuterClass {
private class InterClass {
Public Interlass(){
System.out.println("InterClassCreate");
}
}
public OuterClass(){
InterClass ic = new InterClass();
System.out.println("OuterClassCreate");
}
public static void main(String[] args){
OuterClass oc = new OuterClass();
}
}
输出结果:
C:java test/OuterClass InterClass Create OuterClass Create
13. 用JAVA实现一种排序,JAVA类实现序列化的方法(二种)?
14. 如在COLLECTION框架中,实现比较要实现什么样的接口?
15. 用插入法进行排序代码如下
package test;
import java.util.*;
class InsertSort {
ArrayList al;
public InsertSort(int num,int mod) {
al = new ArrayList(num);
Random rand = new Random();
System.out.println("The ArrayList SortBefore:");
for (int i=0;inum ;i++ ){
al.add(new Integer(Math.abs(rand.nextInt())% mod + 1));
System.out.println("al["+i+"]="+al.get(i));
}
}
public void SortIt(){
Integer tempInt;
int MaxSize=1;
for(int i=1;ial.size();i++){
tempInt = (Integer)al.remove(i);
if(tempInt.intValue()=((Integer)al.get(MaxSize-1)).intValue()){
al.add(MaxSize,tempInt);
MaxSize++;
System.out.println(al.toString());
} else {
for (int j=0;jMaxSize ;j++ ){
if(((Integer)al.get(j)).intValue()=tempInt.intValue()){
al.add(j,tempInt);
MaxSize++;
System.out.println(al.toString());
break;
}
}
}
}
System.out.println("The ArrayList SortAfter:");
for(int i=0;ial.size();i++) {
System.out.println("al["+i+"]="+al.get(i));
}
}
public static void main(String[] args) {
InsertSort is = new InsertSort(10,100);
is.SortIt();
}
}
JAVA类实现序例化的方法是实现java.io.Serializable接口
Collection框架中实现比较要实现Comparable 接口和 Comparator 接口
16. 编程:编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串。但是要保证汉字不被截半个,如"我ABC"4,应该截为"我AB",输入"我ABC汉DEF",6,应该输出为"我ABC"而不是"我ABC+汉的半个"。
public static void split(String source,intnum) throws Exception{
intk=0;
Stringtemp="";
for(int i = 0; i source.length(); i++){
byte[]b=(source.charAt(i)+"").getBytes();
k=k+b.length;
if(knum){
break;
}
temp=temp+source.charAt(i);
}
System.out.println(temp);
}
15、Java编程,打印昨天的当前时刻
public class YesterdayCurrent{
public void main(String[] args){
Calendar cal = Calendar.getInstance();
cal.add(Calendar.DATE, -1);
System.out.println(cal.getTime());
}
}
16、文件读写,实现一个计数器
public int getNum(){
int i = -1;
try{
String stri="";
BufferedReader in = new BufferedReader(newFileReader(f));
while((stri=in.readLine())!=null){
i = Integer.parseInt(stri.trim());
}
in.close();
}catch(Exception e){
e.printStackTrace();
}
return i;
}
public void setNum(){
int i = getNum();
i++;
try{
PrintWriter out=new PrintWriter(newBufferedWriter(new FileWriter(f,false)));
out.write(String.valueOf(i)); //可能是编码的原因,如果直接写入int的话,将出现java编码和windows编码的混乱,因此此处写入的是String
out.close() ;
}catch(Exception e){
e.printStackTrace();
}
}
17、指出下面程序的运行结果。
class A{
static{
System.out.print("1");
}
public A(){
System.out.print("2");
}
}
class B extends A{
static{
System.out.print("a");
}
public B(){
System.out.print("b");
}
}
public class Hello{
public static void main(String[] ars){
A ab = new B(); //执行到此处,结果: 1a2b
ab = new B(); //执行到此处,结果: 1a2b2b
}
}注:类的static 代码段,可以看作是类首次加载(被虚拟机加载)执行的代码,而对于类的加载,首先要执行其基类的构造,再执行其本身的构造
18、抽象类和接口的区别?
(1)接口可以被多重implements,抽象类只能被单一extends(2)接口只有定义,抽象类可以有定义和实现(3)接口的字段定义默认为:publicstatic final, 抽象类字段默认是"friendly"(本包可见)
当功能需要累积时用抽象类,不需要累积时用接口。
19、什么是类的反射机制?
通过类(Class对象),可以得出当前类的fields、method、construtor、interface、superClass、modified等,同是可以通过类实例化一个实例、设置属性、唤醒方法。Spring中一切都是返射、struts、hibernate都是通过类的返射进行开发的。
20、类的返射机制中的包及核心类?
①java.lang.Class②java.lang.refrection.Method③java.lang.refrection.Field
④java.lang.refrection.Constructor⑤java.lang.refrection.Modifier⑥java.lang.refrection.Interface
21、得到Class的三个过程是什么?
①对象.getClass()②类.class或Integer.type(int) Integer.class(java.lang.Integer)③Class.forName();
22、如何唤起类中的一个方法?
①产生一个Class数组,说明方法的参数②通过Class对象及方法参数得到Method③通过method.invoke(实例,参数值数组)唤醒方法
23、如何将数值型字符转换为数字(Integer,Double)?
Integer.parseInt(“1234”) Double.parseDouble(“123.2”)
24、如何将数字转换为字符?
1+”” 1.0+””
25、如何去小数点前两位,并四舍五入。
double d=1256.22d; d=d/100; System.out.println(Math.round(d)*100);
26、如何取得年月日,小时分秒?
Calendar c=Calendar.getInstance();
c.set(Calendar.YEAR,2004);
c.set(Calendar.MONTH,0);
c.set(Calendar.DAY_OF_MONTH,31);
System.out.println(c.get(Calendar.YEAR)+" "+(c.get(Calendar.MONTH)+1)+" "+c.get(Calendar.DAY_OF_MONTH));
27、如何取得从1970年到现在的毫秒数
Java.util.Date dat=new Date(); long now=dat.getTime();
或System.currentTimeMillis()
28、如何获取某个日期是当月的最后一天?
当前日期加一天,若当前日期与结果的月份不相同,就是最后一天。
取下一个月的第一天,下一个月的第一天-1
public static void main(String[] args){
Calendarc=Calendar.getInstance();
c.set(Calendar.YEAR,2004);
c.set(Calendar.MONTH,0);
c.set(Calendar.DAY_OF_MONTH,30);
Calendarc1=(Calendar)c.clone();
System.out.println(c.get(Calendar.YEAR)+""+(c.get(Calendar.MONTH)+1)+" "+c.get(Calendar.DAY_OF_MONTH));
c.add(Calendar.DAY_OF_MONTH,1);
if(c.get(Calendar.MONTH)!=c1.get(Calendar.MONTH)){
System.out.println("是最后一天");
}else{
System.out.println("不是取后一天");
}
}
29、如何格式化日期?
Import java.text. SimpleDateFormat;
SimpleDateFormat sdf=newSimpleDateFormat("yyyy-MM-dd hh:mm:ss");
Date dat=new Date();
String str=sdf.format(dat); //把日期转化为字符串
System.out.println(str);
Java.util.Date d1=sdf.parse(“yyyy-mm-dd”); //将字符串转化为日期
30、编码转换,怎样实现将GB2312编码的字符串转换为ISO-8859-1编码的字符串。
String a=new String("中".getBytes("gb2312"),"iso-8859-1");
String a=new String("中".getBytes("iso-8859-1"));
应该是String a=new String("中".getBytes("gb2312"),"iso-8859-1");
String a1=newString(a.getBytes("iso-8859-1"));
插入法排序
用插入法进行排序代码如下
package test;
import java.util.*;
class InsertSort
{
ArrayList al;
public InsertSort(int num,int mod)
{
al = new ArrayList(num);
Random rand = new Random();
System.out.println("The ArrayList Sort Before:");
for (int i=0;inum ;i++ )
{
al.add(new Integer(Math.abs(rand.nextInt()) % mod + 1));
System.out.println("al["+i+"]="+al.get(i));
}
}
public void SortIt()
{
Integer tempInt;
int MaxSize=1;
for(int i=1;ial.size();i++)
{
tempInt = (Integer)al.remove(i);
if(tempInt.intValue()=((Integer)al.get(MaxSize-1)).intValue())
{
al.add(MaxSize,tempInt);
MaxSize++;
System.out.println(al.toString());
} else {
for (int j=0;jMaxSize ;j++ )
{
if
(((Integer)al.get(j)).intValue()=tempInt.intValue())
{
al.add(j,tempInt);
MaxSize++;
System.out.println(al.toString());
break;
}
}
}
}
System.out.println("The ArrayList Sort After:");
for(int i=0;ial.size();i++)
{
System.out.println("al["+i+"]="+al.get(i));
}
}
public static void main(String[] args)
{
InsertSort is = new InsertSort(10,100);
is.SortIt();
}
}
JAVA类实现序例化的方法是实现java.io.Serializable接口
Collection框架中实现比较要实现Comparable 接口和 Comparator 接口
用JAVA编写插入法对一个给定数组进行升序排序的方法
//用冒泡,就是for循环里加if判断就行了。
class Test{
public static void main(String [] args){
int a[10]={2,1,4,5,6,7,8,9,23,44};
for (i=0;ia.length;i++)
{
for (j=0;ja.length-1-i;j++)
{
if (a[j]a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for (i=0;ia.length;i++){
System.out.println(a[i]);
}
}
}
当前题目:插入法堆的java代码的简单介绍
URL标题:http://azwzsj.com/article/doseese.html