Java基础(5)

查找算法：折半查找法

冒泡排序是一种稳定的排序算法

• 时间复杂度为O(n**2)
• 空间复杂度为O(1)

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的时间复杂度为O(nlogn)。如果不考虑递归问题的化空间复杂度为O(1)。
快速排序也是一种稳定的算法。

1、从数列中挑出一个元素，称为"基准"(pivot);
2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面 (相同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区 (partition)操作；
3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序；

数组：[4,7,1,8,10,6,5,3,7,9]

1、pivot=4 start=O end=9

low=0 high=9 pivot=4=arr[low]
首先从高端部分开始进行比较，保证高端部分比pivot大。如果值比4大，则high--
high=7 此时high指针执行的值比pivot小，arr[low]=arr[high]
[3,7,1,8,10,6,5,3,7,9] low=0 high=7 pivot=4

开始比较低端，从low执行的数据开始进行比较，直到有数据比pivot大为止
如果low指向的数据比pivot小，则low++
low=1时对应的数据为7,比pivot大，则arr[high]=arr[low]
[3,7,1,8,10,6,5,7,7,9] low=1 high=7 pivot=4

一轮比对完成的结束条件应该时low>=high,当前low=1 < high=7

继续高端比较，比较方式同第一次高端比较
high-- 具体值为2, arr[high]3所以high--   low=0   high=1
2、arr[high] 
具体编码实现 
public static void main(string[] args) { 
	int[] arr=new int[] {3,7,1,8,10,6,5,3,7,9};
	quicksort(arr, 0, arr.length-1);
	for(int tmp:arr) {
		System.out.print(tmp+"t");
		}
	}
	
public static void quickSort(int[] arr, int start, int end) {
	if (start < end) {
		int pivot = arr[start];
		int low = start;
		int high = end;

		while (low < high) {
			while (low < high && arr[high] >= pivot) {
				high--;
			}
			arr[low] = arr[high];
			while (low < high && arr[low] <= pivot) {
				low++;
			}
			arr[high] = arr[low];
		}
		arr[low] = pivot;
		quickSort(arr, start, low);
		quickSort(arr, low + 1, end);
	}
}
 
语法基础 
final关键字 
最终的，不可变的
 
修饰变量 
final变量一旦初始化，则不允许修改
 
属性 
在构建对象时final属性行赋值，不管采用的的是直接赋值、非静态代码块赋值、构造器赋值三种方法中的哪一种，重点是一旦赋值不允许修改
 
final String name = "df"; //指定final属性必须给出一个初始化，否则报错 
final String name1;
final Integer age; //初始化可以直接赋值，也可以在代码块中进行赋值或者在构造器中 进行赋值
final Date birth;
{ //代码块，不管执行的是哪个构造器，这个代码块一定执行 
age = 100;
}

public A1() {
	birth = new Date();
	namel="birth"; 
}

public A1(String name1) { 
	birth = new Date()；
//	age=99;语法报错的原因是非静态代码块中已经对age属性进行赋值，在构造器中赋值属于2次赋值，所以报错
	this.name1=name1; //fi nal属性也可以通过构造器的参数进行赋值，不是必须为字面量
}

public void pp() {
// name="df";报错的原因是final属性一旦赋值则不允许修改 }
}
 
局部变量 
局部变量要求声明的同时必须赋初始值，也可以先声明后赋值，但是在使用之前必须赋值，而且一旦赋值不能修改
 
public static void main(String[] args) { 
	A1 aa=new A1();
	//针对行nal类型的形参可以传递不同的数据
	aa.dd(1); 
	aa.dd(100);
}

class A1(){
	public void cc(int kk) { 
		final int bb=123;
		final String num; //先声明后赋值
		if (kk % 2 == 0) 
			num = "abc";
		else 
			num = "ccc";
		// num="ddd"；语法报错 
		System.out.println(num);
		}
		public void dd(final int kk) { 
		//语法正确，表示kk这个值只能在调用时传入数 据，在方法内部不允许修改
		//	kk++;语法报错
	}
}
 
修饰方法 
不允许继承修改
 
class A2 { 
	public void pp() { 
		System.out.println("A2...ppn");
	}
	public final void cc() { //final表示不允许修改定义 
		System.out.println("A2...cc");
	}
}

class B2 extends A2 { 
	public void pp() { //覆盖定义父类中方法
		System.out.println("B2.. .pp11");
	}
// public final void cc() {} 语法错误
}
 
修改类定义 
不允许继承
 
final class A3 { //final类不允许被继承
}

class B3 extends A3 {//语法错误
}
 
重要提示 
由于String、StringBuffer、StringBuilder之类的类型定义是final类型的，所以不允许通过继承的方式重新定义
 
public final class String 
	implements java.io.serializable, comparable, charsequence, Constable, ConstantDesc
	
class A extends String{} //语法错误
 
总结 
final属性上可以声明的同时进行赋值，也可以在构造器或者非静态代码块中进行赋值。一旦赋值不允许修改。
final局部变量可以在声明的同时机型赋值，也可以在第一次使用之前进行赋值。一旦赋值不允许修改。
final针对复杂类型表示的是不允许修改引用，而不是不允许修改引用对象中的属性。
 
public class Person{ 
	String name; int age;
}

final Person p=new Person();	//语法正确，p存放的是Person对象的具体地址一引用值，final表示引用值不允许修改
//p=new Personf);语法错误，这是因为给p变量重新赋值，这是不允许的
p.setName("解放路")；//修改属性，并没有修改p变量的地址，所以这是允许的
 
final方法表示这个方法不允许在子类中覆盖定义。子类中只能继承父类中的final方法，但是不允许子类中重新定义。
final类表示这个类不允许继承。
 
不允许继承的其它实现方式 
class A4 { 
	private A4() { 
		System.out.println("A4构造器");
	}
}

class B4 extends A4 { 
	public B4() { //出现问题，因为A4的构造器无法访问 
		System.out.println("B4 构造器");
	}
}
 
static关键字 
修饰属性 
静态属性用于表示某个类的所有对象共享的属性。注意：一般的非静态属性各个对象之间是隔离的，没有任何关系。
 
public class A{
	private static int count=0; //定义静态属性
}
 
需求：统计某个类的创建次数 
public class A{ 
	private static int count=0; //由于static静态属性，所以这个属性是当前类A的所有 对象所共享，任何一个对象修改属性，导致所有的对象这个属性值都进行了修改
	public A(){ 
		count++; 
		}
	public int getCount(){ 
		return count;
	}
}
 
具体编码 
public static void main(string[] args) { 
	A5[] arr=new A5[10];
	for(int i=0;i<10;i++)
		arr[i]=new A5();
	System.out.println(arr[3].getcount());
	System.out.println(arr[9] .getCount(); 
}

class A5{
	private static int count=0;
	public A5() { 
		count++;
	}
	public int getCount() { 
		return count;
	}
}
 
执行顺序 
创建了10个B1对象，但是所有B1对象的公共属性aa只创建一次
 
public static void main(string]] args) { 
	for(int i = 0; i < 10; i++)
		new B1();
	}
}

class A1 { 
	public A1() { 
		System.out.println("A1...")
	}
}

class B1 { 
	private static A1 aa = new A1();
}
 
修饰方法 
可以直接通过【类名.方法名】的形式进行调用
 
public class A{
	public void pp(){} //成员方法，进行调用必须通过【new A().pp()】
	public static void cc(){} //静态成员方法，可以通过【A.cc()】进行调用，当然也可以 通过【new A().pp()】进行调用，一般建议使用类名称进行调用
}
 
静态方法只能直接访问静态成员
 
public class A{ 
	private int age; 
	private static String name;
	
	public static void cc(){
		System.out.println(age) //语法报错，因为静态方法只能访问静态成员
		System.out.println(new A().age); //如果需要访问非静态成员，必须构 建实例，通过实例进行访问
		System.out.println(name); //正确
		PP(); //语法报错，因为静态方法只能直接访问静态成员 
		new A().PP(); //如果需要访问非静态成员，必须构建实例，通过实例进行访问 
		dd();//正确
	}
	public void pp(){ 
		System.out.println(name) 
	}
	public static void dd(){}
}
 
静态代码块 
在类加载完成之后，在构建对象之前，自动执行的代码段，这个代码段在对象的声明周期中只能执行一次。除非有新的加载动作，否则不会二次执行，因为匿名的原因，也没有办法显式调用
 
public class A{
	static	{	//类内所有方法之外
		System.out.println（"静态代码块"）；
	}
	
	static	{	//允许定义多次
		system .out.printin（"静态代码块2"）;
	}
	
	{
		System.out.println（"非静态代码块"）;
	}
}
 
设计模式 
设计模式是由专家总结出来的在某种情况下针对某种问题的最佳解决方案，是思想，是知识。
四人组总计出来的JavaSE中相关的设计模式有23种，三大类。
 
单例模式singleton 
保证在JVM中一个类有且仅有一个实例，并提供一个统一的全局访问点
 单例模式有多种写法，最常见的是饿汉模式和懒汉模式
 
饿汉模式 
优点：没有加锁处理，执行效率比较高；
 缺点：在类加载阶段完成对象的初始化操作，不管是否需要使用，浪费内存。
 编程实现的思路：
 
私有构造器，不允许除了当前类内之外的其它地方创建对象
私有的静态属性，用于保证这个属性只有一个，这个属性只创建一次
静态的公共方法，因为私有构造器所以类外无法创建对象，只能通过静态方法提供调用
 
public class singleton{
	private singleton(){} //私有构造器只能在当前类内进行调用 
	
	private static Singleton instance=new Singleton();
	public static Singleton getInstance(){
	return instance;
	}
}
 
父子类之间的关系
 
public static void main(String[] args) {
	B4 bb = new B4(); //当构建子类时系统默认对对父类的构造器先执行
	//创建子类对象时，系统先自动查找子类的父类，如果有父类继续向上查找，直到查找到object类为止。
	//构建对象时，先执行祖先类的构造器，然后再执行子类的构造器
	}
}

class A4 { 
	public A4() { 
		System.out.println("A4 构造器..");
	}
}

class B4 extends A4 { 
	public B4() {
		System.out.println("B4 构造器");
	}
}