发表于 | 分类于

　　观察者（Observer）模式的定义：指多个对象间存在一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。这种模式有时又称作发布-订阅模式、模型-视图模式，它是对象行为型模式。

结构

实现观察者模式时要注意具体目标对象和具体观察者对象之间不能直接调用，否则将使两者之间紧密耦合起来，这违反了面向对象的设计原则。

观察者模式的主要角色如下：

1、抽象主题（Subject）角色：也叫抽象目标类，它提供了一个用于保存观察者对象的聚集类和增加、删除观察者对象的方法，以及通知所有观察者的抽象方法。

2、具体主题（Concrete Subject）角色：也叫具体目标类，它实现抽象目标中的通知方法，当具体主题的内部状态发生改变时，通知所有注册过的观察者对象。

3、抽象观察者（Observer）角色：它是一个抽象类或接口，它包含了一个更新自己的抽象方法，当接到具体主题的更改通知时被调用。

4、具体观察者（Concrete Observer）角色：实现抽象观察者中定义的抽象方法，以便在得到目标的更改通知时更新自身的状态。

应用场景

1、对象间存在一对多关系，一个对象的状态发生改变会影响其他对象。

2、当一个抽象模型有两个方面，其中一个方面依赖于另一方面时，可将这二者封装在独立的对象中以使它们可以各自独立地改变和复用。

优缺点

观察者模式是一种对象行为型模式，其主要优点如下：
1、降低了目标与观察者之间的耦合关系，两者之间是抽象耦合关系。
2、目标与观察者之间建立了一套触发机制。

它的主要缺点如下：
1、目标与观察者之间的依赖关系并没有完全解除，而且有可能出现循环引用。
2、当观察者对象很多时，通知的发布会花费很多时间，影响程序的效率。

代码实现

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
59
60
61
62
63
64
65
66
67
68
69
//抽象目标
abstract class Subject
{
    protected List<Observer> observers=new ArrayList<Observer>();   
    //增加观察者方法
    public void add(Observer observer)
    {
        observers.add(observer);
    }    
    //删除观察者方法
    public void remove(Observer observer)
    {
        observers.remove(observer);
    }   
    public abstract void notifyObserver(); //通知观察者方法
}

//具体目标
class ConcreteSubject extends Subject
{
    public void notifyObserver()
    {
        System.out.println("具体目标发生改变...");
        System.out.println("--------------");       
       
        for(Object obs:observers)
        {
            ((Observer)obs).response();
        }
       
    }          
}

//抽象观察者
interface Observer
{
    void response(); //反应
}

//具体观察者1
class ConcreteObserver1 implements Observer
{
    public void response()
    {
        System.out.println("具体观察者1作出反应！");
    }
}
//具体观察者2
class ConcreteObserver2 implements Observer
{
    public void response()
    {
        System.out.println("具体观察者2作出反应！");
    }
}

//Client
public class ObserverPattern
{
    public static void main(String[] args)
    {
        Subject subject=new ConcreteSubject();
        Observer obs1=new ConcreteObserver1();
        Observer obs2=new ConcreteObserver2();
        subject.add(obs1);
        subject.add(obs2);
        subject.notifyObserver();
    }
}

发表于 | 分类于

命令（Command）模式的定义如下：将一个请求封装为一个对象，使发出请求的责任和执行请求的责任分割开。这样两者之间通过命令对象进行沟通，这样方便将命令对象进行储存、传递、调用、增加与管理。

优点： 1、降低了系统耦合度。 2、新的命令可以很容易添加到系统中去。 3、可以比较容易地设计一个组合命令(宏命令)。

缺点：使用命令模式可能会导致某些系统有过多的具体命令类。

适用场景

1.命令的发送者和命令执行者有不同的生命周期。命令发送了并不是立即执行。
2.命令需要进行各种管理逻辑（当系统需要执行一组操作时，命令模式可以定义宏命令来实现该功能）。
3.需要支持撤消\重做操作，可以将命令对象存储起来，采用备忘录模式来实现。

结构与实现

命令模式是对命令的封装。命令模式把发出命令的责任和执行命令的责任分割开，委派给不同的对象。

每一个命令都是一个操作：请求的一方发出请求要求执行一个操作；接收的一方收到请求，并执行操作。命令模式允许请求的一方和接收的一方独立开来，使得请求的一方不必知道接收请求的一方的接口，更不必知道请求是怎么被接收，以及操作是否被执行、何时被执行，以及是怎么被执行的。

命令模式涉及到五个角色，它们分别是：
1、客户端(Client)角色：创建一个具体命令(ConcreteCommand)对象并确定其接收者。
2、命令(Command)角色：声明了一个给所有具体命令类的抽象接口。
3、具体命令(ConcreteCommand)角色：定义一个接收者和行为之间的弱耦合；实现execute()方法，负责调用接收者的相应操作。execute()方法通常叫做执行方法。
4、请求者(Invoker)角色：负责调用命令对象执行请求，相关的方法叫做行动方法。
5、接收者(Receiver)角色：负责具体实施和执行一个请求。任何一个类都可以成为接收者，实施和执行请求的方法叫做行动方法。

代码实现：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//接收者角色类
public class Receiver {
    /**
     * 真正执行命令相应的操作
     */
    public void action(){
        System.out.println("执行操作");
    }
}

//抽象命令角色类
public interface Command {
    /**
     * 执行方法
     */
    void execute();
}

//具体命令角色类
public class ConcreteCommand implements Command {
    //持有相应的接收者对象
    private Receiver receiver = null;
    /**
     * 构造方法
     */
    public ConcreteCommand(Receiver receiver){
        this.receiver = receiver;
    }
    @Override
    public void execute() {
        //通常会转调接收者对象的相应方法，让接收者来真正执行功能
        receiver.action();
    }

}

//请求者角色类
public class Invoker {
    /**
     * 持有命令对象
     */
    private Command command = null;
    /**
     * 构造方法
     */
    public Invoker(Command command){
        this.command = command;
    }
    /**
     * 行动方法
     */
    public void action(){
        
        command.execute();
    }
}

//客户端角色类
public class Client {

    public static void main(String[] args) {
        //创建接收者
        Receiver receiver = new Receiver();
        //创建命令对象，设定它的接收者
        Command command = new ConcreteCommand(receiver);
        //创建请求者，把命令对象设置进去
        Invoker invoker = new Invoker(command);
        //执行方法
        invoker.action();
    }

}

组合命令模式

在软件开发中，有时将命令模式与组合模式联合使用，这就构成了宏命令模式，也叫组合命令模式。宏命令包含了一组命令，它充当了具体命令与调用者的双重角色，执行它时将递归调用它所包含的所有命令，其具体结构图如图：

程序代码如下：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//抽象命令
interface AbstractCommand
{
    public abstract void execute();
}

//树叶构件: 具体命令1
class ConcreteCommand1 implements AbstractCommand
{
    private CompositeReceiver receiver;
    ConcreteCommand1()
    {
        receiver=new CompositeReceiver();
    }
    public void execute()
    {       
        receiver.action1();
    }
}
//树叶构件: 具体命令2
class ConcreteCommand2 implements AbstractCommand
{
    private CompositeReceiver receiver;
    ConcreteCommand2()
    {
        receiver=new CompositeReceiver();
    }
    public void execute()
    {       
        receiver.action2();
    }
}

//树枝构件: 调用者
class CompositeInvoker implements AbstractCommand
{
    private ArrayList<AbstractCommand> children = new ArrayList<AbstractCommand>();   
    public void add(AbstractCommand c)
    {
        children.add(c);
    }   
    public void remove(AbstractCommand c)
    {
        children.remove(c);
    }   
    public AbstractCommand getChild(int i)
    {
        return children.get(i);
    }   
    public void execute()
    {
        for(Object obj:children)
        {
            ((AbstractCommand)obj).execute();
        }
    }    
}

//接收者
class CompositeReceiver
{
    public void action1()
    {
        System.out.println("接收者的action1()方法被调用...");
    }
    public void action2()
    {
        System.out.println("接收者的action2()方法被调用...");
    }
}

//Client
public class CompositeCommandPattern
{
    public static void main(String[] args)
    {
        AbstractCommand cmd1=new ConcreteCommand1();
        AbstractCommand cmd2=new ConcreteCommand2();
        CompositeInvoker ir=new CompositeInvoker();
        ir.add(cmd1);
        ir.add(cmd2);
        System.out.println("客户访问调用者的execute()方法...");
        ir.execute();
    }
}

程序的运行结果如下：
客户访问调用者的execute()方法...
接收者的action1()方法被调用...
接收者的action2()方法被调用...

发表于 | 分类于

　　解释器（Interpreter）模式的定义：给分析对象定义一个语言，并定义该语言的文法表示，再设计一个解析器来解释语言中的句子。提供了评估语言的语法或表达式的方式，它属于行为型模式。这种模式实现了一个表达式接口，该接口解释一个特定的上下文。这种模式被用在 SQL 解析、符号处理引擎等。

结构

解释器模式包含以下主要角色：
1、抽象表达式（Abstract Expression）角色：定义解释器的接口，约定解释器的解释操作，主要包含解释方法 interpret()。
2、终结符表达式（Terminal Expression）角色：是抽象表达式的子类，用来实现文法中与终结符相关的操作，文法中的每一个终结符都有一个具体终结表达式与之相对应。
3、非终结符表达式（Nonterminal Expression）角色：也是抽象表达式的子类，用来实现文法中与非终结符相关的操作，文法中的每条规则都对应于一个非终结符表达式。
4、环境（Context）角色：通常包含各个解释器需要的数据或是公共的功能，一般用来传递被所有解释器共享的数据，后面的解释器可以从这里获取这些值。
5、客户端（Client）：主要任务是将需要分析的句子或表达式转换成使用解释器对象描述的抽象语法树，然后调用解释器的解释方法，当然也可以通过环境角色间接访问解释器的解释方法。

应用场景

1、当语言的文法较为简单，且执行效率不是关键问题时。
2、当问题重复出现，且可以用一种简单的语言来进行表达时。
3、当一个语言需要解释执行，并且语言中的句子可以表示为一个抽象语法树的时候，如 XML 文档解释。

优缺点

解释器模式是一种类行为型模式，其主要优点如下：
1、扩展性好。由于在解释器模式中使用类来表示语言的文法规则，因此可以通过继承等机制来改变或扩展文法。
2、容易实现。在语法树中的每个表达式节点类都是相似的，所以实现其文法较为容易。

解释器模式的主要缺点如下：
1、执行效率较低。解释器模式中通常使用大量的循环和递归调用，当要解释的句子较复杂时，其运行速度很慢，且代码的调试过程也比较麻烦。
2、会引起类膨胀。解释器模式中的每条规则至少需要定义一个类，当包含的文法规则很多时，类的个数将急剧增加，导致系统难以管理与维护。
3、可应用的场景比较少。在软件开发中，需要定义语言文法的应用实例非常少，所以这种模式很少被使用到。

代码实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public interface Expression {
   public boolean interpret(String context);
}

public class TerminalExpression implements Expression {
   
   private String data;
 
   public TerminalExpression(String data){
      this.data = data; 
   }
 
   @Override
   public boolean interpret(String context) {
      if(context.contains(data)){
         return true;
      }
      return false;
   }
}	

public class OrExpression implements Expression {
    
   private Expression expr1 = null;
   private Expression expr2 = null;
 
   public OrExpression(Expression expr1, Expression expr2) { 
      this.expr1 = expr1;
      this.expr2 = expr2;
   }
 
   @Override
   public boolean interpret(String context) {      
      return expr1.interpret(context) || expr2.interpret(context);
   }
}

public class AndExpression implements Expression {
    
   private Expression expr1 = null;
   private Expression expr2 = null;
 
   public AndExpression(Expression expr1, Expression expr2) { 
      this.expr1 = expr1;
      this.expr2 = expr2;
   }
 
   @Override
   public boolean interpret(String context) {      
      return expr1.interpret(context) && expr2.interpret(context);
   }
}

public class InterpreterPatternDemo {
 
   //规则：Robert 和 John 是男性
   public static Expression getMaleExpression(){
      Expression robert = new TerminalExpression("Robert");
      Expression john = new TerminalExpression("John");
      return new OrExpression(robert, john);    
   }
 
   //规则：Julie 是一个已婚的女性
   public static Expression getMarriedWomanExpression(){
      Expression julie = new TerminalExpression("Julie");
      Expression married = new TerminalExpression("Married");
      return new AndExpression(julie, married);    
   }
 
   public static void main(String[] args) {
      Expression isMale = getMaleExpression();
      Expression isMarriedWoman = getMarriedWomanExpression();
 
      System.out.println("John is male? " + isMale.interpret("John"));
      System.out.println("Julie is a married women? " 
      + isMarriedWoman.interpret("Married Julie"));
   }
}

发表于 | 分类于

　　责任链（Chain of Responsibility）是一种对象的行为模式：很多对象由每一个对象对其下家的引用而连接起来形成一条链，请求在这个链上传递，直到链上的某一个对象决定处理此请求；发出这个请求的客户端并不知道链上的哪一个对象最终处理这个请求，这使得系统可以在不影响客户端的情况下动态地重新组织和分配责任。

结构

在责任链模式中，客户只需要将请求发送到责任链上即可，无须关心请求的处理细节和请求的传递过程，所以责任链将请求的发送者和请求的处理者解耦了。

职责链模式主要包含以下角色:
1.抽象处理者（Handler）角色：定义一个处理请求的接口，包含抽象处理方法和一个后继连接。
2.具体处理者（Concrete Handler）角色：实现抽象处理者的处理方法，判断能否处理本次请求，如果可以处理请求则处理，否则将该请求转给它的后继者。
3.客户类（Client）角色：创建处理链，并向链头的具体处理者对象提交请求，它不关心处理细节和请求的传递过程。

应用场景

1.有多个对象可以处理一个请求，哪个对象处理该请求由运行时刻自动确定。
2.可动态指定一组对象处理请求，或添加新的处理者。
3.在不明确指定请求处理者的情况下，向多个处理者中的一个提交请求。

优缺点

责任链模式是一种对象行为型模式，其主要优点如下：
1.降低了对象之间的耦合度。该模式使得一个对象无须知道到底是哪一个对象处理其请求以及链的结构，发送者和接收者也无须拥有对方的明确信息。
2.增强了系统的可扩展性。可以根据需要增加新的请求处理类，满足开闭原则。
3.增强了给对象指派职责的灵活性。当工作流程发生变化，可以动态地改变链内的成员或者调动它们的次序，也可动态地新增或者删除责任。
4.责任链简化了对象之间的连接。每个对象只需保持一个指向其后继者的引用，不需保持其他所有处理者的引用，这避免了使用众多的 if 或者 if···else 语句。
5.责任分担。每个类只需要处理自己该处理的工作，不该处理的传递给下一个对象完成，明确各类的责任范围，符合类的单一职责原则。

其主要缺点如下：
1.不能保证每个请求一定被处理。由于一个请求没有明确的接收者，所以不能保证它一定会被处理，该请求可能一直传到链的末端都得不到处理。
2.对比较长的职责链，请求的处理可能涉及多个处理对象，系统性能将受到一定影响。
3.职责链建立的合理性要靠客户端来保证，增加了客户端的复杂性，可能会由于职责链的错误设置而导致系统出错，如可能会造成循环调用。

纯与不纯

职责链模式存在以下两种情况：
1.纯的职责链模式：一个请求必须被某一个处理者对象所接收，且一个具体处理者对某个请求的处理只能采用以下两种行为之一：自己处理（承担责任）；把责任推给下家处理。
2.不纯的职责链模式：允许出现某一个具体处理者对象在承担了请求的一部分责任后又将剩余的责任传给下家的情况，且一个请求可以最终不被任何接收端对象所接收。
纯的责任链模式的实际例子很难找到，一般看到的例子均是不纯的责任链模式的实现。

代码实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
public class ChainOfResponsibilityPattern
{
    public static void main(String[] args)
    {
        //组装责任链 
        Handler handler1=new ConcreteHandler1(); 
        Handler handler2=new ConcreteHandler2(); 
        handler1.setNext(handler2); 
        //提交请求 
        handler1.handleRequest("two");
    }
}
//抽象处理者角色
abstract class Handler
{
    private Handler next;
    public void setNext(Handler next)
    {
        this.next=next; 
    }
    public Handler getNext()
    { 
        return next; 
    }   
    //处理请求的方法
    public abstract void handleRequest(String request);       
}
//具体处理者角色1
class ConcreteHandler1 extends Handler
{
    public void handleRequest(String request)
    {
        if(request.equals("one")) 
        {
            System.out.println("具体处理者1负责处理该请求！");       
        }
        else
        {
            if(getNext()!=null) 
            {
                getNext().handleRequest(request);             
            }
            else
            {
                System.out.println("没有人处理该请求！");
            }
        } 
    } 
}
//具体处理者角色2
class ConcreteHandler2 extends Handler
{
    public void handleRequest(String request)
    {
        if(request.equals("two")) 
        {
            System.out.println("具体处理者2负责处理该请求！");       
        }
        else
        {
            if(getNext()!=null) 
            {
                getNext().handleRequest(request);             
            }
            else
            {
                System.out.println("没有人处理该请求！");
            }
        } 
    }
}

发表于 | 分类于

状态模式定义：对象行为的变化是由于状态的变化引入，那么即当内部状态发生变化的时候，就会改变对象的行为，而这种改变视乎就改变了整个类。

结构

很多人在说状态模式的时候总拿策略模式来进行对比，可能他们的类图会有一点类似。最根本的差异在于策略模式是在求解同一个问题的多种解法，这些不同解法之间毫无关联；状态模式则不同，状态模式要求各个状态之间有所关联，以便实现状态转移。

1、Context
定义客户感兴趣的接口。维护一个ConcreteState子类的实例，这个实例定义当前状态。
2、State
定义一个接口以封装与Context的一个特定状态相关的行为。
3、ConcreteStatesubclasses
每一子类实现一个与Context的一个状态相关的行为。

应用场景

1、一个对象的行为取决于它的状态,并且它必须在运行时刻根据状态改变它的行为。
2、一个操作中含有庞大的多分支的条件语句，且这些分支依赖于该对象的状态。 这个状态通常用一个或多个枚举常量表示。通常,有多个操作包含这一相同的条件结构。State模式将每一个条件分支放入一个独立的类中。这使得你可以根据对象自身的情况将对象的状态作为一个对象，这一对象可以不依赖于其他对象而独立变化。

优缺点

优点：
1、降低程序的复杂度；
2、提高程序的可维护性；
3、状态机模式体现了开闭原则和单一职责原则。每个状态都是一个子类，增加状态就要增加子类；修改状态只要修改一个类就行了。

缺点：
使用状态机子类会增多，也就是类膨胀，这点需要程序员在开发中自己衡量。

代码实现

定义State

1
2
3
4
5
//定义和Context中的状态相对应的行为
 public interface State {
     //获取天气情况
     String getState();
 }

定义ConcreteStatesubclasses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Sunshine implements State{
 
    @Override
    public String getState() {
         
        return "晴天";
    }
     
}
class Rain implements State{
 
    @Override
    public String getState() {
         
        return "下雨";
    }
     
}

定义Context

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定义当前的状态
 public class Context {
  
    private State state;
  
    public State getState() {
        return state;
    }
 
    public void setState(State state) {
        this.state = state;
    }
    public String stateMessage(){
        return state.getState();
    }
}

调用类

1
2
3
4
5
6
7
8
9
10
11
12
public class StateTest {
  
     public static void main(String args[]){
         Context context=new Context();
         context.setState(new Rain());
 
         System.out.println(context.stateMessage());
 
         context.setState(new Sunshine());
         System.out.println(context.stateMessage());
     }
 }

和策略模式的区别和联系

区别：
状态模式将各个状态所对应的操作分离开来，即对于不同的状态，由不同的子类实现具体操作，不同状态的切换由子类实现，当发现传入参数不是自己这个状态所对应的参数，则自己给Context类切换状态；而策略模式是直接依赖注入到Context类的参数进行选择策略，不存在切换状态的操作联系。

联系：
状态模式和策略模式都是为具有多种可能情形设计的模式，把不同的处理情形抽象为一个相同的接口，符合对扩展开放，对修改封闭的原则。还有就是，策略模式更具有一般性一些，在实践中，可以用策略模式来封装几乎任何类型的规则，只要在分析过程中听到需要在不同实践应用不同的业务规则，就可以考虑使用策略模式处理，在这点上策略模式是包含状态模式的功能的，策略模式是一个重要的设计模式。

发表于 | 分类于

策略模式（Strategy Pattern），将各种算法封装到具体的类中，作为一个抽象策略类的子类，使得它们可以互换。客户端可以自行决定使用哪种算法。

结构

策略模式是对算法的包装，是把使用算法的责任和算法本身分割开来，委派给不同的对象管理。策略模式通常把一个系列的算法包装到一系列的策略类里面，作为一个抽象策略类的子类。用一句话来说，就是：“准备一组算法，并将每一个算法封装起来，使得它们可以互换”。下面就以一个示意性的实现讲解策略模式实例的结构。

这个模式涉及到三个角色：
　　●　环境(Context)角色：持有一个Strategy的引用。
　　●　抽象策略(Strategy)角色：这是一个抽象角色，通常由一个接口或抽象类实现。此角色给出所有的具体策略类所需的接口。
　　●　具体策略(ConcreteStrategy)角色：包装了相关的算法或行为。

认识策略模式

1、策略模式的重心
　　策略模式的重心不是如何实现算法，而是如何组织、调用这些算法，从而让程序结构更灵活，具有更好的维护性和扩展性。

2、算法的平等性
　　策略模式一个很大的特点就是各个策略算法的平等性。对于一系列具体的策略算法，大家的地位是完全一样的，正因为这个平等性，才能实现算法之间可以相互替换。所有的策略算法在实现上也是相互独立的，相互之间是没有依赖的。
　　所以可以这样描述这一系列策略算法：策略算法是相同行为的不同实现。

3、运行时策略的唯一性
　　运行期间，策略模式在每一个时刻只能使用一个具体的策略实现对象，虽然可以动态地在不同的策略实现中切换，但是同时只能使用一个。

4、公有的行为
　　经常见到的是，所有的具体策略类都有一些公有的行为。这时候，就应当把这些公有的行为放到共同的抽象策略角色Strategy类里面。当然这时候抽象策略角色必须要用Java抽象类实现，而不能使用接口。
　　这其实也是典型的将代码向继承等级结构的上方集中的标准做法。

优点

　　（1）策略模式提供了管理相关的算法族的办法。策略类的等级结构定义了一个算法或行为族。恰当使用继承可以把公共的代码移到父类里面，从而避免代码重复。
　　（2）使用策略模式可以避免使用多重条件(if-else)语句。多重条件语句不易维护，它把采取哪一种算法或采取哪一种行为的逻辑与算法或行为的逻辑混合在一起，统统列在一个多重条件语句里面，比使用继承的办法还要原始和落后。
　　（3）策略模式提供了对“开闭原则”的完美支持，用户可以在不修改原有系统的基础上选择算法（策略），并且可以灵活地增加新的算法（策略）。

缺点

　　（1）客户端必须知道所有的策略类，并自行决定使用哪一个策略类。这就意味着客户端必须理解这些算法的区别，以便适时选择恰当的算法类。换言之，策略模式只适用于客户端知道算法或行为的情况。
　　（2）由于策略模式把每个具体的策略实现都单独封装成为类，如果备选的策略很多的话，那么对象的数目就会很可观。

代码

环境角色类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Context {
    //持有一个具体策略的对象
    private Strategy strategy;

    /**
     * 构造函数，传入一个具体策略对象
     * @param strategy    具体策略对象
     */
    public Context(Strategy strategy){
        this.strategy = strategy;
    }

    /**
     * 策略方法
     */
    public void contextInterface(){
        
        strategy.strategyInterface();
    }
}

抽象策略类

1
2
3
4
5
6
public interface Strategy {
    /**
     * 策略方法
     */
    public void strategyInterface();
}

具体策略类

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
public class ConcreteStrategyA implements Strategy {

    @Override
    public void strategyInterface() {
        //相关的业务
    }

}

public class ConcreteStrategyB implements Strategy {

    @Override
    public void strategyInterface() {
        //相关的业务
    }

}

public class ConcreteStrategyC implements Strategy {

    @Override
    public void strategyInterface() {
        //相关的业务
    }

}

客户端调用代码

1
2
3
4
5
6
7
8
9
10
11
12
public class SimpleClient {

  public static void main(String[] args) {
	//选择并创建需要使用的策略对象
    Strategy strategy = new ConcreteStrategyA();
	//创建环境
    Context context = new Context(strategy);
	//执行
    context.contextInterface();
  }

}

从上面的示例可以看出，策略模式仅仅封装算法，提供新的算法插入到已有系统中，以及老算法从系统中“退休”的方法，策略模式并不决定在何时使用何种算法。在什么情况下使用什么算法是由客户端决定的。

和工厂模式的区别

在模式结构上，两者很相似。

差异：
1.用途不一样
工厂是创建型模式,它的作用就是创建对象；
策略是行为型模式,它的作用是让一个对象在许多行为中选择一种行为;

2.关注点不一样
一个关注对象创建
一个关注行为的封装

3.解决不同的问题
工厂模式是创建型的设计模式，它接受指令，创建出符合要求的实例；它主要解决的是资源的统一分发，将对象的创建完全独立出来，让对象的创建和具体的使用客户无关。主要应用在多数据库选择，类库文件加载等。
策略模式是为了解决的是策略的切换与扩展，更简洁的说是定义策略族，分别封装起来，让他们之间可以相互替换，策略模式让策略的变化独立于使用策略的客户。

4.工厂相当于黑盒子，策略相当于白盒子；

发表于 | 分类于

工厂模式

提供一个用于创建对象的接口(工厂接口)，让其实现类(工厂实现类)决定实例化哪一个类(产品类)，并且由该实现类创建对应类的实例。

工厂方法使一个类的实例化延迟到其子类。如图所示，Product抽象类负责定义产品的共性，实现对事物最抽象的定义，Creator为抽象工厂类，具体如何创建产品类由具体的实现工厂ConcreteCreator来完成。

通用模板代码

1
2
3
4
5
6
7
8
public abstract class Product {
	
	public void method() { //产品类的公共方法，已经实现
		//实现了公共的逻辑
	}
	
	public abstract void method2(); //非公共方法，需要子类具体实现
}

具体产品类可以有多个，都继承与抽象类Product，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class ConcreateProduct1 extends Product {
	
	@Override
	public void method2() {
		//product1的业务逻辑
	}
}
public class ConcreateProduct2 extends Product {
 
	@Override
	public void method2() {
		//product2的业务逻辑
	}
}

抽象工厂类负责定义产品对象的产生，代码如下：

1
2
3
4
public abstract class Creator {
	//创建一个产品对象，其输入参数类型可以自行设置
	public abstract <T extends Product> T createProduct(Class<T> clazz);
}

这里用的是泛型，传入的对象必须是Product抽象类的实现类。具体如何产生一个产品的对象，是由具体工厂类实现的，具体工厂类继承这个抽象工厂类：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ConcreteCreator extends Creator {
 
	@Override
	public <T extends Product> T createProduct(Class<T> clazz) {
		Product product = null;
		try {
			product = (Product) Class.forName(clazz.getName()).newInstance();
		} catch (Exception e) { //异常处理
			e.printStackTrace();
		}
		return (T) product;
	}
}

通过这样的设计，我们就可以在测试类中随意生产产品了，看下面的测试类：

1
2
3
4
5
6
7
8
9
10
11
public class FactoryTest {
 
	public static void main(String[] args) {
		Creator factory = new ConcreteCreator();
		Product product1 = factory.createProduct(ConcreteProduct1.class); //通过不同的类创建不同的产品
 		Product product2 = factory.createProduct(ConcreteProduct2.class);
		 /*
		  * 下面继续其他业务处理
		  */
	 }
}

多个工厂模式

每个具体的工厂都已经非常明确自己的职责：创建自己负责的产品类对象。

1
2
3
public abstract class Creator {
	public abstract Product createProduct();
}

注意抽象方法中已经不需要再传递相关类的参数了，因为每个具体的工厂都已经非常明确自己的职责：创建自己负责的产品类对象。所以不同的工厂实现自己的createProduct方法即可：

1
2
3
4
5
6
7
8
9
10
public class Concrete1Creator extends Creator {
	public Product createProduct() {
		return new ConcreteProduct1();
	}
}
public class Concrete2Creator extends Creator {
	public Product createProduct() {
		return new ConcreteProduct2();
	}
}

这样多个不同的工厂就产生了，每个工厂对应只生产自己对应的产品，分工协作，各不影响了！

1
2
3
4
5
6
public class FactoryTest {
	public static void main(String[] args) {
		Human blackMan = new ConcreteCreator1().createProduct(); 
 		Human yellowMan = new ConcreteCreator2().createProduct();
	  }
}

这种工厂模式的好处是职责清晰，结构简单，但是给扩扩展性和可维护性带来了一定的影响，因为如果要扩展一个产品类，就需要建立一个相应的工厂类，这样就增加了扩展的难度。因为工厂类和产品类的数量是相同的，维护时也需要考虑两个对象之间的关系。但是这种模式还是很常用的。

替代单例模式

可以使用静态工厂加反射实现单例模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SingletonFactory {
	private static Singleton instance;
	static {
		try {		
			Class clazz = Class.forName(Singleton.class.getName());
			//获取无参构造方法
			Constructor constructor = clazz.getDeclaredConstructor();
			//设置无参构造方法可访问
			constructor.setAccessible(true);
			//产生一个实例对象
			instance = (Singleton) constructor.newInstance();
		} catch (Exception e) {
			//异常处理
		}
	}
	public static Singleton getInstance() {
		return instance;
	}
}

优点

1.工厂模式具有良好的封装性，代码结构清晰，也有利于扩展。在增加产品类的情况下，只需要适当地修改具体的工厂类或扩展一个工厂类，就可以完成“拥抱变化”。
2.工厂模式可以屏蔽产品类。这一点非常重要，产品类的实现如何变化，调用者都不用关系，只需要关心产品的接口，只要接口保持不变，系统的上层模块就不需要发生变化。
3.工厂模式是典型的解耦框架。高层模块只需要知道产品的抽象类，其他的实现类都不用关心。

简单/静态工厂模式

如果只需要一个工厂就可以把Product生产出来，我干嘛要具体的工厂对象呢？只要使用静态方法就好了。这样一想，把Creator抽象类去掉了，只保留了ConcreteCreator类，同时把method2方法设置成了static类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ConcreteCreator {
 
	@Override
	public static <T extends Product> T createProduct(Class<T> clazz) {
		Product product = null;
		try {
			product = (Product) Class.forName(clazz.getName()).newInstance();
		} catch (Exception e) { //异常处理
			e.printStackTrace();
		}
		return (T) product;
	}
}

在实际项目中，根据需求可以设置成静态工厂类，但是缺点是扩展比较困难。如果就一个工厂，不需要扩展，可以这么设计，仍然是很常用的。

抽象工厂模式

为创建一组相关或相互依赖的对象提供一个接口，而且无需指定他们的具体类。

抽象工厂模式与工厂方法模式的区别

抽象工厂模式是工厂方法模式的升级版本，他用来创建一组相关或者相互依赖的对象。他与工厂方法模式的区别就在于，工厂方法模式针对的是一个产品等级结构；而抽象工厂模式则是针对的是多个产品等级结构。在编程中，通常一个产品结构，表现为一个接口或者抽象类，也就是说，工厂方法模式提供的所有产品都是衍生自同一个接口或抽象类，而抽象工厂模式所提供的产品则是衍生自不同的接口或抽象类。

在抽象工厂模式中，有一个产品族的概念：所谓的产品族，是指位于不同产品等级结构中功能相关联的产品组成的家族。抽象工厂模式所提供的一系列产品就组成一个产品族；而工厂方法提供的一系列产品称为一个等级结构。

优缺点

优点：当一个产品族中的多个对象被设计成一起工作时，它能保证客户端始终只使用同一个产品族中的对象。此外还具有工厂方法模式的优点。

缺点：产品族扩展非常困难，要增加一个系列的某一产品，既要在抽象的 Creator 里加代码，又要在具体的里面加代码。

适用场景：
当需要创建的对象是一系列相互关联或相互依赖的产品族时，便可以使用抽象工厂模式。说的更明白一点，就是一个继承体系中，如果存在着多个等级结构（即存在着多个抽象类），并且分属各个等级结构中的实现类之间存在着一定的关联或者约束，就可以使用抽象工厂模式。假如各个等级结构中的实现类之间不存在关联或约束，则使用多个独立的工厂来对产品进行创建，则更合适一点。

示例

cpu接口和实现类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public interface Cpu {
    void run();

    class Cpu650 implements Cpu {
        @Override
        public void run() {
            //625 也厉害
        }
    }

    class Cpu825 implements Cpu {
        @Override
        public void run() {
            //825 处理更强劲
        }
    }
}

屏幕接口和实现类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public interface Screen {

    void size();

    class Screen5 implements Screen {

        @Override
        public void size() {
            //5寸
        }
    }

    class Screen6 implements Screen {

        @Override
        public void size() {
            //6寸
        }
    }
}

工厂接口

1
2
3
4
5
6
public interface PhoneFactory {

    Cpu getCpu();//使用的cpu

    Screen getScreen();//使用的屏幕
}

具体工厂实现类：小米手机工厂

1
2
3
4
5
6
7
8
9
10
11
public class XiaoMiFactory implements PhoneFactory {
    @Override
    public Cpu getCpu() {
        return new Cpu.Cpu825();//高性能处理器
    }

    @Override
    public Screen getScreen() {
        return new Screen.Screen6();//6寸大屏
    }
}

具体工厂实现类：红米手机工厂

1
2
3
4
5
6
7
8
9
10
11
12
public class HongMiFactory implements PhoneFactory {

    @Override
    public Cpu getCpu() {
        return new Cpu.Cpu650();//高效处理器
    }

    @Override
    public Screen getScreen() {
        return new Screen.Screen5();//小屏手机
    }
}

以上例子可以看出，抽象工厂可以解决一系列的产品生产的需求，对于大批量，多系列的产品，用抽象工厂可以更好的管理和扩展。

总结

无论是简单工厂模式，工厂方法模式，还是抽象工厂模式，他们都属于工厂模式，在形式和特点上也是极为相似的，他们的最终目的都是为了解耦。在使用时，我们不必去在意这个模式到底工厂方法模式还是抽象工厂模式，因为他们之间的演变常常是令人琢磨不透的。经常你会发现，明明使用的工厂方法模式，当新需求来临，稍加修改，加入了一个新方法后，由于类中的产品构成了不同等级结构中的产品族，它就变成抽象工厂模式了；而对于抽象工厂模式，当减少一个方法使的提供的产品不再构成产品族之后，它就演变成了工厂方法模式。

所以，在使用工厂模式时，只需要关心降低耦合度的目的是否达到了。

参考资料

https://blog.csdn.net/eson_15/article/details/51223124
https://www.jianshu.com/p/38493eb4ffbd

发表于 | 分类于

本文给出常见的十种常见排序算法的原理以及 Java 实现，按照是否比较可以分为两大类：

1、 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
  比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

2、 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
  计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr[i]之前有多少个元素，则唯一确定了arr[i]在排序后数组中的位置。
  非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决，算法时间复杂度 O(n) 。
  非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置，所以对数据规模和数据分布有一定的要求。

相关概念：
1、稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
2、不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
3、时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
4、空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡排序

原理：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。

步骤如下：
1、从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。
2、指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。
3、依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。
4、依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。
5、重复上述过程，没排完一轮，比较次数就减少一次。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
public void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length - 1; i++) {
        for(int j = 0; j < arr.length - 1 - i; j++) {
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

简单选择排序

原理：
每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。

步骤如下：
1、给定数组：int[] arr={里面n个数据}；
2、第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arr[1]交换；
3、第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与arr[2]交换；
4、以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与arr[i]交换，直到全部排序完成。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
    int k = i;
    for(int j = k + 1; j < arr.length; j++){// 选最小的记录
        if(arr[j] < arr[k]){ 
            k = j; //记下目前找到的最小值所在的位置
        }
    }
    //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
    if(i != k){  //交换a[i]和a[k]
        int temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }    
}

选择排序总结：
1、N个元素需要排序N-1轮；
2、第i轮需要比较N-i次；
3、N个元素排序，需要比较n（n-1）/2次；
4、选择排序的算法复杂度仍为O（n*n）；
5、相比于冒泡排序，选择排序的交换次数大大减少，因此速度要快于冒泡排序

简单插入排序

原理：
每次执行，把后面的数插入到前面已经排序好的数组中，直到最后一个完成。

详细步骤：
利用插入法对无序数组排序时，我们其实是将数组R划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。
插入排序与打扑克时整理手上的牌非常类似。摸来的第1张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的1张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void InsertSort(int[] arr)
{
    int i, j;
    int n = arr.Length;
    int target;
 
    //假定第一个元素被放到了正确的位置上，这样，仅需遍历1 ~ n-1
    for (i = 1; i < n; i++)
    {
        j = i;
        target = arr[i];
 
        while (j > 0 && target < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            j--;
        }
 
        arr[j] = target;
    }
}

插入排序分析：
1、时间复杂度，由于仍然需要两层循环，插入排序的时间复杂度仍然为O(n*n)。
2、比较次数：在第一轮排序中，插入排序最多比较一次；在第二轮排序中插入排序最多比较二次；以此类推，最后一轮排序时，最多比较N-1次，因此插入排序的最多比较次数为1+2+…+N-1=N*(N-1)/2。尽管如此，实际上插入排序很少会真的比较这么多次，因为一旦发现左侧有比目标元素小的元素，比较就停止了，因此，插入排序平均比较次数为N*(N-1)/4。
3、移动次数：插入排序的移动次数与比较次数几乎一致，但移动的速度要比交换的速度快得多。
综上，插入排序的速度约比冒泡排序快一倍（比较次数少一倍），比选择排序还要快一些，对于基本有序的数据，插入排序的速度会很快，是简单排序中效率最高的排序算法。

快速排序

原理：
选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。然后对这两部分分别重复这个过程，直到整个有序。

算法思想：
基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。

例子：
待划分数据：7, 6, 9, 8, 5,1，假设阈值为5
第一轮：左指针指向7，右指针指向1，左指针向后移，右指针向左移，发现左面第一个大于5的元素7，右面第一个小于5的元素1，交换7和1的位置，结果：1,6,9,8,5,7；
第二轮：从6开始找大于5的数字，找到6，右边从5起找小于5的数字，找到1，但此时由于6在1的右面，，即右指针<左指针，左右指针交叉，此时划分结束。原数列被划分为两部分，左侧子数列只有一个元素，即为1，其为小于阈值的子数列；右侧子数列包括5个元素，均为大于阈值5的元素。

对于基准位置的选取一般有三种方法：固定切分，随机切分和三取样切分。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N2).对于三数取中选择基准点是最理想的一种。
三数取中切分：

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
public static int partition(int []array,int lo,int hi){
    //三数取中
    int mid=lo+(hi-lo)/2;
    if(array[mid]>array[hi]){
        swap(array[mid],array[hi]);
    }
    if(array[lo]>array[hi]){
        swap(array[lo],array[hi]);
    }
    if(array[mid]>array[lo]){
        swap(array[mid],array[lo]);
    }
    int key=array[lo];
    
    while(lo<hi){
        while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
            hi--;
        }
        array[lo]=array[hi];
        while(array[lo]<=key&&hi>lo){//从前半部分向后扫描
            lo++;
        }
        array[hi]=array[lo];
    }
    array[hi]=key;
    return hi;
}

public static void swap(int a,int b){
    int temp=a;
    a=b;
    b=temp;
}

public static void sort(int[] array,int lo ,int hi){
    if(lo>=hi){
        return ;
    }
    int index=partition(array,lo,hi);
    sort(array,lo,index-1);
    sort(array,index+1,hi);
}

分析：
1、快速排序的时间复杂度为O(NlogN).
2、快速排序在序列中元素很少时，效率将比较低，因此一般在序列中元素很少时使用插入排序，这样可以提高整体效率。

归并排序

把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。

原理：
归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表。即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

每个递归过程涉及三个步骤:
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.

示例如下图：

代码实现：

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
public static int[] sort(int[] a,int low,int high){
    int mid = (low+high)/2;
    if(low<high){
        sort(a,low,mid);
        sort(a,mid+1,high);
        //左右归并
        merge(a,low,mid,high);
    }
    return a;
}
 
public static void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high-low+1];
    int i= low;
    int j = mid+1;
    int k=0;
    // 把较小的数先移到新数组中
    while(i<=mid && j<=high){
        if(a[i]<a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    // 把左边剩余的数移入数组 
    while(i<=mid){
        temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while(j<=high){
        temp[k++] = a[j++];
    }
    // 把新数组中的数覆盖nums数组
    for(int x=0;x<temp.length;x++){
        a[x+low] = temp[x];
    }
}

分析：
（1）稳定性：归并排序是一种稳定的排序。
（2）存储结构要求：可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度：对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)。
（4）空间复杂度：需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
注意：若用单链表做存储结构，很容易给出就地的归并排序

希尔排序

希尔排序(Shell Sort)是插入排序的一种，是针对直接插入排序算法的改进，是将整个无序列分割成若干小的子序列分别进行插入排序，希尔排序并不稳定。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

原理：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

Shell排序的执行时间依赖于增量序，好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void shellSort(int[] a){
    double gap = a.length;//增量长度
    int dk,sentinel,k;
    while(true){
        gap = (int)Math.ceil(gap/2);//逐渐减小增量长度
        dk = (int)gap;//确定增量长度 
        for(int i=0;i<dk;i++){
            //用增量将序列分割，分别进行直接插入排序。随着增量变小为1，最后整体进行直接插入排序
            for(int j=i+dk;j<a.length;j = j+dk){
                k = j-dk;
                sentinel = a[j];
                while(k>=0 && sentinel<a[k]){
                    a[k+dk] = a[k];
                    k = k-dk;
                }
                a[k+dk] = sentinel;
            }
        }
        //当dk为1的时候，整体进行直接插入排序  
        if(dk==1){
            break;
        }
    }
}

分析：
1、希尔排序的关键并不是随便分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式移动，使得排序的效率提高。
2、需要注意的是，增量序列的最后一个增量值必须等于1才行。
3、由于记录是跳跃式的移动，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
4、希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。
5、希尔排序最好时间复杂度和平均时间复杂度都是O(nlogn)，最坏时间复杂度为O(n2)。

堆排序

对简单选择排序的优化。堆排序是一种树形选择排序方法，它的特点是：在排序的过程中，将array[0，…，n-1]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（最小）的元素。

堆的定义：
n个关键字序列array[0，…，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)时
① array[i] <= array[2i + 1] 且 array[i] <= array[2i + 2]； 称为小根堆；
② array[i] >= array[2i + 1] 且 array[i] >= array[2i + 2]； 称为大根堆；

步骤如下：
1、将序列构建成大顶堆。
2、将根节点与最后一个节点交换，然后断开最后一个节点。
3、重复第一、二步，直到所有节点断开。

代码实现：

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 static void adjustHeap(int[] a, int i, int len) {
    int temp, j;
    temp = a[i];
    for (j = 2 * i; j < len; j *= 2) {// 沿关键字较大的孩子结点向下筛选
        if (j < len && a[j] < a[j + 1])
            ++j; // j为关键字中较大记录的下标
        if (temp >= a[j])
            break;
        a[i] = a[j];
        i = j;
    }
    a[i] = temp;
}

public static void heapSort(int[] a) {
    int i;
    for (i = a.length / 2 - 1; i >= 0; i--) {// 构建一个大顶堆
        adjustHeap(a, i, a.length - 1);
    }
    for (i = a.length - 1; i >= 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        adjustHeap(a, 0, i - 1);// 将a中前i-1个记录重新调整为大顶堆
    }
}

分析：
1、空间复杂度:o(1)；
2、时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);
3、稳定性：不稳定

计数排序

原理:
对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。
所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。

示例如下：
需要三个数组:
待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1
输出数组 int[] res = new int[arr.length];
1.求出待排序数组的最大值max=6， 最小值min=1
2.实例化辅助计数数组help， help用来记录每个元素之前出现的元素个数， 此时help = [1,0,2,1,1,1]
3.计算 arr 每个数字应该在排序后数组中应该处于的位置，此时 help = [1,1,4,5,6,7];
4.根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6]

代码实现：

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
public static int[] countSort(int[] arr){
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
   
  //找出数组中的最大最小值
  for(int i = 0; i < arr.length; i++){
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
   
  int[] help = new int[max - min + 1];
   
  //找出每个数字出现的次数
  for(int i = 0; i < arr.length; i++){
    int mapPos = arr[i] - min;
    help[mapPos]++;
  }
   
  //计算每个数字应该在排序后数组中应该处于的位置
  for(int i = 1; i < help.length; i++){
    help[i] = help[i-1] + help[i];
  }
   
  //根据help数组进行排序
  int res[] = new int[arr.length];
  for(int i = 0; i < arr.length; i++){
    int post = --help[arr[i] - min];
    res[post] = arr[i];
  }
   
  return res;
}

分析：
1、计数排序是一种拿空间换时间的排序算法，它仅适用于数据比较集中的情况。比如 [0~100]，[10000~19999] 这样的数据。
2、只能是整形数组。
3、数组元素必须都大于0。

桶排序

原理：
把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并 。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

步骤如下：
1.找出待排序数组中的最大值max、最小值min
2.我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
5.遍历桶数组，把排序好的元素放进输出数组

代码实现：

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
public static void bucketSort(int[] arr){
	int max = Integer.MIN_VALUE;
	int min = Integer.MAX_VALUE;
	for(int i = 0; i < arr.length; i++){
		max = Math.max(max, arr[i]);
		min = Math.min(min, arr[i]);
	}
	
	//桶数
	int bucketNum = (max - min) / arr.length + 1;
	ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
	for(int i = 0; i < bucketNum; i++){
		bucketArr.add(new ArrayList<Integer>());
	}
	
	//将每个元素放入桶
	for(int i = 0; i < arr.length; i++){
		int num = (arr[i] - min) / (arr.length);
		bucketArr.get(num).add(arr[i]);
	}
	
	//对每个桶进行排序
	for(int i = 0; i < bucketArr.size(); i++){
		Collections.sort(bucketArr.get(i));// 对每个桶进行排序，这里使用了Collections.sort
	}

    //将桶中元素全部取出来并放入 arr 中输出
	int index = 0;
	for (ArrayList<Integer> bucket : bucketArr) {
	    for (Float data : bucket) {
	        arr[index++] = data;
	    }
	}

}

分析：
1、桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
2、但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
3、桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序

基数排序（Radix Sort）分为两种：第一种是LSD ，从最低位开始排序， 第二种是 MSD 从最高位开始排。这里介绍第一种LSD排序算法。
首先，我们先了解什么是基数。基数是根据具体的排序情况而定的，比如我们常见的基数是十进制-10，还有二进制-2。

原理：
基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。通过对每一个位上的值相排序，就可以完成对整个数组的排序。

步骤如下：
1、遍历所有数组元素，找出元素最大的位值
2、从低位到高位把数组元素上的位值存入链表中
3、遍历所有链表，将链表里面的值重新赋值给数组，再清空链表。

示例如下：
例如：对数组int[ ] data = {421, 240, 35, 532, 305, 430, 124}；
1、进行排序，首先我们要做的是对个位上的数值进行排序。
第一遍排序的结果为：　　240 430 421 532 124 35 305
2、再进行十位上的数值排序：
第二遍排序的结果为：　　305 421 124 430 532 35 240
3、再进行百位上的数值排序：
第三遍排序的结果为：　　35 124 240 305 421 430 532
最后我们的到的排序结果就是： 35 124 240 305 421 430 532

代码实现：

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
//实现基数排序
public void radixSort(int[] data) {
    int maxBin = maxBin(data);
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    for(int i  = 0; i < 10; i ++) {
        list.add(new ArrayList<Integer>());
    }
    for(int i = 0, factor = 1; i < maxBin; factor *= 10, i ++) {
        for(int j = 0; j < data.length; j ++) {
            list.get((data[j]/factor)%10).add(data[j]);
        }
        for(int j = 0, k = 0; j < list.size(); j ++) {
            while(!list.get(j).isEmpty()) {
                data[k] = list.get(j).get(0);
                list.get(j).remove(0);
                k ++;
            }
        }
    }
}

//计算数组里元素的最大位数
public int maxBin(int[] data) {
    int maxLen = 0;
    for(int i = 0; i < data.length; i ++) {
        int size = Integer.toString(data[i]).length();
        maxLen =  size > maxLen ? size : maxLen;
    }
    return maxLen;
}

算法分析：
1、基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。
2、基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

总结

参考资料

十大经典排序算法（动图演示）
Java 排序算法分析与实现
快速排序
Java实现归并排序
Java实现希尔排序
计数排序和桶排序（Java实现）
数据结构Java版之基数排序（四）

发表于 | 分类于

原型模式属于对象的创建模式：通过给出一个原型对象来指明所有创建的对象的类型，然后用复制这个原型对象的办法创建出更多同类型的对象。

应用场景

1、对象之间相同或相似，即只是个别的几个属性不同的时候。
2、对象的创建过程比较麻烦，但复制比较简单的时候。

原型模式的结构

原型模式要求对象实现一个可以“克隆”自身的接口，这样就可以通过复制一个实例对象本身来创建一个新的实例。这样一来，通过原型实例创建新的对象，就不再需要关心这个实例本身的类型，只要实现了克隆自身的方法，就可以通过这个方法来获取新的对象，而无须再去通过new来创建。

这种形式涉及到三个角色：
（1）客户(Client)角色：客户类提出创建对象的请求。
（2）抽象原型(Prototype)角色：这是一个抽象角色，通常由一个Java接口或Java抽象类实现。此角色给出所有的具体原型类所需的接口。
（3）具体原型（Concrete Prototype）角色：被复制的对象。此角色需要实现抽象的原型角色所要求的接口。

浅克隆与深克隆

浅克隆只是复制了基础属性，列如八大基本类型，然而引用类型实际上没有复制，只是将对应的引用给复制了。

简单的说：如果一个对象中只有基本类型属性，那深克隆和浅克隆效果都是一样的，基本类型数据不管是用深克隆还是浅克隆都会被克隆出一份，但如果对象中包含引用对象属性，那浅克隆其实这是拷贝了一份引用，而深克隆确实把整个引用对象都拷贝了一份。

原型模式的优点

（1）根据客户端要求实现动态创建对象，客户端不需要知道对象的创建细节，便于代码的维护和扩展。

（2）使用原型模式创建对象比直接new一个对象在性能上要好的多，因为Object类的clone方法是一个本地方法，它直接操作内存中的二进制流，特别是复制大对象时，性能的差别非常明显。所以在需要重复地创建相似对象时可以考虑使用原型模式。比如需要在一个循环体内创建对象，假如对象创建过程比较复杂或者循环次数很多的话，使用原型模式不但可以简化创建过程，而且可以使系统的整体性能提高很多。

（3）原型模式类似于工厂模式，但它没有了工厂模式中的抽象工厂和具体工厂的实现，代码结构更清晰和简单。

（4）可用于保护性拷贝，避免原始的对象被外部修改。

原型模式的注意事项

（1）使用原型模式复制对象不会调用类的构造方法。因为对象的复制是通过调用Object类的clone方法来完成的，它直接在内存中复制数据，因此不 会调用到类的构造方法。不但构造方法中的代码不会执行，甚至连访问权限都对原型模式无效。还记得单例模式吗？单例模式中，只要将构造方法的访问权限设置为 private型，就可以实现单例。但是clone方法直接无视构造方法的权限，所以，单例模式与原型模式是冲突的。

（2）在使用时要注意深拷贝与浅拷贝的问题。clone方法只会拷贝对象中的基本的数据类型，对于数组、容器对象、引用对象等都不会拷贝，这就是浅拷贝。如果要实现深拷贝，必须将原型模式中的数组、容器对象、引用对象等另行拷贝。

代码实现

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
//具体原型类
class Realizetype implements Cloneable
{
    Realizetype()
    {
        System.out.println("具体原型创建成功！");
    }
    public Object clone() throws CloneNotSupportedException
    {
        System.out.println("具体原型复制成功！");
        return (Realizetype)super.clone();
    }
}
//原型模式的测试类
public class PrototypeTest
{
    public static void main(String[] args)throws CloneNotSupportedException
    {
        Realizetype obj1=new Realizetype();
        Realizetype obj2=(Realizetype)obj1.clone();
        System.out.println("obj1==obj2?"+(obj1==obj2));
    }
}

程序的运行结果如下：
具体原型创建成功！
具体原型复制成功！
obj1==obj2?false

发表于 | 分类于

建造者模式的定义是：将一个复杂对象的构造与它的表示分离，使同样的构建过程可以创建不同的表示。它是将一个复杂的对象分解为多个简单的对象，然后一步一步构建而成。它将变与不变相分离，即产品的组成部分是不变的，但每一部分是可以灵活选择的。

主要优点如下：
1、各个具体的建造者相互独立，有利于系统的扩展。
2、客户端不必知道产品内部组成的细节，便于控制细节风险。

其缺点如下：
1、产品的组成部分必须相同，这限制了其使用范围。
2、如果产品的内部变化复杂，该模式会增加很多的建造者类。

建造者（Builder）模式和工厂模式的关注点不同：建造者模式注重零部件的组装过程，而工厂方法模式更注重零部件的创建过程，但两者可以结合使用。

应用场景

1、创建的对象较复杂，由多个部件构成，各部件面临着复杂的变化，但构件间的建造顺序是稳定的。
2、创建复杂对象的算法独立于该对象的组成部分以及它们的装配方式，即产品的构建过程和最终的表示是独立的。

结构与实现

建造者（Builder）模式的主要角色如下：
1、产品角色（Product）：它是包含多个组成部件的复杂对象，由具体建造者来创建其各个零部件。
2、抽象建造者（Builder）：它是一个包含创建产品各个子部件的抽象方法的接口，通常还包含一个返回复杂产品的方法 getResult()。
3、具体建造者(Concrete Builder）：实现 Builder 接口，完成复杂产品的各个部件的具体创建方法。
4、指挥者（Director）：它调用建造者对象中的部件构造与装配方法完成复杂对象的创建，在指挥者中不涉及具体产品的信息。

代码实现

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Product
{
    private String partA;
    private String partB;
    private String partC;
    public void setPartA(String partA)
    {
        this.partA=partA;
    }
    public void setPartB(String partB)
    {
        this.partB=partB;
    }
    public void setPartC(String partC)
    {
        this.partC=partC;
    }
    public void show()
    {
        //显示产品的特性
    }
}

abstract class Builder
{
    //创建产品对象
    protected Product product=new Product();
    public abstract void buildPartA();
    public abstract void buildPartB();
    public abstract void buildPartC();
    //返回产品对象
    public Product getResult()
    {
        return product;
    }
}

public class ConcreteBuilder extends Builder
{
    public void buildPartA()
    {
        product.setPartA("建造 PartA");
    }
    public void buildPartB()
    {
        product.setPartA("建造 PartB");
    }
    public void buildPartC()
    {
        product.setPartA("建造 PartC");
    }
}

class Director
{
    private Builder builder;
    public Director(Builder builder)
    {
        this.builder=builder;
    }
    //产品构建与组装方法
    public Product construct()
    {
        builder.buildPartA();
        builder.buildPartB();
        builder.buildPartC();
        return builder.getResult();
    }
}

public class Client
{
    public static void main(String[] args)
    {
        Builder builder=new ConcreteBuilder();
        Director director=new Director(builder);
        Product product=director.construct();
        product.show();
    }
}

模式的扩展

建造者（Builder）模式在应用过程中可以根据需要改变，如果创建的产品种类只有一种，只需要一个具体建造者，这时可以省略掉抽象建造者，甚至可以省略掉指挥者角色。