Machine Learning

Supervised Learning

In supervised learning, we are given a data set and already know what our correct output should look like, having the idea that there is a relationship between the input and the output.

Regression problem

we are trying to predict results within a continuous output, meaning that we are trying to map input variables to some continuous function.

classification problem

we are instead trying to predict results in a discrete output. In other words, we are trying to map input variables into discrete categories.

Unsupervised Learning

Unsupervised learning allows us to approach problems with little or no idea what our results should look like. We can derive structure from data where we don’t necessarily know the effect of the variables.

We can derive this structure by clustering the data based on relationships among the variables in the data.

With unsupervised learning there is no feedback based on the prediction result

Q：如何防止一个类被继承

A：类前加上final

Q：因为某样东西属性是final，就认定它的值能在编译时期知道

A：错：

1
2
3
4
5

public class FinalData{
  final int i1 = (int)(Math.random()*20);
  static final i2 = (int)(Math.random()*20);
  static final I3 = 99;
}

上例中i1和i2在运行期间使用随机生成的数字。顺便对于含有固有初始化值得final static基本类型的数据，名字根据规则要全部采用大写。而i2在编译期间是未知的，所以它没有的大写。

Q：final和static的区别

A：

1
2
3
4

fd1: i1 = 15, i2 = 9
Creating new FinalData
fd1: i1 = 15, i2 = 9
fd2: i1 = 10, i2 = 9

对于fd1和fd2来说，i1是唯一的，但i5的值不会犹豫创建了另一个FinalData对象而发生改变。因为它的属性是static，而且在载入时初始化，而非每创建一个对象时初始化。Static强调它们只有一个；而final表明它是一个常数。

Q：为何使用final方法

A：

There are two reasons for final methods. The first is to put a “lock” on the method to preventany inheriting class from changing its meaning. This is done for design reasons when you want to make sure that a method’s behavior is retained during inheritance and cannot be overridden.

The second reason for final methods is efficiency. In earlier implementations of Java, if you made a method final, you allowed the compiler to turn any calls to that method into inlinecalls. When the compiler saw a final method call, it could (at its discretion) skip the normal approach of inserting code to perform the method call mechanism (push arguments on thestack, hop over to the method code and execute it, hop back and clean off the stack arguments, and deal with the return value) and instead replace the method call with a copy of the actual code in the method body. This eliminated the overhead of the method call. Of course, if a method is big, then your code begins to bloat, and you probably wouldn’t see anyperformance gains from inlining, since any improvements will be dwarfed by the amount oftime spent inside the method.

In more recent version of Java, the virtual machine (in particular, the hotspot technologies) can detect these situations and optimize away the extra indirection, so its no longer necessary-in fact, it is now generally discouraged-to use final to try to help the optimizer. With Java SE5/6, you should let the compiler and JVM handle efficiency issues and make a method final only if you want to explicitly prevent overriding.

两个原因，第一是为Method上锁，防止继承类改变其的意义。设计程序时，若希望一个方法的行为在继承期间保持不变，而且不可被覆盖或改写，就可以采取这种做法。

采用final方法的第二个理由是程序执行的效率。将一个方法设成final后，编译器就可以把对那个方法的所有调用都置入“嵌入”调用里。只要编译器发现一个final方法调用，就会（根据它自己的判断）忽略为执行方法调用机制而采取的常规代码插入方法（将自变量压入堆栈；跳至方法代码并执行它；跳回来；清除堆栈自变量；最后对返回值进行处理）。相反，它会用方法主体内实际代码的一个副本来替换方法调用。这样做可避免方法调用时的系统开销。当然，若方法体积太大，那么程序也会变得雍肿，可能受到到不到嵌入代码所带来的任何性能提升。因为任何提升都被花在方法内部的时间抵消了。Java编译器能自动侦测这些情况，并颇为“明智”地决定是否嵌入一个final方法。然而，最好还是不要完全相信编译器能正确地作出所有判断。通常，只有在方法的代码量非常少，或者想明确禁止方法被覆盖的时候，才应考虑将一个方法设为final。

类内所有private方法都自动成为final。由于我们不能访问一个private方法，所以它绝对不会被其他方法覆盖（若强行这样做，编译器会给出错误提示）。可为一个private方法添加final指示符，但却不能为那个方法提供任何额外的含义

Q：合成还是继承

A：

object-oriented programming, the most likely way that you’ll create and use code is by
simply packaging data and methods together into a class, and using objects of that class.
You’ll also use existing classes to build new classes with composition. Less frequently, you’ll
use inheritance. So although inheritance gets a lot of emphasis while learning OOP, it doesn’t mean that you should use it everywhere you possibly can. On the contrary, you should use it sparingly, only when it’s clear that inheritance is useful. One of the clearest ways to determine whether you should use composition or inheritance is to ask whether you’ll ever need to upcast from your new class to the base class. If you must upcast, then inheritance is necessary, but if you don’t need to upcast, then you should look closely at whether you need inheritance. But if you remember to ask “Do I need to upcast?” you’ll have a good tool for deciding between composition and inheritance.

在面向对象的程序设计中，创建和使用代码最可能采取的一种做法是：将数据和方法统一封装到一个类里，并且使用那个类的对象。有些时候，需通过“合成”技术用现成的类来构造新类。而继承是最少见的一种做法。因此，尽管继承在学习OOP的过程中得到了大量的强调，但并不意味着应该尽可能地到处使用它。相反，使用它时要特别慎重。只有在清楚知道继承在所有方法中最有效的前提下，才可考虑它。为判断自己到底应该选用合成还是继承，一个最简单的办法就是考虑是否需要从新类上溯造型回基础类。若必须上溯，就需要继承。但如果不需要上溯造型，就应提醒自己防止继承的滥用。但只要记住经常问自己“我真的需要上溯造型吗”，对于合成还是继承的选择就不应该是个太大的问题。

Q：Java初始化和类装在的顺序

A：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

//: Beetle.java
// The full process of initialization.
class Insect {
  int i = 9;
  int j;
  Insect() {
    prt("i = " + i + ", j = " + j);
    j = 39;
  }
  static int x1 = 
    prt("static Insect.x1 initialized");
  static int prt(String s) {
    System.out.println(s);
    return 47;
  }
}
public class Beetle extends Insect {
  int k = prt("Beetle.k initialized");
  Beetle() {
    prt("k = " + k);
    prt("j = " + j);
  }
  static int x2 =
    prt("static Beetle.x2 initialized");
  static int prt(String s) {
    System.out.println(s);
    return 63;
  }
  public static void main(String[] args) {
    prt("Beetle constructor");
    Beetle b = new Beetle();
  }
} ///:~

输出为：

1
2
3
4
5
6
7

static Insect.x initialized
static Beetle.x initialized
Beetle constructor
i = 9, j = 0
Beetle.k initialized
k = 63
j = 39

对Beetle运行Java时，发生的第一件事情是装载程序到外面找到那个类。在装载过程中，装载程序注意它有一个基础类（即extends关键字要表达的意思），所以随之将其载入。无论是否准备生成那个基础类的一个对象，这个过程都会发生（请试着将对象的创建代码当作注释标注出来，自己去证实）。

若基础类含有另一个基础类，则另一个基础类随即也会载入，以此类推。接下来，会在根基础类（此时是Insect）执行static初始化，再在下一个衍生类执行，以此类推。保证这个顺序是非常关键的，因为衍生类的初始化可能要依赖于对基础类成员的正确初始化。

此时，必要的类已全部装载完毕，所以能够创建对象。首先，这个对象中的所有基本数据类型都会设成它们的默认值，而将对象句柄设为null。随后会调用基础类构建器。在这种情况下，调用是自动进行的。但也完全可以用super来自行指定构建器调用（就象在Beetle()构建器中的第一个操作一样）。基础类的构建采用与衍生类构建器完全相同的处理过程。基础顺构建器完成以后，实例变量会按本来的顺序得以初始化。最后，执行构建器剩余的主体部分。

对象的创建过程，请考虑一个名为Dog的类：

(1) 类型为Dog的一个对象首次创建时，或者Dog类的static方法／static字段首次访问时，Java解释器必须找到Dog.class（在事先设好的类路径里搜索）。

(2) 找到Dog.class后（它会创建一个Class对象），它的所有static初始化模块都会运行。因此，static初始化仅发生一次——在Class对象首次载入的时候。

(3) 创建一个new Dog()时，Dog对象的构建进程首先会在内存堆（Heap）里为一个Dog对象分配足够多的存储空间。

(4) 这种存储空间会清为零，将Dog中的所有基本类型设为它们的默认值（零用于数字，以及boolean和char的等价设定）。

(5) 进行字段定义时发生的所有初始化都会执行。

(6) 执行构建器。

一个类不允许被设置成private或者protected，所以只有两种选择来访问类：包或者public。如果你不想让任何人访问那个类，你可以令所有的构建器private，因此，在class内置一个static方法，可以防止除了你以外的人创建一个此类的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//: access/Lunch.java
// Demonstrates class access specifiers. Make a class
// effectively private with private constructors:
class Soup1 {
  private Soup1() {}
  // (1) Allow creation via static method:
  public static Soup1 makeSoup() {
    return new Soup1();
  }
}
class Soup2 {
  private Soup2() {}
  // (2) Create a static object and return a reference
  // upon request.(The "Singleton" pattern):
  private static Soup2 ps1 = new Soup2();
  public static Soup2 access() {
return ps1; }
  public void f() {}
}
// Only one public class allowed per file:
public class Lunch {
  void testPrivate() {
    // Can’t do this! Private constructor:
    //! Soup1 soup = new Soup1();
  }
  void testStatic() {
    Soup1 soup = Soup1.makeSoup();
  }
  void testSingleton() {
    Soup2.access().f();
  }
} ///:~

Soup1我们可创建一个static方法，再通过它创建一个新的Soup，然后返回指向它的一个句柄。如果想在返回之前对Soup进行一些额外的操作，或者想了解准备创建多少个Soup对象（可能是为了限制它们的个数），这种方案无疑是特别有用的。

Soup2是采用“设计方案”（Design Pattern）技术。通常方案叫作“独子”（Singleton），因为它仅允许创建一个对象。类Soup的对象被创建成Soup的一个static private成员，所以有一个而且只能有一个。除非通过public方法access()，否则根本无法访问它。

今天正好跟朋友说起赌博过程中的一些事情，我说我几年前第一次去赌场的时候观察转盘，找到了一种规律然后投注赢了钱，他们说这是巧合，不存在某种规律，所以这篇文章想以不严谨的方式来论证其中的一些科学依据。

我刚高考完那年，跟我父母和他们单位的人一起去了港澳旅游，顺便也去了澳门赌场，幸好我刚满18岁一个月，当时就允许我进了赌场。揣着口袋里的150港币就去四处找可以玩的。可惜连最基本的押大小都需要200起………..所以我只能找到了50港币起的一个机器转盘游戏。

网上随便找了一个类似的图，当然在赌场倍数不一样。由图可以看出，这个游戏是轮盘赌博的一类，与正规的轮盘区别是小球改成了指针，而小球的物理滚动变成了此处指针的由于某种程序设置而转动，由此就可以排除轮盘赌博中 小球每一局由于受到不同的物理作用而产生的结果的不可测性（除非我是拉普拉斯的恶魔），指针由于非人为，必定内部存在某种程序，或者给定转盘某种（程序或非程序）的初始加速度，来完成转盘的旋转。

现在我们不管转盘的内部程序或者加速度的变化是什么，假定内部程序是不变的（有此假定是因为非人为操作，内部程序是编好的，或者除非哪个程序员脑子抽了写了一个随机函数），那么根据大数定理，当旋转次数 n→∞ 时，

意思是样本数越多，其平均就越接近期望值，意思是当n趋近于无穷时，里面任何一个数字出现的概率都将接近于一个常数，这就给了我们的推测打下了基础。而我们根本无需管程序内部是什么样的，不论10出现的概率是十分之一，五十分之一还是一百分之一，这都与我们无关，内部程序是一个黑箱，而我们只需要知道他外部输出的概率即可。

当然我们不可能看无穷个结果来推测出每一个数字出现的概率。我们只需要观察n个连续的结果，来大致推测某种概率规律。以上图的转盘为例，假设我们观察了十分钟，输出结果为

1，2，1，3，4，3，4，10，2，2，4，1，1，1.5，2，4，10，1.5，1，3，10

当然我写这个假设的输出结果没有意义，因为我们既然已经知道了上面大数定理的公式，我们就知道某个数字出现的概率是固定的，就知道当n趋近于无穷的时候，概率再小的事情也会发生（其实就是墨菲定律，这是我本科时候理解的大数定理，当然不严谨），就知道每一个数字必然会出现在某个位置（这是一句废话），然而这个必然出现就可以作为我们推理的依据。（当然数学上并不是必然出现，但这样你人品也太差了）

假设10这个数字必然会出现，假设每次出现的概率为1/50，那么当旋转次数n越大，10若没有出现在前一次，它在后一次出现的概率就会比前一次更高（这句话说的不对）。

等等，你或许要问我，这10出现的概率每一次都是1/50，而每一次转盘旋转事件若是相互独立的话，为什么概率会变？其实概率并不是变了，记得前段时间面试题和网上很火的一个问题：抛10次硬币都是正面，那第11次还出正面的概率是多少？

（转自Ent，果壳）

标准的回答是，当然还是二分之一。每次硬币是一个独立事件。硬币没有记忆，不会记得之前发生了什么事情。

“什么！可是连续11次的概率是1/2048啊？”

对，如果你站在第一次扔出来之前，那是这样。但现在已经扔了10次了。前10次扔出任何一个特定结果（比如全是正面）的概率，已经是1/1024了。接下来这一次是正面的概率还是正常的1/2，乘起来正好是1/2048。

或者你可以这么想：前方是一片分岔的小路，一共分岔了11轮，通向2048种不同的可能性。一开始，你面前的所有可能性都真的是可能的。但是你经过第一个分岔，就有1024种对你关闭了；经过第二个，又有512种关闭了……等到你已经经过第10个的时候，面前只剩下最后一个分岔的两条路。那么这两条路，对于此刻的你而言，左的概率也是1/2，右的概率也是1/2。

不然的话，假若左是1/2048，那右难道是2047/2048？如果左右平等，右也是1/2048，那剩下的2046呢？它们都在你已经不可能抵达的那些岔路上，不能计入你眼前的概率了。

“可是……连续11次正面是1/2048啊，多小的概率啊？”

走上任何一条具体的道路，都是一样的。11次随便什么结果都是1/2048，你总得选一个。

“可是，这是连续11次正面啊，不是‘随便什么结果’啊。”

好吧，这就是症结所在：虽然任何特定结果都是等概率的，但是不同的结果有不同的模式。连续11次正面，这个模式在直觉上是不对劲的，而譬如说5正6反这个模式在直觉上没有问题。因为直觉的不对劲，让我们难以老老实实接受1/2这个结果。

那就是直觉错了呗？

也不一定——如果你是个贝叶斯主义者的话。

——————————————

回到一开头。以上全部计算都依赖于一个前提：这是一枚“标准硬币”，它没有记忆，正反概率都是1/2。

等等，你是怎么知道的？

哦，题干里写的。出题人说了是这样，那就是这样呗。

在这个狭小的场景里，这就是一条先验知识。它是“先于经验”而存在的，你并非通过亲身经历而获知它是标准硬币，而是通过出题人（或者上帝或者先天知识或者纯推理或者别的什么奇怪的来源）获得的。如果你相信先验知识的话，那就照办吧。

但是并没有人规定你一定要相信先验知识（虽然在做题的时候，不相信出题人的后果会很惨咯）。如果我不信呢？至少，我觉得我可以用我的观察去修正它呢？

那我就是在用后验知识了。换句话说，贝叶斯。

在这个案例里，我已经见到了连续10次正面。当然，一个标准硬币可以产出这样的结果，只不过概率是1/1024而已。但是，有另外一种可能的解释，那就是这个硬币作弊了。或者它的两面都是正面，或者它的正面那边比反面那边重很多。如果它是一枚作弊的、必定正面的硬币，那么它就会以1的概率出产连续10正，这可比标准硬币更有解释力啊！

那么在这里我们可以说，这10次观察得到了一个后验知识——该硬币有偏向于正面的倾向性。这倾向性有多大？可以算但是很麻烦，这里暂且忽略。但无论如何，如果你是一个贝叶斯主义者，相信直觉，不愿意接受“标准硬币”那个先验知识，那么你应当得出的结论是：下一次硬币为正面的概率大于1/2.

对，是大于。这才是直觉的正确用法。无论你是哪一派的，都不会得出小于1/2的结果。

上面的问题与这个问题无关………但我觉得概率的思想是一样的。

所以如果连续n次转盘都不出现10，那么概率为49/50的n次方，随着n的增大而这个概率在变小，所以说明并不是10出现的概率变大，而是连续不出现10的概率在变小。所以我们就可以适当进行观察，以上面的观察为例，第一次出现10是在第8位，第二次出现10是在第9位，第三次出现10是在第4位。要知道10作为最大的数字，只要赌场的程序员不蠢想赚钱，那么它出现的概率应该是最小的。则在10没有出现的连续序列之后，10出现的概率增大（某种算法的结果）到某一个值之后，假设是1/4，那么下一次出现10的概率会增大到1/4而不是之前的1/50，而在某个临界概率之后，投注10中奖的概率会大大增多。

这个临界概率当然不能算出来，而是通过观察自己大致猜一下。比如上面的序列，我可以猜测在第5个数字之后，10出现的概率能达到我的预期，则我开始投注。或者说你想保守一点，在第6或者第7个数字之后再投注。压地越早，则后续可能出现10的范围越大（极限地想，比如你第一次就开始压10，直到10出现为止）。而压地越晚，即使你后期出现10概率会变大，但指不定10会出现的预期之前（比如你想从1/2左右的概率开始压10，但10出现在了1/4概率的位置），那么又得重新计算。

因此，只要你在合适的位置（合适的概率之后）进行投注，那么理论上，在某个区间之内，必然会出现你所投注的倍数。

毕竟五年过去了，已经找不到当年我记录那转盘的记录了，但我记得当年转盘上最大的数字是50，50毕竟出现的概率太小了，我不知道要等多久才能算出个规律来，所以我记的是12这个倍数。我当时站着看了十几分钟那个转盘，在手机上记下来每一次转出来的数字，记下了12出现的位置和大致的间隔。然后在我大概觉得规律估摸差不多的时候，把我仅有的150块钱拿出50块（坑爹啊，最低投注50，老子可没有身家几千万来玩这个），投在了我觉得可能的出现的时候，然后…………….并没有出现12，so sad，然后我接着下一个又来了一次………然后中了，走了，见好就收。

话说当时的我肯定不会有现在的我想这么多原理，只是觉得可能有这么一种方式可以推出一定的规律。但以上推论说是不严谨，原因之处在于，第一，假定内部程序是个黑箱的稳定函数，即使你把12和50的概率设置再低也无所谓，除非真是脑子进水了，设置的概率是个随机数……..第二是理论归理论，即使连续不出现50的概率在变小，但还是有概率它不会出现，甚至有可能从赌场开业转盘开转，到宇宙寂灭，都不会转出来50………比如概率为0的事情也是有可能发生的……..所以你可能觉得50已经过了50个数字没出现了，然后觉得你发家致富的机会来了，一连投了1000000次都没出现50………….这就是你人品的问题了。

一直幻想着，哪天我本金足够了，不怕用本金来烧概率的时候，就去压50的，毕竟一次就赢2500，算下来我只要误差范围在50次以内，甚至只要赢的时候与50剩余的次数的差，与50次多出来的次数的差是正数，理论上我就能有无限的稳定收入…………

也就是想想而已。

With the this keyword in mind, you can more fully understand what it means to make amethod static. It means that there is no this for that particular method. You cannot call non-static methods from inside static methods

[^The one case in which this is possible occurs if you pass a reference to an object into the static method (the static method could also create its own object). Then, via the reference (which is now effectively this), you can call non-static methods and access non-static fields. But typically, if you want to do something like this, you’ll just make an ordinary, non-static method.]:

(although the reverse is possible), and you can call a static method for the class itself, without any object. In fact, that’s primarily what a static method is for. It’s as if you’re creating the equivalent of a global method. However,global methods are not permitted in Java, and putting the static method inside a class allowsit access to other static methods and to static fields.

Some people argue that static methods are not object-oriented, since they do have the semantics of a global method; with a static method, you don’t send a message to an object, since there’s no this. This is probably a fair argument, and if you find yourself using a lot of static methods, you should probably rethink your strategy. However, statics are pragmatic,and there are times when you genuinely need them, so whether or not they are “proper OOP” should be left to the theoreticians.

先定义一些排序算法通用的API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Sort{
  public static void sort(Comparable[] a){
    // 新建排序算法对象
    Quick quick = new Quick();
    quick.sort(a);
  }
  
  protected static boolean less(Comparable v, Comparable w){
    return (v.compareTo(w) < 0);
  }
  
  protected static void exc (Comparable[] a, int i, int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
  
  protected static void show(Comparable[] a){
    for (int i =0; i<a.length; i++)
    	System.out.print(a[i] + " ");
    System.out.println();
  }
  
  protected static boolean isSorted(Comparable[] a){
    for (int i=0; i<a.length; i++)
    	if (less(a[i], a[i+1])) return false;
    return true;
  }
  
  public static void main(String[] args){
    Comparable[] a = {'A','R','E','U','K','I','D','D','I','N','G','M','E'};
    sort(a);
    assert isSorted(a);
    show(a);
  }
}

插入排序 / Insertion Sort

1
2
3
4
5
6
7
8
9

public class Insertion extends Sort{
  public static void sort(Comparable[] a){
    int N = a.length;
    for (int i=0; i<N; i++){
      for (int j = i; j>0 && less(a[j],a[j-1]); j--)
      	exc(a,j,j-1);
    }
  }
}

选择排序 / Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12

public class Selection extends Sort{
  public static void sort(Comparable[] a){
    int N = a.length;
    for (int i=0; i<N; i++){
      int min = i;
      for (int j=i+1; j<N; j++){
        if (less(a[j],a[min])) min = j;
      }
      exc(a,i,min);
    }
  }
}

希尔排序 / Shell Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Shell extends Sort{
  public static void sort(Comparable[] a){
    int N = a.length();
    int h = 1;
    while (h < N/3) (h = 3*h + 1);
    while (h >= 1){
      for (int i=h; i<N; i++){
        for (int j=i; j>=h && less(a[j],a[j-h]); j-=h)
        	exc(a,j,j-h);
      }
      h = h/3;
    }
  }
}

归并排序 / Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Merge extends Sort{
  
  private static Comparable[] aux;
  
  public static void sort(Comparable[] a){
    aux = new Comparable[a.length];
    sort(a,0,a.length-1);
  }
  
  public static void sort(Comparable[] a, int lo, int hi){
    if (hi<=lo) return;
    int mid = lo + (hi-lo)/2;
    sort(a,lo,mid);
    sort(a,mid,hi);
    Merge(a,lo,mid,hi);
  }
  
  public static void Merge(Comparable[] a, int lo, int mid, int hi){
    int i = lo;
    int j = mid + 1;
    for (int k=lo; k<=hi; k++) aux[k] = a[k];
    for (int k=lo; k<=hi; k++){
      if (i>mid) a[k] = aux[j++];
      else if (j>hi) a[k] = aux[i++];
      else if (less(aux[i],aux[j])) a[k] = aux[i++];
      else a[k] = a[j++];
    }
  }  
}

快速排序 / Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Quick extends Sort{
  public static void sort(Comparable[] a){
    StdRandom.shuffle(a);
    sort(a, 0, a.length);
  }
  
  public static void sort(Comparable[] a, int lo, int hi){
    if (hi<=lo) return;
    int j = partition(a,lo,hi);
    sort(a,lo,j-1);
    sort(a,j+1,hi);
  }
  
  public static int partition(Comparable[] a, int lo, int hi){
    int i = lo;
    int j = hi+1;
    Comparable v = a[lo];
    while (true){
      while (less(a[++i],v)) if (i == hi) break;
      while (less(v,a[--j])) if (j == lo) break;
      if (i >= j) break;
      exc(a,i,j);
    }
    // 跟 j 交换位置，因为 i 此时位置在 a[i] > v 处而 a[j] < v
    exc (a,lo,j);
    return j;
  }
}

三向切分快速排序 / Quick 3 Ways

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Quick3Way extends Quick{
  public static void sort(Comparable[] a, int lo, int hi){
    if (lo>=hi) return;
    int i = lo+1;
    int gt = hi;
    int lt = lo;
    Comparable v = a[lo];
    while ( i <= gt ){
      int cm = v.compareTo(a[i]);
      if (cm > 0) exc(a,i,gt--);
      else if (cm < 0) exc(a,lt++,i++);
      else i++;
    }
    sort(a,lo,lt-1);
    sort(a,gt+1,hi);
  }
}

堆排 / StackSort

数组最大堆：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

public class MaxPQ<Key extends Comparable<Key>> {
  private Key[] pq;
  private N = 0;
  
  public boolean less(int i, int j){
    return pq[i].compareTo(pq[j]) < 0;
  }
  
  public void exc(int i, int j){
    Key temp;
    temp = pq[i];
    pq[i] = pq[j];
    pq[j] = temp;
  }
  
  public void swin(int k){
    while (k>1 && less(k/2,k)){
      exc(k/2,k);
      k /= 2;
    }
  }
  
  public void sink(int k){
    while (2*k <= N){
      int j = 2*k;
      if (j<N && less(2*k, 2*k+1)) j++;
      if (!less(k,j)) break;
      exc(k,j);
      k = j;
    }
  }
  
  public MaxPQ (int maxN){
    pq = (Key[]) new Comparable[maxN+1];
  }
  
  public boolean isEmpty(){
    return N==0;
  }
  
  public void insert(Key v){
    pq[++N] = v;
    swin(N);
  }
  
  public int size(){
    return N;
  }
  
  public Key delMax(){
    Key max = pq[1];
    exc(N--,1);
    pq[N+1] = null;
    sink(1);
    return max;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class StackSort{
  
  private Comparable[] a;
  private int N = a.length;
  
  public void StackSort(int max){
    a = new Comparable[max];
  }
  
  public void sort(Comparable[] a){
    for (int k = a.length/2; k>=1; k--)
    	sink(k);
    while (N>1){
      exc(N--,1);
      sink(N);
    }
  }
  
  public boolean less(int i, int j){
    return a[i].compareTo(j) < 0;
  }
  
  piublic void sink(int k){
    while (2*k <= a.length){
      int j = 2*k;
      if (less(j,j+1)) j++;
      if (!less(k,j)) break;
      exc(k,j);
      k = j;
    }
  }
  
  public void exc(int i, int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
  }
}

就这么多吧。

The constructor is an unusual type of method because it has no return value. This is distinctly different from a void return value, in which the method returns nothing but you still have option to make it return something else. Constructors return nothing and you don’t have an option (the new expression does return a reference to the newly created object, but the constructor itself has no return value).

构造器是一种特殊的Method，因为它没有返回值，这个跟void空返回值有很大的区别。因为即使void method本身不会返回什么，你依旧可以让它返回一些东西。构造器不会返回任何东西，你也没有任何选择让它返回什么东西。

Java运算符记录本，以此记下容易出错的地方。

来自于 Thinking in Java

Relational Operators

The relational operators == and != also work with all objects. Here is an example:

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Equivalence{
  public static void main (String[] args){
    Integer n1 = new Integer(47);
    Integer n2 = new Integer(47);
    System.out.println(n1 == n2);
    System.out.println(n1 != n2);
  }
}
/* Output:
false
true
*/

The statement System.out.println(n1==n2) will print the result of the boolean comparison within it. While the contents of the objects are the same, the references are not the same. The operators == and != compare object references, so the output is actually “false” and then “true”.

What if we want to compare the actual contents of an object for equivalences? We must use the special method equals() that exits for all objects (not primitives, which work fine with == and !=). Example:

1
2
3
4
5
6
7
8
9

public class EqualsMethod{
  public static void main(String[] args){
    Integer n1 = new Integer(47);
    Integer n2 = new Integer(47);
    System.out.printly(n1.equals(n2));
  }
}
/* Output: true */

But default equals() does not compare contents. Here is an example:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Value{
  int i;
}
public class EqualsMethod2{
  public static void main(String[] args){
    Value v1 = new Value();
    Value v2 = new Value();
    v1.i = v2.i = 100;
    System.out.println(v1.equals(v2));
  }
}
/* Output: false */

The result is false. This is because the default behavior of equals() is to compare references. So unless you override equals() in your new class you won’t get the desired behavior. Most of the Java library classes implement equals() so that it compares the contents of objects instead of their references.

Bitwise Operators

The bitwise operators allow you to manipulate individual bits in an integral primitive data type. Bitwise operators perform Boolean algebra on the corresponding bits in the two arguments to produce the result.

The bitwise operators come from C’s low-level orientation, where you often manipulate hardware directly and must set the bits in hardware registers. Java was originally designed to be embedded in TV set-top boxes, so this low-level orientation still made sense.

The bitwise AND operator (&) produces a one in the output bit if both input bits are one; otherwise, it produces a zero.

1
2
3
4
5
6
7
8
9
10
11
12
13

// Example
class Bitwise{
  public static void main(String[] args){
    int a = 129;
    int b = 128;
    System.out.println(a&b);
  }
}
/* Output: 128;
Integer.toBinaryString(a)   is 10000001;
Integer.toBinaryString(b)   is 10000000;
Integer.toBinaryString(a&b) is 10000000; */

The bitwise OR operator (|) produces a one in the output bit if either input is a one and produces a zero only if both input bits are zero.

1
2
3
4
5
6
7
8
9
10
11
12
13

// Example
class Bitwise{
  public static void main(String[] args){
    int a = 129;
    int b = 128;
    System.out.println(a|b);
  }
}
/* Output: 129;
Integer.toBinaryString(a)   is 10000001;
Integer.toBinaryString(b)   is 10000000;
Integer.toBinaryString(a|b) is 10000001; */

The bitwise EXCLUSIVE OR, or XOR (^) , produces a one in the output bit if one or the other input bit is a one, but not both, which means if the bits are same, producing 0, if the bits are different, producing 1.

1
2
3
4
5
6
7
8
9
10
11
12
13

// Example
class Bitwise{
  public static void main(String[] args){
    int a = 15;
    int b = 2;
    System.out.println(a^b);
  }
}
/* Output: 13;
Integer.toBinaryString(a)   is 1111;
Integer.toBinaryString(b)   is 0010;
Integer.toBinaryString(a^b) is 1101; */

The bitwise NOT, also called the ones complement operator, (~), is a unary operator; it takes only one argument. (All other bitwise operators are binary operators.) Bitwise NOT produces the opposite of the input bit - a one if the input bit is zero, a zero if the input bit is one.

1
2
3
4
5
6
7
8
9
10

// Example
class Bitwise{
  public static void main(String[] args){
    int a = 2;
    System.out.println(~a);
  }
}
/* Output: -3;
Integer.toBinaryString(a)  is 10;
Integer.toBinaryString(~a) is 1111 1111 1111 1111 1111 1111 1111 1101; */