[design pattern](1) Strategy

引言

最近，在学习设计模式相关的知识。本博客主要想讲一讲策略模式，这也是我学习的第一个模式。写下这篇博客，主要想记录下个人的一点理解，也是想通过写博客的方式来加深对与Strategy的一点理解。以下的内容如果有什么说的不对的地方，还请各位大神指正。

思考题

首先我们来思考下面的一个问题：

问题：写出冒泡排序和快速排序算法，并且根据传参不同，使用不同的排序算法排序。

首先，来看没有使用设计模式的代码是什么样子：

SortAlgorithm.java:

import java.util.Random;
import java.util.Arrays;

public class SortAlgorithm {
    private static int index = 10000;
    private static int randomMax = 50000;
    private static Integer[] oldOrder = new Integer[index];
    private static Random random = new Random();
    static {
        for(int i = 0; i < index; i++) {
            oldOrder[i] = random.nextInt(randomMax);
        }
    }
    
    //通过设置算法名称来决定用什么算法
    private String algorithmName;
    
    public static void main(String... args) {
        SortAlgorithm sortAlgorithm = new SortAlgorithm();
        Integer[] oldOrder1 = Arrays.copyOf(oldOrder, index);
        Integer[] oldOrder2 = Arrays.copyOf(oldOrder, index);
        
        sortAlgorithm.setAlgorithmName("bubble");
        //System.out.println(String.format("BubbleSort sort before order:%s", Arrays.asList(oldOrder1).toString()));
        long startTime = System.currentTimeMillis();
        Integer[] newOrder1 = sortAlgorithm.executeAlgorithm(oldOrder1);
        System.out.println(String.format("BubbleSort take time:%s", System.currentTimeMillis() - startTime));
        //System.out.println(String.format("BubbleSort sort after order:%s", Arrays.asList(newOrder1).toString()));
        
        sortAlgorithm.setAlgorithmName("quick");
        //System.out.println(String.format("QuickSort sort before order:%s", Arrays.asList(oldOrder2).toString()));
        startTime = System.currentTimeMillis();
        Integer[] newOrder2 = sortAlgorithm.executeAlgorithm(oldOrder2);
        System.out.println(String.format("QuickSort take time:%s", System.currentTimeMillis() - startTime));
        //System.out.println(String.format("QuickSort sort after order:%s", Arrays.asList(newOrder2).toString()));
    }
    
    public Integer[] executeAlgorithm(Integer[] oldOrder) {
        if("bubble".equals(algorithmName)){
            return sortBubble(oldOrder);
        }else if("quick".equals(algorithmName)) {
            return sortQuick(oldOrder);
        }
        return null;
    }
    
    public void setAlgorithmName(String algorithmName) {
        this.algorithmName = algorithmName;
    }
    
    private Integer[] sortBubble(Integer[] oldOrder) {
        for(int i = 1; i < oldOrder.length; i++) {
            for(int j = 0; j < oldOrder.length - i; j++) {
                if(oldOrder[j] > oldOrder[j + 1]) {
                    Integer temp = oldOrder[j];
                    oldOrder[j] = oldOrder[j + 1];
                    oldOrder[j + 1] = temp;
                }
            }
        }
        return oldOrder;
    }
    
    private Integer[] sortQuick(Integer[] oldOrder) {
        partSort(oldOrder, 0, oldOrder.length - 1);
        return oldOrder;
    }
    
    private void partSort(Integer[] oldOrder, int start, int end) {
        if(start < end) {
            int middle = swaps(oldOrder, start, end);
            partSort(oldOrder, start, middle);
            partSort(oldOrder, middle + 1, end);
        }
    }
    
    private int swaps(Integer[] oldOrder, int start, int end) {
        Integer temp = oldOrder[start];
        for(;start < end;) {
            for(;start < end && temp <= oldOrder[end]; end--);
            if(start < end) {
                oldOrder[start] = oldOrder[end];
                start++;
            }
            for(;start < end && temp > oldOrder[start]; start++);
            if(start < end) {
                oldOrder[end] = oldOrder[start];
                end--;
            }
        }
        oldOrder[start] = temp;
        return start;
    }
}

print:

BubbleSort take time:717
QuickSort take time:14

上面是我的实现，所有的代码都集中在SortAlgorithm一个class里面。那么试想一下这时候如果我们想再增加一个选择排序，那么我们需要修改SortAlgorithm类，这样我们就违背了开闭原则。因此我们要想办法把修改变为增加。那么怎么样才能将修改变为增加呢？通过使用 strategy 可以做到。

介绍strategy

定义：定义一系列的算法，将每一个算法封装起来，并且让这些封装的算法之间可以相互替换。该模式可以使算法独立于使用它们的客户而变化。
类图：

通过上面的类图我们可以总结出一下几点：

具体算法类 ConcreteStrategyA 和 ConcreteStrategyA 都继承了 Strategy 接口，并且都实现了 algorithm 方法。通过实现接口我们可以很好的实践开闭原则，我们也可以很好的实现扩展
类 Client 中有一个 Strategy 变量，通过设置这个变量我们可以很容易的转换我们的算法

实现步骤：

首先定义一个接口
让所有的算法都实现这个接口
让客户端持有这个接口

重构思考题

那么通过对Strategy的学习，我们来重构下我们上面的问题：

首先，我们定义一个接口：

Sort.java:

public interface Sort {
    Integer[] sort(Integer[] oldOrder);
}

然后，我们定义一系列的算法实现上面定义的接口：

BubbleSort.java:

public class BubbleSort implements Sort {
    @Override
    public Integer[] sort(Integer[] oldOrder) {
        for(int i = 1; i < oldOrder.length; i++) {
            for(int j = 0; j < oldOrder.length - i; j++) {
                if(oldOrder[j] > oldOrder[j + 1]) {
                    Integer temp = oldOrder[j];
                    oldOrder[j] = oldOrder[j + 1];
                    oldOrder[j + 1] = temp;
                }
            }
        }
        return oldOrder;
    }
}

QuickSort.java:

public class QuickSort implements Sort {
    @Override
    public Integer[] sort(Integer[] oldOrder) {
        partSort(oldOrder, 0, oldOrder.length - 1);
        return oldOrder;
    }
    
    private void partSort(Integer[] oldOrder, int start, int end) {
        if(start < end) {
            int middle = swaps(oldOrder, start, end);
            partSort(oldOrder, start, middle);
            partSort(oldOrder, middle + 1, end);
        }
    }
    
    private int swaps(Integer[] oldOrder, int start, int end) {
        Integer temp = oldOrder[start];
        for(;start < end;) {
            for(;start < end && temp <= oldOrder[end]; end--);
            if(start < end) {
                oldOrder[start] = oldOrder[end];
                start++;
            }
            for(;start < end && temp > oldOrder[start]; start++);
            if(start < end) {
                oldOrder[end] = oldOrder[start];
                end--;
            }
        }
        oldOrder[start] = temp;
        return start;
    }
}

最后，我们实现一个算法调用类：

SortAlgorithm.java:

public class SortAlgorithm {
    private Sort sort;
    
    public void setSort(Sort sort) {
        this.sort = sort;
    }
    
    public Integer[] executeAlgorithm(Integer[] oldOrder) {
        return sort.sort(oldOrder);
    }
}

测试用例：

Client.java:

import java.util.Random;
import java.util.Arrays;

public class Client {
    private static int index = 10;
    private static int randomMax = 100;
    private static Integer[] oldOrder = new Integer[index];
    private static Random random = new Random();
    static {
        for(int i = 0; i < index; i++) {
            oldOrder[i] = random.nextInt(randomMax);
        }
    }
    
    public static void main(String... args) {
        SortAlgorithm sortAlgorithm = new SortAlgorithm();
        Integer[] oldOrder1 = Arrays.copyOf(oldOrder, index);
        Integer[] oldOrder2 = Arrays.copyOf(oldOrder, index);
        
        sortAlgorithm.setSort(new BubbleSort());
        System.out.println(String.format("BubbleSort sort before order:%s", Arrays.asList(oldOrder1).toString()));
        long startTime = System.currentTimeMillis();
        Integer[] newOrder1 = sortAlgorithm.executeAlgorithm(oldOrder1);
        System.out.println(String.format("BubbleSort take time:%s", System.currentTimeMillis() - startTime));
        System.out.println(String.format("BubbleSort sort after order:%s", Arrays.asList(newOrder1).toString()));
        
        sortAlgorithm.setSort(new QuickSort());
        System.out.println(String.format("QuickSort sort before order:%s", Arrays.asList(oldOrder2).toString()));
        startTime = System.currentTimeMillis();
        Integer[] newOrder2 = sortAlgorithm.executeAlgorithm(oldOrder2);
        System.out.println(String.format("QuickSort take time:%s", System.currentTimeMillis() - startTime));
        System.out.println(String.format("QuickSort sort after order:%s", Arrays.asList(newOrder2).toString()));
    }
    
    private static int[] copyOldOrder(int[] oldOrder) {
        int[] result = new int[index];
        for(int i = 0; i < index; i++) {
            result[i] = oldOrder[i];
        }
        return result;
    }
}

上面的代码使用了策略模式，通过使用这个模式我们可以很容易的扩展，现在只要我们实现 Sort 接口就可以扩展我们的排序算法。