一、JDK提供的比较器：
在Arrays 类中，提供了sort方法。
sort(Object[] os);
1.如果想使用Arrays 的sort(Object[] os)方法，那么os 中的元素类型，必须实现java.lang.Comparable 接口。并按照接口的规则去在子类中实现即可。
2.如果想使用Arrays 的sort(Object[] os，Comparator com)方法，那么必须指定一个外部比较器com，且com 必须是jdk 提供的java.util.Comparator 的子类对象。
例：
import java.util.Arrays;
import java.util.Comparator;
import com.javase.util.MyUtils;
public class TestArraySort {
public static void main(String[] args) {
Tiger[] tigerArr = new Tiger[6];
for (int i = 0; i < tigerArr.length; i++) {
tigerArr[i] = new Tiger(MyUtils.getRandomNumber(1, 10),
i % 2 == 0 ? i + "小" : "a大",
MyUtils.getRandomNumber(0, 2) == 1 ? "公" : "母");
}
// 数组的字符串表示形式，数组元素逐个调用toString 得到所有的元素的字符串表示形式。
System.out.println("原数组:\n" + Arrays.toString(tigerArr));
// 如果一个对象数组，想使用 Arrays 的sort 方法进行排序，
// 那么元素的类型 必须 实现java.lang.Comparable 接口。
Arrays.sort(tigerArr);
System.out.println("\n内部比较器--按年龄排列数组:\n" + Arrays.toString(tigerArr));
// Arrays.sort(tigerArr, c); 使用 外部比较器 c 的比较的规则，对 tigerArr 数组进行排序。
Arrays.sort(tigerArr, new NameSort());
System.out.println("\n外部比较器--按姓名排列数组:\n" + Arrays.toString(tigerArr));
}
}
// 定义了一个外部比较器对象，一个对对象名字进行外部比较的比较器。
// 自定义的对 Tiger 的名字进行外部比较的类。 通过泛型指定外部比较的类型。
// 通过泛型可以不再对Object 对象进行需要类型的 强制转换。
class NameSort implements Comparator {
@Override
public int compare(Tiger arg0, Tiger arg1) {
// 字符串对象实现了内部比较的规则。实现java.lang.Comparable 接口。
return arg0.getName().compareTo(arg1.getName());
}
}
// 泛型，指的是要对什么类型进行内部排序，尖括号中就填什么类型即可。
class Tiger implements Comparable {
private int age;
private String name;
private String gender;
public Tiger() {
}
public Tiger(int age, String name, String gender) {
super();
this.age = age;
this.name = name;
this.gender = gender;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getGender() {
return gender;
}
public void setGender(String gender) {
this.gender = gender;
}
@Override
public String toString() {
return "\nTiger [age=" + age + ", name=" + name + ", gender=" + gender
+ "]";
}
@Override
public int compareTo(Tiger arg0) {
return this.age - arg0.age;
}
}
二、内部类
内部类：在类的内部定义的类。
类中包含的成员：成员变量，成员方法，构造方法，代码块，内部类。
内部类：
1：普通成员内部类。（很少见）
2：静态成员内部类。（第二常见）
3：方法内部类。（基本加不到）
4：方法匿名内部类。（最常见）
（一）普通成员内部类
普通成员内部类特点：
1：关于类的访问权限修饰符，可以是四个权限。和普通的类的实例成员一样。
2：在内部类中可以访问外部类的所有的访问权限的成员。
3：如果外部类和内部类的成员名有冲突，可以在内部类中通过外部类的类名+this.区分。如：Outer.this.age ++;
4：内部类的对象依赖于外部类的对象，而且必须先创建外部类的对象才能创建内部类的对象。
这种类型的内部类，如果想创建内部类的对象，必须先创建外部类对象，使用起来不太方便。
5：外部类可以访问内部类的私有的成员。
6：还可以实现一种变相的多重继承，使用内部类继承一个类，外部类也继承一个类。在外部类中就可以通过创建内部类对象访问内部类继承的类的功能。
7：Outer$Inner.class 内部类也单独编译，但是必须指明是谁的内部类。
合适考虑使用内部类：
如果某个类只想给某个类提供服务，关系很是亲密，并且不想被其他的类访问。就可以将该类定义在它所服务的类的内部使用。
import com.javase.day15.Outer.Inner;
public class TestNormalInnerClass {
public static void main(String[] args) {
// 在其他的类中直接创建内部类的对象的方法。
// 必须先创建外部类对象，才能创建内部类对象。
Outer outer = new Outer();
Inner inner = outer.new Inner();
// 2
Inner inner2 = new Outer().new Inner();
}
}
class Outer extends A {
private int age;
void test1() {
age++;
}
void test2() {
Inner inner = new Inner();
inner.test();
inner.age++;
a();
inner.b();
}
// 普通成员内部类
// 理解：外部类的一个普通的实例成员。
public class Inner extends B {
private int age;
void test() {
Outer.this.age++;
test1();
}
}
}
class A {
void a() {
}
}
class B {
void b() {
}
}
（二）静态成员内部类
特点： 1：静态成员内部类前使用static 修饰。
2：静态成员内部类对象不依赖于外部类对象，而依赖于外部类。效率稍高于普通成员内部类。
3：通过外部类直接创建内部类对象。
import com.javase.day15.Outer1.Inner;
public class TestStaticInnerClass {
public static void main(String[] args) {
Inner inner = new Outer1.Inner();
}
}
class Outer1 {
private int age;
private static int count;
static class Inner {
void test() {
count++;
}
}
}
（三）方法内部类
public class TestMethodInnerClass {
public static void main(String[] args) {
final int age = 10;
// 只能在方法内部使用，类似于局部变量
class AA {
void test() {
System.out.println(age);
}
}
final AA a = new AA();
// 在方法内部内部类的内部只能访问方法内的使用final 修饰的局部变量，或者等价于final修饰的局部变量（在变量的整个作用域内，不能修改变量的值）
// 局部变量的生命周期依赖于方法的返回，但是局部创建的对象的生命周期不一定依赖于方法的返回。
// 不能让一个对象去访问一个不存在的变量。只能修饰成final去解决。编译的时候，所有的final的引用都被进行了使用常量值对终态变量的替换。
new Thread() {
public void run() {
for (int i = 0; i < 100; i++) {
a.test();
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}.start();
System.out.println("TestMethodInnerClass.main()");
}
}
（四）方法匿名内部类
1：方法匿名内部类，本质是一种继承或者是实现接口的子类的形式，只不过没有类名
2：匿名类，没有类名，所以没有构造方法。
3：使用方便，不用再单独的创建一个类。
4：在awt，jdk的图形界面编程中，使用匿名内部类的方式处理窗口的事件（非常的普遍）。
import java.util.Arrays;
import java.util.Comparator;
import com.javase.util.MyUtils;
public class TestAnonymousInnerClass {
public static void main(String[] args) {
// 方法匿名内部类，本质是一种继承或者是实现接口 的子类的形式，只不过没有类名
// 匿名类，没有类名，所以没有构造方法。
// 1.继承某一个顶层非抽象类
new TestClass() {
void testShow() {
System.out.println("2222222222");
}
}.testShow();
// 2.继承抽象类
new TestAbstractClass() {
@Override
void testAbstractShow() {
System.out.println("333333333333333");
}
}.testAbstractShow();
// 实现接口
Tiger[] tigerArr = new Tiger[6];
for (int i = 0; i < tigerArr.length; i++) {
tigerArr[i] = new Tiger(MyUtils.getRandomNumber(1, 10), i + "小",
MyUtils.getRandomNumber(0, 2) == 1 ? "公" : "母");
}
System.out.println(Arrays.toString(tigerArr));
Arrays.sort(tigerArr, new Comparator() {
@Override
public int compare(Tiger arg0, Tiger arg1) {
return arg0.getAge() - arg1.getAge();
}
});
System.out.println(Arrays.toString(tigerArr));
Arrays.sort(tigerArr, new Comparator() {
@Override
public int compare(Tiger arg0, Tiger arg1) {
return arg0.getName().compareTo(arg1.getName());
}
});
System.out.println(Arrays.toString(tigerArr));
}
}
class TestClass {
void testShow() {
System.out.println("1111111111");
}
}
abstract class TestAbstractClass {
abstract void testAbstractShow();
}
三、算法
（一）查找：
1.顺序查找；
空间复杂度：
S(n) = O(1)
时间复杂度：
T(n) = O(n)
/**
* //对指定的数组，查找是否有指定的值。
* @param arr 待查找的数组
* @param key 查找的值
* @return 如果存在返回 key 所在的索引，否则返回-1
*/
public static int searchKey(int[] arr, int key){
if(arr == null)return -1;
int len = arr.length;
//长度是0
if(len == 0)return -1;
//使用for 循环逐个遍历，查找
for(int i=0;i
if(arr[i] == key)
return i;
}
return -1;
}
public static void test1(){
int[] arr = new int[10];
for(int i=0;i
arr[i] = MyUtil.getRandomNumber(0, 20);
}
System.out.println(Arrays.toString(arr));
System.out.println(searchKey(arr, 17));
}
2.折半查找。
折半查找又称为二分查找，这种查找方法需要待查的查找表满足两个条件：
首先，查找表必须使用顺序存储结构；
其次，查找表必须按关键字大小有序排列。
使用非递归实现折半查找
key=21的查找过程
/**
* 二分查找
* @param arr 升序待查找的数组
* @param key 待查找的值
* @return 如果找到，返回 索引，否则 返回-1；
*/
public static int binarySearch(int[] arr,int key){
//处理极限情况
if(arr == null)return -1;
int len = arr.length;
if(len == 0)return -1;
int low = 0;//待查找范围的最小索引
int high = len-1;//待查找范围的最大索引
//key 不在数组的区间内
if(key < arr[low] || key > arr[high])return -1;
//key 等于第一个或者最后一个元素
if(key == arr[low] )return low;
if(key == arr[high]) return high;
int count = 0;
//在区间内
while(low <= high){
count ++;
//先二分
int mid = low + high >> 1;
//判断mid 指向的数组元素的值和key 比较
if(arr[mid] == key){
System.out.println(count);
return mid;
}else if(arr[mid] < key){
low = mid +1 ;
}else{
high = mid - 1;
}
}
return -1;
}
static void test2(){
int[] arr = new int[100000];
for(int i=0;i
arr[i] = i;
}
Arrays.sort(arr);
// System.out.println(Arrays.toString(arr));
System.out.println(binarySearch(arr, 99));
}
（二）排序
什么是排序
排序（sorting） ）的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。
其确切的定义为：
假设有n个数据元素的序列{R 1 , R 2 , … , R n }，其相应关键字的序列是{K 1 , K 2 , … , K n }，
通过排序要求找出下标1 , 2 , … , n的一种排列p 1 , p 2 , … , p n ，使得相应关键字满足如下的非递减（或非递增）关系
Kp 1 ≤ Kp 2 ≤ … ≤ Kp n
这样，就得到一个按关键字有序的纪录序列：{ Rp 1 , Rp 2 , … , Rp n }
内部排序和外部排序
一类是整个排序过程在内存储器中进行，称为内部排序；
另一类是由于待排序元素数量太大，以至于内存储器无法容纳全部数据，排序需要借助外部存储设备才能完成，这类排序称为外部排序。
本章介绍的排序方法都属于内部排序
稳定排序和不稳定排序
如果在待排序的序列中存在多个具有相同关键字的元素。
假设K i =K j （1≤ i≤ n，1≤ j≤ n，i≠j），若在排序之前的序列中R i 在R j 之前，
经过排序后得到的序列中R i 仍然在R j 之前，则称所用的排序方法是 稳定的；
否则，当相同关键字元素的前后关系在排序中发生变化，则称所用的排序方法是不稳定的。
无论是稳定的还是不稳定的排序方法，均能完成排序的功能。
在某些场合可能对排序有稳定性的要求，此时就应当选择稳定的排序方法。
例如，假设一组学生纪录已经按照学号有序，现在需要根据学生的成绩排序，当分数相同时要求学号小的学生在前，
显然此时对分数进行排序就必须选择稳定的排序方法。
排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )
若排序后得到结果( 18, 23, 34, 47, 47, 56, 66, 82 )，则称该排序方法是稳定的
若排序后得到结果( 18, 23, 34, 47, 47, 56, 66, 82 )，则称该排序方法是不稳定的
比较排序和非比较排序
大部分排序都是需要通过比较首先来判断大小，作为排序的依据的。
但是也有例外的，比如计数排序、基数排序，不需要进行比较。
插入排序：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度
交换排序：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度
选择排序：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度
归并排序：通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度
排序类型
一般说是八大排序类型
另外还可以加上非比较的计数排序、选择排序中的树形选择排序、插入排序中的折半插入排序
排序效率
时间复杂度最高的就是三种基本排序：直接插入、简单选择、冒泡排序。
建议优先掌握直接插入、简单选择、冒泡排序、快速排序
1.冒泡排序
冒泡排序的分析：
空间效率：仅使用一个辅存单元。
时间效率：假设待排序的元素个数为n，则总共要进行 n-1 趟排序，对 j 个元素的子序列进行一趟起泡排序需要进行 j-1 次关键字比较。由此，起泡排序的总比较次数为
因此，起泡排序的时间复杂度为Ο(n2 )。
稳定性：稳定
2.选择排序
简单选择排序的分析
空间效率：显然简单选择排序只需要一个辅助空间。
时间效率：在简单选择排序中，所需移动元素的次数较少，在待排序序列已经有序的情况下，简单选择排序不需要移动元素，在最坏的情况下，即待排序序列本身是逆序时，则移动元素的次数为3(n-1)。然而无论简单选择排序过程中移动元素的次数是多少，在任何情况下，简单选择排序都需要进行n(n-1)/2 次比较操作，因此简单选择排序的时间复杂度为Ο(n2 )。
稳定性：不稳定
每一趟从待排序区中找一个最小的元素，然后将该元素和待排序区的第一个元素进行交换。每一趟最多只交换一次。
代码实现思路：
外层循环控制趟数：数组的长度-1.
内层循环：每一趟从待排序区中找一个最小元素的下标。
找到之后和第一个待排序区的元素交换即可。
/**
* 对指定的数组进行选择排序
*/
static void selectSort(int[] arr){
//外层循环控制趟数
//i 控制趟数，i 记录着当前需要比较交换的待排序区的元素。
for(int i=0;i
//min 记录着 当前趟的最小元素下标
int min = i;
//内层循环控制当前趟 查找最小元素下标
for(int j = i + 1;j < arr.length ;j++){
if(arr[j] < arr[min]){
min = j;
}
}
//交换
if(min != i){
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
static void test3(){
int[] arr = new int[30];
for(int i=0;i
arr[i] = MyUtil.getRandomNumber(0, 100);
}
System.out.println(Arrays.toString(arr));
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
3.插入排序
直接插入排序的分析
空间效率：仅使用一个辅存单元。
时间效率：假设待排序的元素个数为n，则向有序表中逐个插入记录的操作进行了 n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。
⑴ 在最好情况下，即待排序序列已按关键字有序，每趟操作只需 1 次比较 0 次移动。此时有：
总比较次数= n-1 次
总移动次数= 0 次
⑵ 在最坏情况下，即待排序序列按关键字逆序排序，这时在第 j 趟操作中，为插入元素需要同前面的 j 个元素进行 j 次关键字比较，移动元素的次数为 j+1 次。此时有：
⑶ 平均情况下：即在第 j 趟操作中，插入记录大约需要同前面的 j/2 个元素进行关键字比较，移动记录的次数为 j/2+1 次。
此时有：
总比较次数≈ n2 /4 次
总移动次数≈ n2 /4 次
由此，直接插入排序的时间复杂度为O(n2 )
稳定性：稳定
1：左边是有序区，右边是待排序区。
2：每次从待排序区中取第一个元素。将该元素插入到 有序区的合适的位置。
//插入排序
static void insertSort(int[] arr){
//外层循环控制趟数，并i 记录着待排序区的第一个元素的索引，也就是需要将i 索引的元素插入到有序区的合适的位置。
for(int i= 1;i
//备份需要插入合适位置的数据
int value = arr[i];
int j = i-1;
//内层循环 给当前的value 找一个合适的位置。只要比value 大的元素都要后移。逆序后移
for(; j >= 0 && arr[j] > value; j--){
arr[j + 1] = arr[j];
}
//将value 插入到指定的位置
arr[j+1] = value;
}
}
static void test4(){
int[] arr = new int[30];
for(int i=0;i
arr[i] = MyUtil.getRandomNumber(0, 100);
}
System.out.println(Arrays.toString(arr));
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
