设计模式系列篇(十四)——策略模式
2020-08-31 本文已影响0人
复旦猿
What
策略模式（Strategy Pattern）是一种行为设计模型。该模式定义一族算法类，将每个算法分别封装起来，让它们可以互相替换。策略模式可以使算法的变化独立于使用它们的客户端（这里的客户端代指使用算法的代码）。
Why
策略模式可以起到解耦的作用，其解耦的是策略的定义、创建、使用这三部分，可以避免复杂的分支判断。具体优点如下：
- 策略模式提供了对“开闭原则”的完美支持，用户可以在不修改原有系统的基础上选择算法或行为，也可以灵活地增加新的算法或行为。
- 策略模式提供了管理相关的算法族的办法。
- 策略模式提供了可以替换继承关系的办法。
- 使用策略模式可以避免使用多重条件转移语句。
When
在以下情况下可以使用策略模式：
- 如果在一个系统里面有许多类，它们之间的区别仅在于它们的行为，那么使用策略模式可以动态地让一个对象在许多行为中选择一种行为。
- 一个系统需要动态地在几种算法中选择一种。
- 如果一个对象有很多的行为，如果不用恰当的模式，这些行为就只好使用多重的条件选择语句来实现。
- 不希望客户端知道复杂的、与算法相关的数据结构，在具体策略类中封装算法和相关的数据结构，提高算法的保密性与安全性。
How
一个完整的策略模式就是由策略的定义、创建和使用三个部分组成的。策略类的定义比较简单，包含一个策略接口和一组实现这个接口的策略类。策略的创建由工厂类来完成，封装策略创建的细节。策略模式包含一组策略可选，客户端代码如何选择使用哪个策略，有两种确定方法：编译时静态确定和运行时动态确定。其中，“运行时动态确定”才是策略模式最典型的应用场景。
今天，我们就以根据数据量自动选择排序算法的实例来为大家介绍策略模式的实现方法。我们大家应该都很熟悉排序算法有很多，冒泡、插入、选择、希尔、归并、快速排序等等等，我们现在的需求是对于输入数据的数据量来动态选择排序算法，规则如下：
- 当输入数据长度小于10时，选择插入排序；
- 当输入数据长度大于等于10并且小于20时，选择归并排序；
- 当输入数据长度大于等于20时，选择快速排序。
接下来，我们就以策略的定义、创建和使用来分别介绍策略模式的实现方法。
首先是策略的定义，代码如下：
// 排序算法接口
public interface SortAlgorithm {
int[] sort(int[] list);
}
// 插入排序算法
public class InsertSortAlgo implements SortAlgorithm {
@Override
public int[] sort(int[] list) {
if (list == null || list.length < 2) {
return list;
}
for (int i = 0; i < list.length; i++) {
int value = list[i];
int j = i;
for (; j > 0; j--) {
// 移动数据
if (value < list[j - 1]) {
list[j] = list[j - 1];
} else {
break;
}
}
// 插入数据
list[j] = value;
}
return list;
}
}
// 归并排序算法
public class MergeSortAlgo implements SortAlgorithm {
@Override
public int[] sort(int[] list) {
if (list == null || list.length < 2) {
return list;
}
if (list.length == 2) {
if (list[0] > list[1]) {
int tmp = list[0];
list[0] = list[1];
list[1] = tmp;
}
return list;
}
int left = 0;
int right = list.length;
int mid = (left + right) / 2;
int[] leftA = new int[mid];
int[] rightA = new int[right - mid];
int i = 0;
int j = mid;
while (i < mid) {
leftA[i] = list[i++];
}
while (j < right) {
rightA[j - mid] = list[j++];
}
leftA = sort(leftA);
rightA = sort(rightA);
return merge(leftA, rightA);
}
private static int[] merge(int[] list, int[] B) {
int lenA = list.length;
int lenB = B.length;
int[] C = new int[lenA + lenB];
int i = 0;
int j = 0;
int m = 0;
while (i < lenA && j < lenB) {
if (list[i] <= B[j]) {
C[m++] = list[i++];
} else {
C[m++] = B[j++];
}
}
while (i < lenA) {
C[m++] = list[i++];
}
while (j < lenB) {
C[m++] = B[j++];
}
return C;
}
}
// 快速排序算法
public class QuickSortAlgo implements SortAlgorithm {
@Override
public int[] sort(int[] list) {
if (list == null || list.length < 2) {
return list;
}
partition(list, 0, list.length - 1);
return list;
}
private void partition(int[] list, int left, int right) {
if (left > right) {
return;
}
int i = left;
int j = right;
int base = list[left];
while (i < j) {
while (list[j] >= base && i < j) {
j--;
}
if (i < j) {
list[i] = list[j];
}
while (list[i] <= base && i < j) {
i++;
}
if (i < j) {
list[j] = list[i];
}
}
list[i] = base;
partition(list, left, i - 1);
partition(list, i + 1, right);
}
}
接下来，是策略的创建。一般采用工厂模式进行生成。
public class SortAlgoFactory {
private static List<RangeAlgo> algorithms = new ArrayList<>();
static {
algorithms.add(new RangeAlgo(0, 10, new InsertSortAlgo()));
algorithms.add(new RangeAlgo(10, 20, new MergeSortAlgo()));
algorithms.add(new RangeAlgo(20, Integer.MAX_VALUE, new QuickSortAlgo()));
}
public void addAlgorithms(RangeAlgo rangeAlgo) {
algorithms.add(rangeAlgo);
}
public static SortAlgorithm newSortAlgorithm(Integer num) {
for (RangeAlgo algo : algorithms) {
if (algo.inRange(num)) {
System.out.println(String.format("use sort algorithm %s", algo.getAlgorithm().getClass()));
return algo.getAlgorithm();
}
}
throw new IllegalStateException("invalid num");
}
private static class RangeAlgo {
private Integer min;
private Integer max;
private SortAlgorithm algorithm;
public SortAlgorithm getAlgorithm() {
return algorithm;
}
public RangeAlgo(Integer min, Integer max, SortAlgorithm algorithm) {
this.min = min;
this.max = max;
this.algorithm = algorithm;
}
public boolean inRange(Integer num) {
return num >= this.min && num < this.max;
}
}
}
如果你想增加更多的排序算法，只需要实现新的排序策略算法，然后调用addAlgorithms方法更新algorithms列表就可以了，所以这很符合开闭原则。
最后，是策略的使用。测试代码如下：
public class TestMain {
public static void main(String[] args) {
int[] A = new int[]{3, 1, 2, 4, 6};
SortAlgorithm sortAlgorithm1 = SortAlgoFactory.newSortAlgorithm(A.length);
A = sortAlgorithm1.sort(A);
System.out.println(Arrays.toString(A));
int[] B = new int[]{3, 1, 2, 4, 6, 2, 4, 10, 9, 20, 39};
SortAlgorithm sortAlgorithm2 = SortAlgoFactory.newSortAlgorithm(B.length);
B = sortAlgorithm2.sort(B);
System.out.println(Arrays.toString(B));
int[] C = new int[]{3, 1, 2, 4, 6, 2, 4, 10, 9, 20, 39, 3, 1, 2, 4, 6, 2, 4, 10,
9, 20, 39, 3, 1, 2, 4, 6, 2, 4, 10, 9, 20, 39};
SortAlgorithm sortAlgorithm3 = SortAlgoFactory.newSortAlgorithm(C.length);
C = sortAlgorithm3.sort(C);
System.out.println(Arrays.toString(C));
}
}
输出如下：
use sort algorithm class strategy.InsertSortAlgo
[1, 2, 3, 4, 6]
use sort algorithm class strategy.MergeSortAlgo
[1, 2, 2, 3, 4, 4, 6, 9, 10, 20, 39]
use sort algorithm class strategy.QuickSortAlgo
[1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 6, 6, 6, 9, 9, 9, 10, 10, 10, 20, 20, 20, 39, 39, 39]
代码地址
写在最后
如果你觉得我写的文章帮到了你，欢迎点赞、评论、分享、赞赏哦，你们的鼓励是我不断创作的动力～
