OOP and Algorithms

Course II notes

Writing Classes

两个重要的组成部分：

对象的行为（behaviors）
对应的数据（data）

Instance Variables

Instance variables：所有 instances 都有的属性，但其值对于每个 instance 都是独特的
Instance variables 在内存中拥有独立的空间
Instance variables 的声明在 class 中声明；在类中申明的成员都被称为类成员。

class defination

instant variable 的声明位置应该在紧接 class header

public class Insect {
    //instance variables here
}

简单的例子：

public class Insect {
    private double weight;
    private int x;
    private int y;
}

Visibility Modifiers

Visibility Modifiers 指在类/instance variable 声明的最前面的关键字。该关键字用于控制类对 instance variable 的管理权限。一些概念：

encapsulation：类应该提供管理好自身 instance variables 的功能
private: 只有类中的 method 能够修改本类的 instance variables
public：允许类外的其他类访问本类的 instance varibales.

Testing Objects

通常对类进行测试的手段一般是在类中直接新建一个 main 来测试：

public class Insect {
    private double weight;
    private int x;
    private int y;

    public static void main(String[] args) {
        Insect buzz1 = new Insect();
        Insect buzz2 = new Insect();
    }
}

The Constructor

Default constructor

同 C++
默认值：
- int / double / float: 0 / 0.0
- boolean: false
- class: null

定义 constructor

绝大部分情况使用 public，因为需要允许其他部分调用构造函数生成对象。
名字与类相同
没有返回值

构造函数的调用（Object 的实例化）需要配合自定义构造函数的参数列表：

//cstr
public Insect(double initWeight, int initX, int initY) {
    weight = initWeight;
    x = initX;
    y = initY;
}

//calling cstr
public static void main(String[] args) {
    Insect bug1 = new Insect(5.0, 1, 2);
    Insect bug2 = new Insect(3.0, 1, 3);
}

Constructor Overloading

与其他 method 一样，constructor 也可以通过重载适应不同的参数列表：

public static final int DEFAULT_X = 0;
public static final int DEFAULT_Y = 0;

//cstr overloading
public Insect(double initWeight) 
{
    weight = initWeight;
    x = DEFAULT_X;
    y = DEFAULT_Y;
    count ++;
}

Constructor Chaining

类似于 C++ 中的委托构造函数。
使用 this 作为创建方式
Chain 是可以多级的，可以将委托构造函数本身作为底层函数实现更高层的构造函数。

//cstr chain
public Insect(double initWeight)
{
    this(initWeight, DEFAULT_X, DEFAULT_Y);
}

//cstr
public Insect(double initWeight, int initX, int initY) 
{
    weight = initWeight;
    x = initX;
    y = initY;
    count ++;
}

instances methods

Instances methods 概念上类似 C++ 的成员函数。分为两类：

Interface：这类函数一般都是 public 的，为其他外部调用者提供接口，因此没有 static 关键字。
helper：这类函数一般是 private 的，只用于实现 interace 中的 Method。

//interface
public
void move(int newX, int newY)
{
    double distance = calDistance(x, y, newX, newY);
    System.out.println(distance);
    if (distance > 0) {
        x = newX;
        y = newY;
        weight = weight * distance;
        System.out.printf("Moved %.2f units\n", distance);
    }
    else {
        System.out.println("Staying put");
    }
}

//helper
private static 
double calDistance(double x_1, 
                    double y_1, 
                    double x_2, 
                    double y_2) {
                    
    return Math.sqrt(Math.pow(y_1-y_2, 2) + Math.pow(x_1-x_2, 2));
}

//call
bug1.move(1, 10);
bug2.move(10, -300);

Static Variables and Constants

class 的定义中通常会出现一些各个 Instance 都会共享的常量：

public static final double aConstant = 0.0001;

static 将该常量从 instance 限定转换为多个 instances 共享。
因为是常量，所以添加 public 并不会影响封装。

如果不是常量的话，需要设置为 private，避免除了 instances 以外的数据对其进行修改。比如我们在构造函数内部添加一个计数属性用于统计总共创建的对象数：

private static int count = 0;
public Insect {
    ..../
    count ++;
}

只有在外部访问类成员的时候，才需要 className.classMember 这样的方式。

Static Methods

设计类函数的时候，需要更多的考虑通用性；比如使用 return 取代打印，这样就能消除对命令行的依赖。
与类无关的函数（比如工具类函数），尽量设计为 public static method
static method 无法访问 non-static member，构建之前需要仔细思考成员之间的关系。

Math.random()

Math.random() 返回 $[0,1)$ 之间的数。可以使用下面的表达式来返回 (min, max) 之间的 int：

(int)(Math.random() * ((max - min)  + 1)) + min;

Using "this" as a reference

this 关键字表示的是当前 object 的引用。Java 中可以在类的内部使用 this.attribute / this.method() 的方式来访问（调用）类成员。比如之前的构造函数可以改写成：

public Insect(double weight, int x, int x) 
{
    this.weight = weight;
    this.x = x;
    this.y = y;
}

注意这里的 weight, x, y 是构造函数的局部变量；真正的 instance variable weight, x, y 是通过 this 来取得的。

Accessor & Mutator

某些情况下，我们可能需要在类外访问或者修改类中的私有变量。这种情况下我们是无法通过 className.classMember 的方式进行访问的。

Accessor

访问解决方法是，在类中创建 public 的 method，通过该 method 去访问对应的私有变量。我们将这样的 method 称为 Accessor 或 Getter，比如：

class Insect {
//instance variable
private int count = 0;
private static final int aConstant = 1;
//Accessor
public int getCount() {
    return count;
}
//call
Insect bee = new insect(....);
bee.getCount();

类中的私有常量可以通过 public static 类型的 Accessor 来访问：

public static getStaticConstant() {
    return aConstant;
}
//call by using class name instead of instance name:
Insect.getStaticConstant();

Accessor 的一些常见特点以及注意事项：

没有参数列表
返回值类型是对应私有变量的类型
只为有访问私有变量需求的类提供 Accessor

Mutator

Mutator（Setter），用于在类外修改类中的私有变量。其实现方式与 Accessor 一致。几个 converntion：

Mutator 返回类型为 void，因为只需要做修改
以 set 为前缀，比如 setName(para)
在修改对应的变量之前，需要做输入合法性检测

public void setCount(int newCount) {
    if(isLegalCount(newCount) {
        count = newCount;
    }
}

toString Method

toString() 是 Java 自带的，所有 Object 都会继承的，一个将当前对象信息转化为 String 的 method。默认情况下，toString() 的输出结果为：

#className@instanceHASH
Insect@7699a589

我们通常会在类中 overload 这个 method 来跟踪打印类中的成员。比如 Insect 类，如果需要查看类中 3 个 Instance variable 的内容：

public String toString() {
    return "weight: " + weight + " x: " + x + " y: " + y;
}
//call
System.out.println(bug3.toString());

由于 println method 默认情况下打印的就是 toString() 的返回结果，因此上面的内容打印可以直接简化为：

System.out.println(bug3);

实例：扔骰子

几个重点：

结构：
1. 负责存储骰子数据的数据类 Die ，以及骰子的行为 roll 的实现方法
2. 负责运行游戏的游戏逻辑类 Craps
3. 负责启动游戏的启动类 CrapLauncher
注意事项：
1. Method 的 visibility 取决于在哪里使用
2. 访问私有变量一定要通过 Accessor
3. 除了 Math.Random()，Java 还提供了 util.Random 供使用。本例使用了 Random.nexInt(bound) 实现了骰子的随机结果。
  1. Random.nexInt(bound) 返回的区域是 $[0, bound)$

Source code with comments: craps.zip

Inheritance

describing this transfer of attributes and behaviors from one class to another
- A derived class is called a subclass or child class

Hierarchies

Java 不允许多重继承，因此一个 chlid class 只允许有一个 parent class
parent class 应该选与 chlid class 重合度最高那一个
继承代表的关系是 IS，比如 “yellow jacket is a Wasp, Wasp is an insect”
Java 提供了一个名为 Class 的类；该类多用于继承时使用。

Wrting a subclass

The protected Modifier

在 Java 的继承机制中：

私有成员不会被继承
通过 public 的方式继承会破坏封装

因此，如果一个 subclass，希望继承来自 Parent class 的私有成员，但又不希望这些成员被该 subclass 以外的类使用的话，使用 protected 关键字定义 parent class 中的成员：

public class Canine {
    protected double size;
    public Canine(double size) {
        this.size = size;
    }
}

注：Java 中的 protected 成员，允许被同 package 下的其他 class 使用。

访问权限表格：

Modifier	Class	Package	Subclass	World
public	Y	Y	Y	Y
protected	Y	Y	Y	N
private	Y	N	N	N

Declaring Subclasses and Instance Variables

声明子类使用关键字 extends

public class Canine {
    protected double size;
    public Canine(double size) {
        this.size = size;
    }
}

Subclass Constructors

继承（引用）父类成员使用 super() method
super() 代表了对父类构造函数的调用
必须处于子类构造函数定义中的第一列

public class Dog extends Canine {
    //for the subclasses under the dog, e.g. Husky
    protected String name;
    //cstr
    public Dog(String name, double size) {
        //refer to "size" in the parent class "Canine"
        super(size);
        this.name = name;
    }
}

super 的调用在子类里是强制的。如果我们没有显式的为子类调用 super 以及对应的私有变量，Java 会自动调用一个无参数 的 super。这种调用不会考虑到已继承的变量，因此通常会出错：

//the Dog constructor is not going to work due to the above rule
//Canine() cannot apply to Dog()

public class Dog extends Canine {
    //....
    private size = 0;
    //cstr
    public Dog(String name, double size) {
        this.size = size;
        this.name = name;
    }
}

Overriding Methods

Java 中的重写只需要在子类中重新定义需要重写的函数即可：

public class Canine {
    //....
    public void bark() {
        System.out.println("wof wof");
    }
}

public Dog(String name, double size) {
    super(size);
    this.name = name;
}
//super bark override
public void bark() {
    for (int i = 0; i < 2; ++i) {
        super.bark();
    }
}
//call
Dog spot = new Dog("Spot", 9.6);
spot.bark();

//result
wof wof
wof wof

注意上面的重写部分，如果希望以父类函数为基础进行重写，只需要使用 super 调用父类函数即可，比如这里的 super.bark()。

调用重写函数的过程的概念就是 C++ 里的动态绑定；也就是根据 instance 指向的 class 类型来决定（动态类型，运行期决定）。

Overriding 的前提是父类 method 与子类 method 的签名一致。
重写的子类 method 不一定遵守父类 method 的 visiblity；比如子类可以使用 public 的方式重写父类中可见性为 pravide 的 method

可以在函数前加上 @Override 来确保重写的函数名是否与父类中的函数名相同。

final method

final 关键字应用到 method 上，会阻止其被重写
final 关键字应用到 class 上，会阻止其被继承
如果某个实现（优化）非常特别，或者数据非常敏感，使用 final 来确保其不会被重写。

Abstract class

abstract method：声明了，但还没有定义（实现）的 method
abstract class: 至少包含一个 abstract method 的 class
这两者绑定：包含 abstract method 的 class 必须声明为抽象类

abstract method

概念同 C++ 的虚函数

什么是 abstract method? 在模拟现实生活的过程中，有一些行为的一致性是很低的。比如犬类给自己顺毛的行为，狼，狗，家狗，野狗，都不一样；这种情况下，在父类 Canine 中定义一个标准的 groom() method 是很难的。

我们处理的方式是，声明这个方法，但不实例化，将实现交给子类自行解决。这个要求是强制的；也就是说，在继承了 abstract method (class) 后，子类必须对对应的 abstract method 进行具体的实现。

abstract Modifier

定义抽象类 / 抽象方法只需要添加 abstract 关键字即可：

public abstract class Canine {
    //....
    public abstract void groom();
    //....
}

Java Object Class

Object Class 是所有类的 root
在引用类方法时，我们只能引用类中已有的方法，而不能考虑可能存在的方法，因为：
- 子类是父类的一种，因此指向父类的引用，也可以说是指向子类
- 但因为使用引用调用方法时，该方法必须要在类中有声明
- 因此，不能因为子类中可能存在某种属于的方法，就使用父类的引用去调用子类的方法。所以使用 Object 类型的对象，去访问任意其他 Object 对象中没有声明的方法，都是错误的。
- 通俗点来讲，你不知道你指向的具体是什么，所以不能乱来。比如猫是动物，狗也是动物，但你不能说因为猫是动物，所以我能让动物抓老鼠；因为很可能当前动物的实例是条狗。
- 解决方案是使用多态（polymorphism），后面会讲到。

Object.equals() 的重写

Object 中有一个 method 叫 equals（之前用过，String 类中对齐进行了重载）。默认情况下，Object.equals() 的作用是判断两个实例引用是否指向同一个实例。根据之前讨论的内容，设想一种情况：在不知道 Object 的实例类型具体是哪种子类的情况下，我们要如何使用该对象与其某种特定类型的子类进行比较呢？

一个可行的判断依据是，只有两个子类是同一类型的对象时，才能进行比较。以 Dog 为例，只有两边都是狗的时候，我们才能依据一些条件来进行比较。因此，首先需要做两种判断：

空对象不予考虑（值为 null 的对象）
对象类型不是 Dog 的不予考虑

Java 提供了 instanceof 运算符将上述的两个操作合二为一了。因此，要检测是不是同一类型的对象，有：

if (!(o instanceof Dog)) {
        return false;
    }

有了这层建议，我们就可以在 Dog 类中将 equals 按照我们的规则进行重写了，比如：

public boolean equals(Object o) {
    if (!(o instanceof Dog)) {
        return false;
    }
    Dog doggy = (Dog) o;
    return ((doggy.size == size) && (doggy.name.equals(name)));
}

需要注意的是，即便证明了 o 是 Dog 类型的对象，但使用 o 依然无法访问 Dog 重写的 equals。因此，我们需要使用另外一个 Dog 类型的引用来指向 o，从而间接达到用 o 访问 Dog.equal() 的效果。我们将该引用命名为 doggy，其值为将 o 强制转换为 Dog 类型后的值：

Dog doggy = (Dog) o;

这样，即便不清楚 o 的具体类型的情况下，我们也能安全的将其与 Dog 类型的实例进行比较了。

Interfaces and Algorithms

interface

在实际的应用中会出现这么一种关系，某一类的对象具有某个行为上的共同点，但对象本身并不构成继承的关系。比如狗与车，都有 “洗” 的行为；但狗和车显然不构成 IS 的关系。

这种情况是无法使用子类重写的方式解决的。因为子类重写的方式要求两点：

继承
父类必须声明了这样的方法

比如如果都是犬类所属，那对象的 group 定义为犬类即可：

public class GroomEverything {
    public static void main(String[] args) {
        Canine[] groomer = {
            new Wolf(17,3),
            new Poodle("richie", 2,"Pantene", "Bodyshop")
        };
    
        for (Canine c : groomer) { 
            c.groom();
            }     
    }
}

但显然车对象是无法放进 grommer 的，因为车的父类并不是 Canine。因此，我们需要一种新的方式来解决这个问题：如果将没有继承关系，但又具有某些相同行为的不同对象放入到一个 group 中进行遍历调用？

Java 提供了 Interface 来解决这个问题。interface 是一种类型（与 class 类似），但更像是一个方法声明的集合。他主要做的是：

声明一系列需要重新定义的 abstract method
编译 interface 之后，如果有 class 希望重写该 Interface 里的方法，都可以进行声明
如果是 concrete class，那么需要定义重写的方法。抽象类则不用，因为可以交给具体的子类实现。
一个 class 可以重写（实现）多个 interface

Interface 的定义

与 class 的定义类似，interface 也需要单开一个与 Interface 名称相同的文件。在 interface 中声明 method 的方式与 class 一致。在 interface 中，moidifer 的默认有两点：

所有声明的 method 默认都是 abstract method
所有声明的 method 默认都是 public method

//in Groomable.java
public interface Groomable {
    //lists of abstract methods
    public void groom();
}

编译的结果依然是 .class 文件。

绑定和使用 Interface

首先需要为对应的 class 添加 implements 关键字：

//do it as well to other classes that need to be added into groommer
public class Car implements Groomable {
    //...
}

在对应的 class 中实现 interface 中的方法：

public class Car implements Groomable {
    //...
     public void groom() {
        if (speed == 0) {
            System.out.println("Car grooming!");
        }
    }
}

然后将使用类型替换为我们定义的 interface 的名字。这里从 Canine[] 替换为了 Groomable[]：

public class GroomEverything {
    public static void main(String[] args) {
        Groomable[] groomer = {
            new Wolf(17,3),
            new Poodle("richie", 2,"Pantene", "Bodyshop"),
            new Car("Honda", "Civic", 2004)
        };
    
        for (Groomable c : groomer)
            {
                c.groom();
            }     
    }  
}

默认情况下，所有希望一起使用的 class 都需要添加 implements 关键字来绑定 interface。但如果父类是抽象类，我们只需要绑定父类即可；父类下的所有子类都会继承这一绑定。规则与之前一样，抽象类要有方法声明，子类要有方法实现：

public abstract class Canine implements Groomable{
    //...
     public abstract void groom();
}

//implements keyword is not needed for subclasses
public class Wolf extends Canine {
    public void groom() {
        System.out.println("wolf groom");
    }
}

Generic Sorting Method

Sorting 在 OOP 中有着重要的作用；但 Sorting 是一件具体的事情。以 Wolf 对象为例，我们可以根据其 rank 的值设计一个排序方法：

public wolfSort(Wolf[] wolfArry) {
    //...
    //condition
    return wolf1.getRank() > wolf2.getRank();
}

但如果比较的对象不是 Wolf 对象，那么我们需要重写该方法的两部分：header（包括接收的对象）和 condition。这样做非常繁琐，因为每一个新类型的对象都需要写一个新的排序方法。

由于 Object class 的存在，Java 能够提供一种新的方法：

排序方法是通用的
具体的排序规则由具体类实现

我们将这个方法命名为 CompereTo()。由于所有的类都是 Object 的子类，因此通用排序方法可以改写为：

public genericSort(Object[] arry) {
    //...
    //condition
    return obj1.compareTo(obj2);
}

也就是说，我们只需要在具体类中实现 compareTo() 就可以完成比较，而不是针对每一个类都去设计一个 sorting 的 method。

CompareTo 的简单结构

返回值类型为 int，分为三种情况：
- 两者相等则返回零
- 前者大于后者返回正数，反之返回负数
元素的访问通过 arr[index] 的方式。与 interface 绑定会确认这些元素内有可以执行的方法。

Java 对以上内容的支持

提供了一种 Interface java.lang.Comparable 类型作为 compareTo 的实现条件。
提供了 util.Array.sort() 作为对象排序的实现（使用 Timsort）
- 执行期间先会将调用 compareTo 的对象转化为 Compareable 类型

(Comparable).arr[index].compareTo(arr[anotherIndex]);

使用上述支持实现自定义 compareTo()

Comparable 与之前自定义 Interface 的使用方法一致，将其至于 implements 关键字后面。如果有多个 Interface，以逗号隔开：

public class Wolf extends Canine implements Groomable, Comparable {
    //...
}

接下来需要将 Wolf 对象使用的 compareTo() 实现：

public int compareTo(Object anotherWolf) {
    return -(rank - ((Wolf)anotherWolf).rank);
}

返回值是 int
parameter 是 Object 类型
使用 parameter 的时候需要将 Object 类型转化为 Wolf 类型，这样才能访问 rank 变量。
注意用括号保证 casting 的部分的优先级。access operator . 的优先级非常高。

修复在 runitime 时对象类型转换失败的问题

上述的解决方案中，由于 casting 是在 runtime 时进行的，因此 anotherWolf 的类型直到被转换的那一刻才会被检验。这个过程使得不正确的输入类型会导致 runtime error。

解决这个问题的方式是将条件判断转移到编译期。Java 提供了 Interface 的 Type Parameter 来解决这个问题。Type Parameter 可以让 compareTo() 在编译期就可以将真正需要的对象类型确定下来。具体写法：

public class Wolf extends Canine implements Comparable<Wolf> {
    /...
}

对应的，compareTo 中的实现也需要将 Object 类型改为 Wolf 类型；但因为类型已经确定，casting 的过程也可以省略了：

public int compareTo(Wolf anotherWolf) {
    return -(rank - anotherWolf.rank);
}

类型检测尽量放到编译期去验证。

Arrays.sort() 的使用

实现了 compareTo() 之后，我们就可以利用 Arrays.sort() 对 Wolf 对象进行排序了。使用前需要导入 Array package:

//import
import java.util.Arrays;

//rewrited toString for output:
public String toString() {
    return String.format("Rank: %d", rank);
}

//call in main
public static void main(String[] args) {
    Wolf[] wolfPack = {
        new Wolf(17.1, 2),
        new Wolf(3, 10),
        new Wolf(9.2, 7),
        new Wolf(17.01, 3),
        new Wolf(5, 9)
    };
    Arrays.sort(wolfPack);
    System.out.println("Sorted: " + Arrays.toString(wolfPack));
}

默认的排序是升序，因此 rank 为 10 的会排在最前面：

Sorted: [Rank: 10, Rank: 9, Rank: 7, Rank: 3, Rank: 2]

Sorting Algorithm

Selection Sort

查找最小数，标记 index
与当前子数列第一位交换

//int version
public static void selectionSort(int[] arr)
{
    int minIdx = 0;
    for (int i = 0; i < arr.length-1; ++i)
        for(int j = i+1; j < arr.length; ++j)
        {
            minIdx = i;
            if (arr[j] < arr[minIdx])
            {
                minIdx = j;
            }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
        }
}

//Object version
public static void selectSort(Comparable[] arr)
{
    int minIdx = 0;
    for (int i = 0; i < arr.length-1; ++i)
        for(int j = i+1; j < arr.length; ++j)
        {
            minIdx = i;
            if (arr[j].compareTo(arr[minIdx]) < 0)
            {
                minIdx = j;
            }
        Comparable temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
        }
}

//call
Comparable[] groomer = {
            new Wolf(17,3),
            new Wolf(17,6),
            new Wolf(17,7),
            new Wolf(17,1),
            new Wolf(17,4),
};
    selectSort(groomer);

泛型版本的 sort 需要替换关系运算符为 compareTo()
该版本也可以使用 Type prarameter 在编译期阶段检测类型

Selection Sort 的优化

loop 中的交换：

Comparable temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;

只需要在最小值不处于比较区域的最开头时才进行。

if (minIndex != i) {
    Comparable temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
}

Merge Sort

使用递归
base case: 数组长度小于 2
- 数组长度小于 2 时，数组为空（或是单元素），已经排好序了，因此什么都不做 (return;)
- 数组长度大于 2 时：
  - divide：
    - 求数组的中间点，以中间点为分界线，将数组分为左右两部分
  - conquer
    - 对左右部分分别进行递归排序
    - 合并排好序的数组
排序以及合并的方法：
- 比较左部分和右部分的第一个元素
- 选取较小的元素赋值给结果数组的第一位
- 被选取的部分 index 向前，结果数组 index 向前
- 一直直到左右任意一个部分读取完毕
- 如果有任何没有读取完毕的数组，合并到结果数组中

public class Merge {
    
    //[start, end)
    public static int[] copyRange(int[] arr, int start, int end)
    {
        int[] slicedArray = new int[end - start];
        for (int i = start, j = 0;i < end; ++i, ++j) {
            slicedArray[j] = arr[i];
        }
        return slicedArray;
    }
    
    public static void mergeArrays(int[] mergedArray, int[] left, int[] right)
    {
        int lLen = left.length;
        int rLen = right.length;

        int leftIdx = 0;
        int rightIdx = 0;
        int mergedIdx = 0;

        //sorting 
        while (leftIdx != lLen && rightIdx != rLen)
        {
            if (left[leftIdx] < right[rightIdx]) {
                mergedArray[mergedIdx++] = left[leftIdx++];
            }
            else {
                mergedArray[mergedIdx++] = right[rightIdx++];
            }
        }
        // merge if there is any left
        while(leftIdx < lLen) {
            mergedArray[mergedIdx++] = left[leftIdx++];
        }
        while(rightIdx < rLen) {
            mergedArray[mergedIdx++] = right[rightIdx++];
        }
    }

    public static void mergeSort(int arr[]) {
        int currArrayLen = arr.length;
        if (currArrayLen < 2) {
            return;
        }
        else {
            int midIndex = currArrayLen / 2;
        
            int[] left = copyRange(arr, 0, midIndex);
            int[] right = copyRange(arr, midIndex, currArrayLen);

            mergeSort(left);
            mergeSort(right);
            mergeArrays(arr, left, right);
        }     
    }
}

如果需要修改为支持 Comparable interface，只需要修改：

数组的类型，从 int 改为 Comparable 类型
比较的方法：从关系运算符改为 CompareTo

Source Code: mergecomparable.java

Insertion Sort

将数列分为两部分：左边为有序，右边为无序
默认有序部分为最左边的数
每次循环将无序部分中最左边的一位加入到有序部分中进行排序
- 排序的顺序：新元素从右到左的顺序以此比较（因为左边有序，只要新元素小于某个元素就能插到前面了）
最坏情况下（倒序）也是所有元素都要比较一遍，因此也是 $n^2$ 复杂度
最好情况下（顺序）每次比较一个元素，因此是 $n$ 复杂度

Java 中的实现关键点：

比较的条件：有序部分还存在元素，且当前元素大于被比较的元素
插入的位置：上述条件不满足时，证明有序部分中当前元素是剩余元素中最大的，但小于被比较元素的数，因此插入的位置就应该在其右一位。
移位的模拟：需要保存被比较的元素，这样被比较的元素所占的位置可以拿出来做移位用。

public static void insertionSort(int[] arr) {

    for (int unSortIdx = 1; unSortIdx < arr.length; ++unSortIdx)
    {
       int currVal =  arr[unSortIdx];
       int sortIdx = unSortIdx - 1;
       
       while(sortIdx >= 0 && arr[sortIdx] > currVal)
       {
            arr[sortIdx + 1] = arr[sortIdx];
            sortIdx--;
       }
       arr[sortIdx + 1] = currVal;
    }        
}

Complexity Analysis

分析的主要目标是算法运行花费的时间
参考的标准是时间与输入规模的关系
时间使用运算次数（number of operations）来衡量
讨论的是 worst case

Stopwatch evaluation

使用 System.nanoTime() 来记录算法运行的时间：

long start = System.nanoTime();
selectionSort(input);
long end = System.nanoTime();
System.out.println("Elapsed time in ns:" + (end - start));

Constant Time

算法的运算次数不受输入规模的影响
关系图像为一条与 $x$ 轴平行直线

Linear Time & Linear Search

算法的运算次数的增长与输入规模呈线性比例
关系图像为带斜率的直线

public static int linearSearch(Comparable key, Comparable[] elementLst)
    {
        for (int i = 0; i < elementLst.length; ++i) {
            if (elementLst[i].compareTo(key) == 0) {
                return i;
            }
        }
        return -1;
    }

Quadratic Time

Selection sort: 无论如何都要把元素都比一遍（ $\frac{n^2-n}{2}$ ），因此无论是什么顺序，其复杂度都是 $n^2$ 级别的。

linearithmic Time

Merge sort: $nlog_2(n)$
- 归并的过程是 $log_2(n)$ 次

如何估算复杂度

single loop：提供线性的增长
nested loop(2)： $n^2$

Growth Rates and Big-O Notation

Growth Rate	Big-O notation
Constant	$O(1)$
Logarithmic	$O(log(n))$
Linear	$O(n)$
Linearithmic	$O(nlog(n))$
Quadratic	$O(n^2)$
Cubic	$O(n^3)$
Exponential	$O(a^n)$

Binary Search

public static int binarySearch(int[] arr, int key)
    {
        int minIdx = 0;
        int maxIdx = arr.length - 1;
        int midIdx;
        
        while (minIdx <= maxIdx)
        {
            midIdx = (minIdx + maxIdx) / 2;
            
            if (arr[midIdx] == key) {
                return midIdx;
            }
            //key in [0:mid)
            else if (arr[midIdx] > key) {
                maxIdx = midIdx - 1;
            }
            else if (arr[midIdx] < key) {
                minIdx = minIdx + 1;
            }
        }
        return - 1;
    }

More About Interfaces

只有 abstract method 的 interface 被称为是 pure abstractions。这样的 interface 意味着设计者希望将 method 的 concept 和 detail 完全分开。
Java 8 以后支持混合的实现模式：可以在 Interface 中实现 concrete method
支持两种方式：default method 和 static method

Default Methods

这是一种允许在 interface 中直接定义 Method 的方式。主要适应的场景是快速为 interface 下的各种类型添加新的共同 Method。比如之前例子中，动物与车都有“洗”的行为；如果希望给这个“洗”加一个付款 pay()，如果不使用 default method，那么只能在 interface 中声明虚函数，再去每个类里单独实现了。有了 default method 以后，则可以直接在 interface 里写；所有 interface 下的实现类都会自动得到该 Method:

public interface Groomable {
    public void groom();
    //public, by default
    default void pay() {
        System.out.println("All should pay!");
    }
}

default method 的重写

重写与一般重写一致：

public void pay() {
        System.out.println("I am the wolf and I don't need to pay!");
    }

Static Methods

如果不要求重写，那么没有必要给每一个 interface 的参与类都添加一个 Method。为此，Interface 中也提供了用于定义 static method 的方法：

public interface Groomable {
    //...
    static String calTip(double price, double percentage) {
        double rawTip = price *(percentage / 100);
        return String.format("%.2f" , rawTip);
    }
}

调用的时候按正常的 className.methodName 写法调用即可：

Groomable.rawTip(9.99, 20);

Constants in Interfaces

Interface 中允许定义常量
任何在 interface 中声明的变量，都会被视为 public static final 类型，无论是否带有 Modifier。

public interface Mascot {
    public static final double MAX_CELEBRATION_SEC = 30;
    //equivalent
    double MAX_CELEBRATION_SEC = 30;
}

为什么 interface 里的变量必须是常量？

对 Interface 本身的期望是一个存储 concept 的地方，这些常量为概念服务
Class 中的常量是存放在类中而非对象中，interface 中也应该如此

相比起在 interface 中存放常量，选择在类中存放是更好的选择。因为 class 中同时允许 instance variable 的存在。

Constant Interfaces

Constant Interfaces 指 Interface 中包含的成员均为常量。其应用场景为：程序需要使用很多常量。将这些常量全放在一个地方，可以方便读取。

这样使用固然很方便，但我们还是应该记得：interface 是用于声明行为（concept）的。constant interface 并不属于这一概念，因此尽量不要使用。

Interface Hierarchies

Interface 允许继承
Interface 允许多重继承

UML

在 UML 使用 «interface» 表示 interface
interface 到 interface 之间的关系用实线加空三角表示（extends）
class 到 interface 的关系用虚线加空三角表示（implements）
client（比如运行游戏的主程序，不是 Interface，也没有任何继承关系）使用虚线加箭头表示；指向的是该 client 的依赖（dependences）

Polymorphism

多态（Polymorphism）允许我们使用一段代码灵活吃处理不同类型的对象。

Java 处理多态的过程

Canine pixy;
pixy = new Poodle(..);
pixy.bark();

Java 会首先查找声明中的类型（declar type）
找到后，再查找实例化的类型（new 后面那个类型，instantiate type）
找到这两者之后，编译器会考虑以下两点：
1. declar type 的引用能指向具有 instantiate type 的对象吗?
2. 如果我们想通过该对象访问某些方法，那么这些方法在 declar type 中有没有声明且定义？

如果上述条件都不满足，Java 编译器会认为该 assignment 是不合法的。

Legal Assignments

Java 会对针对第一个问题进行所谓的 Relationshio test：

如果 declar type 是 class
- 检查 instantiate type 是不是 declar type 本身，或是其 subclass

比如：

//ok, pixy is a Poodle, Poodle is a dog
Dog pixy;
pixy = new Poodle();

//error, pixy is a Dog, a Dog may not be a Poodle
Poodle pixy;
pixy = new Dog(...);

这种 Is a 的规则同样应用于将 argument 传递给 parameter 的过程中。这种情况下：

argument 指向的类型是 object type
parameter 指向的类型是 instantiate type

比如：

public class Human {
    public void playFetch(Dog myPet) {
        //....
    }
}
Dog richie = new Dog(...);
Poodle pixy = new Poodle(...);

//ok, richie is a Dog
owner.playFetch(richie);
//ok, pixy is a Poodle, Poodle is a Dog
owner.playFetch(pixy);

如果 declar type 是 instance
- 检查 instantiate type 本身或是其任意父类（祖先）有没有实现 interface

声明为相同 interface 类型的两个对象很可能不是互通的；比如车不能实例化为狗，即便车和狗都有“洗”的行为。

Method Calls

第二个需要检查的是 method 的调用：

如果 declar type 中包含了该 method，那是没有问题的，比如：

//Canine defines bark()
//Poodle defines enterDogShow()

//declar type
Canine pixy;
Poodle richie = new Poodle(...);
pixy = richie;

//ok, bark() is defined in Canine
pixy.bark();

//error, Canine doesn't define enterDogShow, even if pixy's instantiate type is Poodle
pixy.enterDogShow()；

method call 只考虑声明类型中是否存在该函数的定义，不考虑对象类型；除非对象类型中存在着该 method 的 overriding（详情见之后的动态绑定）

Casting

上述例子中，如果我们希望使用 pixy 直接访问 enterDogShow()，我们需要将其转换为 Poodle 类型：

//ok, in case of using enterDogshow(), we need casting 
// !!!notice the praentheses!!!
((Poodle)pixy).enterDogShow();

Casting 可以在继承关系树上向上，或是向下进行（注意不是 is-a 或者 has-a 的关系不行！），得到的结果是一个临时的转换后的 Object 类型（的引用）。我们只需要确保 Casting 之后的类型可以访问被调用的方法即可。

Casting 只是生成了一个临时的，对应的 Object 类型的引用。pixy 永远都是指向 Canine 类型的引用。

Casting 潜在的问题

Casting 带来了一个问题。来看以下例子：

Canine dg;
dg = new Dog(...);

//is thi legal?
((Poodle)dg).enterDogShow();

这种情况下, dg 的 object type 是 Dog，而不是 Poodle。Casting 是可以进行的；但是在调用 method 的时候，JVM 会做 Is a 的检测。上面的例子中，我们调用的是 Poodle 类型实现的 method，在调用之前，编译器会询问：调用者的 object type 是不是 method 实现所在的 object type? （此处就是在问：Dog 是 Poodle 吗？）如果不是，那该 method call 就无法通过编译。

Dynamic Binding

在检测 method call 是否合法的同时，JVM 还会同时在运行期检测哪一个版本最适合当前的 call。处理该调用匹配的过程被称为动态绑定（Dynamic Binding）。总的来说：

如果 object type 和 declar type 中存在不一样的实现（即 object type 中有重写），那么选择 object type 的版本

//if Canine & Poodle both have a bark() implementation
Canine pixy;  
pixy = new Poodle(...); 

//call Poodle.bark()
pixy.bark();

如果 object type 中不存在重写，JVM 会按照继承树逐级往上查询，直到找到对应的实现

//if Canine & Dog both have a bark() implementation, but Poodle dosen't
Canine pixy;  
pixy = new Poodle(...); 

//call Dog.bark()
pixy.bark();

−目录

OOP and Algorithms

Writing Classes

Instance Variables

class defination

Visibility Modifiers

Testing Objects

The Constructor

Default constructor

定义 constructor

Constructor Overloading

Constructor Chaining

instances methods

Static Variables and Constants

Static Methods

Math.random()

Using "this" as a reference

Accessor & Mutator

Accessor

Mutator

toString Method

实例：扔骰子

Inheritance

Hierarchies

Wrting a subclass

The protected Modifier

Declaring Subclasses and Instance Variables

Subclass Constructors

Overriding Methods

final method

Abstract class

abstract method

abstract Modifier

Java Object Class

Object.equals() 的重写

Interfaces and Algorithms

interface

Interface 的定义

绑定和使用 Interface

Generic Sorting Method

CompareTo 的简单结构

Java 对以上内容的支持

使用上述支持实现自定义 compareTo()

修复在 runitime 时对象类型转换失败的问题

Arrays.sort() 的使用

Sorting Algorithm

Selection Sort

Selection Sort 的优化

Merge Sort

Insertion Sort

Complexity Analysis

Stopwatch evaluation

Constant Time

Linear Time & Linear Search

Quadratic Time

linearithmic Time

如何估算复杂度

Growth Rates and Big-O Notation

Binary Search

More About Interfaces

Default Methods

default method 的重写

Static Methods

Constants in Interfaces

Constant Interfaces

Interface Hierarchies

UML

Polymorphism

Java 处理多态的过程

Legal Assignments

Method Calls

Casting

Casting 潜在的问题

Dynamic Binding