图

在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

什么是图

• 阶（Order） - 图 G 中点集 V 的大小称作图 G 的阶。
• 子图（Sub-Graph） - 当图 G’=(V’,E’)其中 V‘包含于 V，E’包含于 E，则 G’称作图 G=(V,E)的子图。每个图都是本身的子图。
• 生成子图（Spanning Sub-Graph） - 指满足条件 V(G’) = V(G)的 G 的子图 G’。
• 导出子图（Induced Subgraph） - 以图 G 的顶点集 V 的非空子集V1 为顶点集，以两端点均在 V1 中的全体边为边集的 G 的子图，称为 V1 导出的导出子图；以图 G 的边集 E 的非空子集 E1 为边集，以 E1 中边关联的顶点的全体为顶点集的 G 的子图，称为 E1 导出的导出子图。
• 有向图 - 如果给图的每条边规定一个方向，那么得到的图称为有向图。
• 无向图 - 边没有方向的图称为无向图。
• 度（Degree） - 一个顶点的度是指与该顶点相关联的边的条数，顶点 v 的度记作 d(v)。
• 入度（In-degree）和出度（Out-degree） - 对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
• 自环（Loop） - 若一条边的两个顶点为同一顶点，则此边称作自环。
• 路径（Path） - 从 u 到 v 的一条路径是指一个序列 v0,e1,v1,e2,v2,…ek,vk，其中 ei 的顶点为 vi 及 vi - 1，k 称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。
• 行迹（Trace） - 如果路径 P(u,v)中的边各不相同，则该路径称为 u 到 v 的一条行迹。闭的行迹称作回路（Circuit）。
• 轨迹（Track） - 如果路径 P(u,v)中的顶点各不相同，则该路径称为 u 到 v 的一条轨迹。闭的轨迹称作圈（Cycle）。
• 桥（Bridge） - 若去掉一条边，便会使得整个图不连通，该边称为桥。

如果图的边没有方向性，则被成为无向图。

图的基本操作

• 创建一个图结构 - CreateGraph(G)
• 检索给定顶点 - LocateVex(G,elem)
• 获取图中某个顶点 - GetVex(G,v)
• 为图中顶点赋值 - PutVex(G,v,value)
• 返回第一个邻接点 - FirstAdjVex(G,v)
• 返回下一个邻接点 - NextAdjVex(G,v,w)
• 插入一个顶点 - InsertVex(G,v)
• 删除一个顶点 - DeleteVex(G,v)
• 插入一条边 - InsertEdge(G,v,w)
• 删除一条边 - DeleteEdge(G,v,w)
• 遍历图 - Traverse(G,v)

参考资料

• 数据结构与算法之美

哈希表

哈希表 是一种使用 哈希函数 组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合 和 哈希映射。

• 哈希集合 是集合数据结构的实现之一，用于存储非重复值。
• 哈希映射 是映射 数据结构的实现之一，用于存储(key, value)键值对。

什么是哈希表

哈希表的英文叫“Hash Table”，我们平时也叫它“散列表”或者“Hash 表”。

哈希表 是一种使用 哈希函数 组织数据，以支持快速插入和搜索的数据结构。

有两种不同类型的哈希表：哈希集合 和 哈希映射。

• 哈希集合 是集合数据结构的实现之一，用于存储非重复值。
• 哈希映射 是映射 数据结构的实现之一，用于存储(key, value)键值对。

哈希表用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有哈希表。

哈希表通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

有两种不同类型的哈希表：哈希集合和哈希映射。

• 哈希集合是集合数据结构的实现之一，用于存储非重复值。
• 哈希映射是映射 数据结构的实现之一，用于存储(key, value)键值对。

在标准模板库的帮助下，哈希表是易于使用的。大多数常见语言（如 Java，C ++ 和 Python）都支持哈希集合和哈希映射。

散列函数

散列函数，顾名思义，它是一个函数。我们可以把它定义成 **hash(key)**，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说，

1. 当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
2. 当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

散列函数将取决于 键值的范围 和 桶的数量 。

散列函数设计的基本要求：

1. 散列函数计算得到的散列值是一个非负整数；
2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

散列冲突

即便像业界著名的MD5、SHA、CRC等哈希算法，也无法完全避免这种散列冲突。

该如何解决散列冲突问题呢？我们常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

装载因子

当哈希表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证哈希表的操作效率，一般情况下，我们会尽可能保证哈希表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。

装载因子的计算公式是：

1

哈希表的装载因子 = 填入表中的元素个数 / 哈希表的长度

装载因子越大，说明空闲位置越少，冲突越多，哈希表的性能会下降。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

当装载因子过大时，就需要对哈希表扩容。新申请一个更大的哈希表，将数据搬移到这个新哈希表中。针对数组的扩容，数据搬移操作比较简单。但是，针对哈希表的扩容，数据搬移操作要复杂很多。因为哈希表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，哈希表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。

装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。

当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。

线性探测（Linear Probing）：当我们往哈希表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

对于使用线性探测法解决冲突的哈希表，删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。这是为什么呢？在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定哈希表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。本来存在的数据，会被认定为不存在。这个问题如何解决呢？

我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。

线性探测法其实存在很大问题。当哈希表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个哈希表，所以最坏情况下的时间复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张哈希表，才能找到要查找或者删除的数据。

链表法

在哈希表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的哈希表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)。当查找、删除一个元素时，我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢？

实际上，这两个操作的时间复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示哈希表中“槽”的个数。

开放寻址法 vs. 链表法

开放寻址法适用于数据量比较小、装载因子小的场景。

链表法适用于存储大对象、大数据量的哈希表。比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

哈希表的应用场景

哈希算法的应用非常非常多，最常见的七个，分别是：

• 安全加密：如：MD5、SHA
• 唯一标识：UUID
• 数据校验：数字签名
• 散列函数：
• 负载均衡：会话粘滞（session sticky）负载均衡算法。可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。
• 数据分片
• 分布式存储：一致性哈希算法、虚拟哈希槽

典型应用场景

Java 的 HashMap 工具类，其

• HashMap 默认的初始大小是 16
• 最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示哈希表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。
• HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现链表过长的情况，一旦出现链表过长，则会严重影响 HashMap 的性能。在 JDK1.8 版本中，对 HashMap 做了进一步优化：引入了红黑树。当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

练习

Leetcode 练习题：

• 705. 设计哈希集合
• 706. 设计哈希映射

思考

1. 假设我们有 10 万条 URL 访问日志，如何按照访问次数给 URL 排序？
2. 有两个字符串数组，每个数组大约有 10 万条字符串，如何快速找出两个数组中相同的字符串？

参考资料

• 数据结构与算法之美

数据结构和算法指南

1. 为什么学习数据结构和算法

• 为了找到一份好工作：大厂面试喜欢考算法
• 更深入了解流行技术的设计思想：数据结构和算法是计算机基础学科，很多框架、中间、底层系统设的设计，都借鉴了其思想。因此，掌握数据结构和算法，有利于更深入了解这些技术的设计思想。
• 提升个人的编程水平
• 不满足于做业务狗，拓展性能思考的视角

2. 如何学习数据结构和算法

数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。

先要学会复杂度分析，才能识别数据结构和算法的利弊。

• 循序渐进
• 边学边练，适度刷题
• 学习并思考：学而不思则罔，思而不学则殆
• 知识需要沉淀，不要想试图一下子掌握所有

线性表的查找

查找简介

什么是查找？

查找是根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。

查找算法的分类

若在查找的同时对表记录做修改操作（如插入和删除），则相应的表称之为动态查找表；

否则，称之为静态查找表。

此外，如果查找的全过程都在内存中进行，称之为内查找；

反之，如果查找过程中需要访问外存，称之为外查找。

查找算法性能比较的标准

——平均查找长度 ASL（Average Search Length）

由于查找算法的主要运算是关键字的比较过程，所以通常把查找过程中对关键字需要执行的平均比较长度（也称为平均比较次数）作为衡量一个查找算法效率优劣的比较标准。

选取查找算法的因素

(1) 使用什么数据存储结构（如线性表、树形表等）。

(2) 表中的次序，即对无序表还是有序表进行查找。

顺序查找

要点

它是一种最简单的查找算法，效率也很低下。

存储结构

没有存储结构要求，可以无序，也可以有序。

基本思想

从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功；

若扫描结束仍没有找到关键字等于 k 的结点，表示查找失败。

核心代码

1
2
3
4
5
6
7
8
9
10
11

public int orderSearch(int[] list, int length, int key) {
    // 从前往后扫描list数组，如果有元素的值与key相等，直接返回其位置
    for (int i = 0; i < length; i++) {
        if (key == list[i]) {
            return i;
        }
    }

    // 如果扫描完，说明没有元素的值匹配key，返回-1，表示查找失败
    return -1;
}

算法分析

顺序查找算法最好的情况是，第一个记录即匹配关键字，则需要比较 1 次；

最坏的情况是，最后一个记录匹配关键字，则需要比较 N 次。

所以，顺序查找算法的平均查找长度为

ASL = (N + N-1 + … + 2 + 1) / N = (N+1) / 2

顺序查找的平均时间复杂度为**O(N)**。

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

存储结构

使用二分查找需要两个前提：

(1) 必须是顺序存储结构。

(2) 必须是有序的表。

基本思想

首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；

否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

核心代码

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

public int binarySearch(int[] list, int length, int key) {
    int low = 0, mid = 0, high = length - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (list[mid] == key) {
            return mid; // 查找成功，直接返回位置
        } else if (list[mid] < key) {
            low = mid + 1; // 关键字大于中间位置的值，则在大值区间[mid+1, high]继续查找
        } else {
            high = mid - 1; // 关键字小于中间位置的值，则在小值区间[low, mid-1]继续查找
        }
    }
    return -1;
}

算法分析

二分查找的过程可看成一个二叉树。

把查找区间的中间位置视为树的根，左区间和右区间视为根的左子树和右子树。

由此得到的二叉树，称为二分查找的判定树或比较树。

由此可知，二分查找的平均查找长度实际上就是树的高度**O(log₂N)**。

二分查找的局限性

• 二分查找依赖的是顺序表结构，简单点说就是数组
• 二分查找针对的是有序数据
• 数据量太小不适合二分查找
• 数据量太大也不适合二分查找

分块查找

要点

分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。

分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

存储结构

分块查找表是由“分块有序”的线性表和索引表两部分构成的。

所谓“分块有序”的线性表，是指：

假设要排序的表为 R[0…N-1]，将表均匀分成 b 块，前 b-1 块中记录个数为 s=N/b，最后一块记录数小于等于 s；

每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字。

注：这是使用分块查找的前提条件。

如上将表均匀分成 b 块后，抽取各块中的最大关键字和起始位置构成一个索引表 IDX[0…b-1]。

由于表 R 是分块有序的，所以索引表是一个递增有序表。

下图就是一个分块查找表的存储结构示意图

基本思想

分块查找算法有两个处理步骤：

(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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

class BlockSearch {

    class IndexType {
        public int key; // 分块中的最大值
        public int link; // 分块的起始位置
    }

    // 建立索引方法，n 是线性表最大长度，gap是分块的最大长度
    public IndexType[] createIndex(int[] list, int n, int gap) {
        int i = 0, j = 0, max = 0;
        int num = n / gap;
        IndexType[] idxGroup = new IndexType[num]; // 根据步长数分配索引数组大小

        while (i < num) {
            j = 0;
            idxGroup[i] = new IndexType();
            idxGroup[i].link = gap * i; // 确定当前索引组的第一个元素位置
            max = list[gap * i]; // 每次假设当前组的第一个数为最大值
            // 遍历这个分块，找到最大值
            while (j < gap) {
                if (max < list[gap * i + j]) {
                    max = list[gap * i + j];
                }
                j++;
            }
            idxGroup[i].key = max;
            i++;
        }

        return idxGroup;
    }

    // 分块查找算法
    public int blockSearch(IndexType[] idxGroup, int m, int[] list, int n, int key) {
        int mid = 0;
        int low = 0;
        int high = m -1;
        int gap = n / m; // 分块大小等于线性表长度除以组数

        // 先在索引表中进行二分查找，找到的位置存放在 low 中
        while (low <= high) {
            mid = (low + high) / 2;
            if (idxGroup[mid].key >= key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 在索引表中查找成功后，再在线性表的指定块中进行顺序查找
        if (low < m) {
            for (int i = idxGroup[low].link; i < idxGroup[low].link + gap; i++) {
                if (list[i] == key)
                    return i;
            }
        }

        return -1;
    }

    // 打印完整序列
    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    // 打印索引表
    public void printIDX(IndexType[] list) {
        System.out.println("构造索引表如下：");
        for (IndexType elem : list) {
            System.out.format("key = %d, link = %d\n", elem.key, elem.link);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int key = 85;
        int array2[] = { 8, 14, 6, 9, 10, 22, 34, 18, 19, 31, 40, 38, 54, 66, 46, 71, 78, 68, 80, 85 };
        BlockSearch search = new BlockSearch();

        System.out.print("线性表: ");
        search.printAll(array2);

        IndexType[] idxGroup = search.createIndex(array2, array2.length, 5);
        search.printIDX(idxGroup);
        int pos = search.blockSearch(idxGroup, idxGroup.length, array2,
                array2.length, key);
        if (-1 == pos) {
            System.out.format("查找key = %d失败", key);
        } else {
            System.out.format("查找key = %d成功，位置为%d", key, pos);
        }
    }

}

运行结果

1
2
3
4
5
6
7
8

线性表: 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85
构造索引表如下：
key = 14, link = 0
key = 34, link = 5
key = 66, link = 10
key = 85, link = 15

查找key = 85成功，位置为19

算法分析

因为分块查找实际上是两次查找过程之和。若以二分查找来确定块，显然它的查找效率介于顺序查找和二分查找之间。

三种线性查找的 PK

(1) 以平均查找长度而言，二分查找 > 分块查找 > 顺序查找。

(2) 从适用性而言，顺序查找无限制条件，二分查找仅适用于有序表，分块查找要求“分块有序”。

(3) 从存储结构而言，顺序查找和分块查找既可用于顺序表也可用于链表；而二分查找只适用于顺序表。

(4) 分块查找综合了顺序查找和二分查找的优点，既可以较为快速，也能使用动态变化的要求。

参考资料

堆

什么是堆？

堆（Heap）是一个可以被看成近似完全二叉树的数组。

• 堆是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

堆可以分为大顶堆和小顶堆。

• 对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。

• 对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。

如何实现堆

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

堆常见的操作：

• HEAPIFY 建堆：把一个乱序的数组变成堆结构的数组，时间复杂度为 $$O(n)$$。
• HEAPPUSH：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 $$O(log N)$$
• HEAPPOP：从最大堆中取出最大值或从最小堆中取出最小值，并将剩余的数组保持堆结构，时间复杂度为 $$O(log N)$$。
• HEAPSORT：借由 HEAPFY 建堆和 HEAPPOP 堆数组进行排序，时间复杂度为$$ O(N log N)$$，空间复杂度为 $$O(1)$$。

堆的应用场景

求 TOP N

堆结构的一个常见应用是建立优先队列（Priority Queue）。

求 Top K 的问题抽象成两类。一类是针对静态数据集合；另一类是针对动态数据集合

优先级队列

在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。

堆和优先级队列非常相似：往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。

参考：Java 的 PriorityQueue 类

求中位数

线性表的排序

📦 本文已归档到：“blog”

🔁 本文中的示例代码已归档到：“algorithm-tutorial”

冒泡排序

要点

冒泡排序是一种交换排序。

什么是交换排序呢？

交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。

算法思想

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。

假设有一个大小为 N 的无序序列。冒泡排序就是要每趟排序过程中通过两两比较，找到第 i 个小（大）的元素，将其往上排。

以上图为例，演示一下冒泡排序的实际流程：

假设有一个无序序列 { 4. 3. 1. 2, 5 }

• 第一趟排序：通过两两比较，找到第一小的数值 1 ，将其放在序列的第一位。
• 第二趟排序：通过两两比较，找到第二小的数值 2 ，将其放在序列的第二位。
• 第三趟排序：通过两两比较，找到第三小的数值 3 ，将其放在序列的第三位。

至此，所有元素已经有序，排序结束。

要将以上流程转化为代码，我们需要像机器一样去思考，不然编译器可看不懂。

• 假设要对一个大小为 N 的无序序列进行升序排序（即从小到大）。
  • 每趟排序过程中需要通过比较找到第 i 个小的元素。
  • 所以，我们需要一个外部循环，从数组首端(下标 0) 开始，一直扫描到倒数第二个元素（即下标 N - 2) ，剩下最后一个元素，必然为最大。
• 假设是第 i 趟排序，可知，前 i-1 个元素已经有序。现在要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比较即可。
  • 所以，需要一个内部循环，从数组末端开始（下标 N - 1），扫描到 (下标 i + 1)。

核心代码

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

public void bubbleSort(int[] list) {
    int temp = 0; // 用来交换的临时数

    // 要遍历的次数
    for (int i = 0; i < list.length - 1; i++) {
        // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
        for (int j = list.length - 1; j > i; j--) {
            // 比较相邻的元素，如果前面的数大于后面的数，则交换
            if (list[j - 1] > list[j]) {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }

        System.out.format("第 %d 趟：\t", i);
        printAll(list);
    }
}

算法分析

冒泡排序算法的性能

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 C 和记录移动次数 M 均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为 O(N)。

若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax = N(N-1)/2 = O(N2)

Mmax = 3N(N-1)/2 = O(N2)

冒泡排序的最坏时间复杂度为 O(N2)。

因此，冒泡排序的平均时间复杂度为 O(N2)。

总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。

所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

优化

对冒泡排序常见的改进方法是加入标志性变量 exchange，用于标志某一趟排序过程中是否有数据交换。

如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。

核心代码

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

// 对 bubbleSort 的优化算法
public void bubbleSort_2(int[] list) {
    int temp = 0; // 用来交换的临时数
    boolean bChange = false; // 交换标志

    // 要遍历的次数
    for (int i = 0; i < list.length - 1; i++) {
        bChange = false;
        // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
        for (int j = list.length - 1; j > i; j--) {
            // 比较相邻的元素，如果前面的数大于后面的数，则交换
            if (list[j - 1] > list[j]) {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
                bChange = true;
            }
        }

        // 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
        if (false == bChange)
            break;

        System.out.format("第 %d 趟：\t", i);
        printAll(list);
    }
}

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

快速排序

要点

快速排序是一种交换排序。

快速排序由 C. A. R. Hoare 在 1962 年提出。

算法思想

它的基本思想是：

通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

详细的图解往往比大堆的文字更有说明力，所以直接上图：

上图中，演示了快速排序的处理过程：

1. 初始状态为一组无序的数组：2、4、5、1、3。
2. 经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。
3. 新的数组中，以 2 为分割点，左边都是比 2 小的数，右边都是比 2 大的数。
4. 因为 2 已经在数组中找到了合适的位置，所以不用再动。
5. 2 左边的数组只有一个元素 1，所以显然不用再排序，位置也被确定。（注：这种情况时，left 指针和 right 指针显然是重合的。因此在代码中，我们可以通过设置判定条件 left 必须小于 right，如果不满足，则不用排序了）。
6. 而对于 2 右边的数组 5、4、3，设置 left 指向 5，right 指向 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

public int division(int[] list, int left, int right) {
    // 以最左边的数(left)为基准
    int base = list[left];
    while (left < right) {
        // 从序列右端开始，向左遍历，直到找到小于base的数
        while (left < right && list[right] >= base)
            right--;
        // 找到了比base小的元素，将这个元素放到最左边的位置
        list[left] = list[right];

        // 从序列左端开始，向右遍历，直到找到大于base的数
        while (left < right && list[left] <= base)
            left++;
        // 找到了比base大的元素，将这个元素放到最右边的位置
        list[right] = list[left];
    }

    // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
    // 而left位置的右侧数值应该都比left大。
    list[left] = base;
    return left;
}

private void quickSort(int[] list, int left, int right) {

    // 左下标一定小于右下标，否则就越界了
    if (left < right) {
        // 对数组进行分割，取出下次分割的基准标号
        int base = division(list, left, right);

        System.out.format("base = %d:\t", list[base]);
        printPart(list, left, right);

        // 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        quickSort(list, left, base - 1);

        // 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
        quickSort(list, base + 1, right);
    }
}

算法分析

快速排序算法的性能

时间复杂度

当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。

而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。

所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。

空间复杂度

快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N 次的分割处理，所以占用空间也是 Nlog2N 个。

算法稳定性

在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

插入排序

要点

直接插入排序是一种最简单的插入排序。

插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，知道全部插入完成。

算法思想

在讲解直接插入排序之前，先让我们脑补一下我们打牌的过程。

• 先拿一张 5 在手里，
• 再摸到一张 4，比 5 小，插到 5 前面，
• 摸到一张 6，嗯，比 5 大，插到 5 后面，
• 摸到一张 8，比 6 大，插到 6 后面，
• 。。。
• 最后一看，我靠，凑到的居然是同花顺，这下牛逼大了。

以上的过程，其实就是典型的直接插入排序，每次将一个新数据插入到有序队列中的合适位置里。

很简单吧，接下来，我们要将这个算法转化为编程语言。

假设有一组无序序列 R0, R1, … , RN-1。

• 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。
• 然后，我们要依次把 R1, R2, … , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。
• 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入 Ri 时，前 i-1 个数肯定已经是有序了。

所以我们需要将 Ri 和 R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。

核心代码

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

public void insertSort(int[] list) {
   // 打印第一个元素
   System.out.format("i = %d:\t", 0);
   printPart(list, 0, 0);

   // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
   for (int i = 1; i < list.length; i++) {
       int j = 0;
       int temp = list[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置

       // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
       for (j = i - 1; j >= 0 && temp < list[j]; j--) {
           list[j + 1] = list[j];
       }
       list[j + 1] = temp;

       System.out.format("i = %d:\t", i);
       printPart(list, 0, i);
   }
}

算法分析

直接插入排序的算法性能

时间复杂度

当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为 **O(N)**。

当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为 **O(N2)**。

所以，数据越接近正序，直接插入排序的算法性能越好。

空间复杂度

由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。

算法稳定性

直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

希尔排序

要点

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

该方法因 DL．Shell 于 1959 年提出而得名。

算法思想

希尔排序的基本思想是：

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。

我们来通过演示图，更深入的理解一下这个过程。

在上面这幅图中：

初始时，有一个大小为 10 的无序序列。

• 在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
  • 接下来，按照直接插入排序的方法对每个组进行排序。
• 在** 第二趟排序中**，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
  • 按照直接插入排序的方法对每个组进行排序。
• 在第三趟排序中，再次把 gap 缩小一半，即 gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
  • 按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。

所以，希尔排序是不稳定的算法。

核心代码

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

public void shellSort(int[] list) {
   int gap = list.length / 2;

   while (1 <= gap) {
       // 把距离为 gap 的元素编为一个组，扫描所有组
       for (int i = gap; i < list.length; i++) {
           int j = 0;
           int temp = list[i];

           // 对距离为 gap 的元素组进行排序
           for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
               list[j + gap] = list[j];
           }
           list[j + gap] = temp;
       }

       System.out.format("gap = %d:\t", gap);
       printAll(list);
       gap = gap / 2; // 减小增量
   }
}

算法分析

希尔排序的算法性能

时间复杂度

步长的选择是希尔排序的重要部分。只要最终步长为 1 任何步长序列都可以工作。

算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为插入排序，这就保证了数据一定会被排序。

Donald Shell 最初建议步长选择为 N/2 并且对步长取半直到步长达到 1。虽然这样取可以比 O(N2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长 5 进行了排序然后再以步长 3 进行排序，那么该数列不仅是以步长 3 有序，而且是以步长 5 有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就不会以如此短的时间完成排序了。

已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…)，该序列的项来自这两个算式。

这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

算法稳定性

由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。

直接插入排序和希尔排序的比较

• 直接插入排序是稳定的；而希尔排序是不稳定的。
• 直接插入排序更适合于原始记录基本有序的集合。
• 希尔排序的比较次数和移动次数都要比直接插入排序少，当 N 越大时，效果越明显。
• 在希尔排序中，增量序列 gap 的取法必须满足：**最后一个步长必须是 1 。 **
• 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

简单选择排序

要点

简单选择排序是一种选择排序。

选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

算法思想

1. 从待排序序列中，找到关键字最小的元素；
2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
3. 从余下的 N - 1 个元素中，找出关键字最小的元素，重复 1、2 步，直到排序结束。

如图所示，每趟排序中，将当前**第 i 小的元素放在位置 i **上。

核心代码

算法分析

简单选择排序算法的性能

时间复杂度

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则**比较次数总是 N (N - 1) / 2 **。

而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.

当序列反序时，移动次数最多，为 3N (N - 1) / 2。

所以，综合以上，简单排序的时间复杂度为 **O(N2)**。

空间复杂度

简单选择排序需要占用一个临时空间，在交换数值时使用。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

堆排序

要点

在介绍堆排序之前，首先需要说明一下，堆是个什么玩意儿。

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于 n 个元素的序列 {R0, R1, … , Rn} 当且仅当满足下列关系之一时，称之为堆：

• Ri <= R2i+1 且 Ri <= R2i+2 （小根堆）
• Ri >= R2i+1 且 Ri >= R2i+2 （大根堆）

其中 i=1,2,…,n/2 向下取整;

如上图所示，序列 R{3, 8,15, 31, 25} 是一个典型的小根堆。

堆中有两个父结点，元素 3 和元素 8。

元素 3 在数组中以 R[0] 表示，它的左孩子结点是 R[1]，右孩子结点是 R[2]。

元素 8 在数组中以 R[1] 表示，它的左孩子结点是 R[3]，右孩子结点是 R[4]，它的父结点是 R[0]。可以看出，它们满足以下规律：

设当前元素在数组中以 R[i] 表示，那么，

• 它的左孩子结点是：R[2*i+1];
• 它的右孩子结点是：R[2*i+2];
• 它的父结点是：R[(i-1)/2];
• R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

算法思想

• 首先，按堆的定义将数组 R[0..n]调整为堆（这个过程称为创建初始堆），交换 R[0]和 R[n]；
• 然后，将 R[0..n-1]调整为堆，交换 R[0]和 R[n-1]；
• 如此反复，直到交换了 R[0]和 R[1]为止。

以上思想可归纳为两个操作：

1. 根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
2. 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下，如何构建初始堆。

设有一个无序序列 { 1, 3,4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后，我们来看一下完整的堆排序处理：

还是针对前面提到的无序序列 { 1,3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。

核心代码

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

public void HeapAdjust(int[] array2, int parent, int length) {
    int temp = array2[parent]; // temp保存当前父节点
    int child = 2 * parent + 1; // 先获得左孩子

    while (child < length) {
        // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
        if (child + 1 < length && array2[child] < array2[child + 1]) {
            child++;
        }

        // 如果父结点的值已经大于孩子结点的值，则直接结束
        if (temp >= array2[child])
            break;

        // 把孩子结点的值赋给父结点
        array2[parent] = array2[child];

        // 选取孩子结点的左孩子结点,继续向下筛选
        parent = child;
        child = 2 * child + 1;
    }

    array2[parent] = temp;
}

public void heapSort(int[] list) {
    // 循环建立初始堆
    for (int i = list.length / 2; i >= 0; i--) {
        HeapAdjust(list, i, list.length);
    }

    // 进行n-1次循环，完成排序
    for (int i = list.length - 1; i > 0; i--) {
        // 最后一个元素和第一元素进行交换
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;

        // 筛选 R[0] 结点，得到i-1个结点的堆
        HeapAdjust(list, 0, i);
        System.out.format("第 %d 趟: \t", list.length - i);
        printPart(list, 0, list.length - 1);
    }
}

算法分析

堆排序算法的总体情况

时间复杂度

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。

当想得到一个序列中第 k 个最小的元素之前的部分排序序列，最好采用堆排序。

因为堆排序的时间复杂度是 **O(n+klog2n)**，若 k ≤ n/log2n，则可得到的时间复杂度为 **O(n)**。

算法稳定性

堆排序是一种不稳定的排序方法。

因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，

因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

归并排序

要点

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法思想

将待排序序列 R[0…n-1] 看成是 n 个长度为 1 的有序序列，将相邻的有序表成对归并，得到 n/2 个长度为 2 的有序表；将这些有序序列再次归并，得到 n/4 个长度为 4 的有序序列；如此反复进行下去，最后得到一个长度为 n 的有序序列。

综上可知：

归并排序其实要做两件事：

• “分解”——将序列每次折半划分。
• “合并”——将划分后的序列段两两合并后排序。

我们先来考虑第二步，如何合并？

在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。

这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。

先将他们合并到一个局部的暂存数组R2 中，带合并完成后再将 R2 复制回 R 中。

为了方便描述，我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。

每次从两个段中取出一个记录进行关键字的比较，将较小者放入 R2 中。最后将各段中余下的部分直接复制到 R2 中。

经过这样的过程，R2 已经是一个有序的序列，再将其复制回 R 中，一次合并排序就完成了。

核心代码

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

public void Merge(int[] array2, int low, int mid, int high) {
    int i = low; // i是第一段序列的下标
    int j = mid + 1; // j是第二段序列的下标
    int k = 0; // k是临时存放合并序列的下标
    int[] array2 = new int[high - low + 1]; // array2是临时合并序列

    // 扫描第一段和第二段序列，直到有一个扫描结束
    while (i <= mid && j <= high) {
        // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
        if (array2[i] <= array2[j]) {
            array2[k] = array2[i];
            i++;
            k++;
        } else {
            array2[k] = array2[j];
            j++;
            k++;
        }
    }

    // 若第一段序列还没扫描完，将其全部复制到合并序列
    while (i <= mid) {
        array2[k] = array2[i];
        i++;
        k++;
    }

    // 若第二段序列还没扫描完，将其全部复制到合并序列
    while (j <= high) {
        array2[k] = array2[j];
        j++;
        k++;
    }

    // 将合并序列复制到原始序列中
    for (k = 0, i = low; i <= high; i++, k++) {
        array2[i] = array2[k];
    }
}

掌握了合并的方法，接下来，让我们来了解如何分解。

在某趟归并中，设各子表的长度为 gap，则归并前 R[0…n-1] 中共有 n/gap 个有序的子表：R[0...gap-1], R[gap...2*gap-1], … , R[(n/gap)*gap ... n-1]。

调用 Merge 将相邻的子表归并时，必须对表的特殊情况进行特殊处理。

若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为 n-1。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public void MergePass(int[] array2, int gap, int length) {
    int i = 0;

    // 归并gap长度的两个相邻子表
    for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
        Merge(array2, i, i + gap - 1, i + 2 * gap - 1);
    }

    // 余下两个子表，后者长度小于gap
    if (i + gap - 1 < length) {
        Merge(array2, i, i + gap - 1, length - 1);
    }
}

public int[] sort(int[] list) {
    for (int gap = 1; gap < list.length; gap = 2 * gap) {
        MergePass(list, gap, list.length);
        System.out.print("gap = " + gap + ":\t");
        this.printAll(list);
    }
    return list;
}

算法分析

归并排序算法的性能

时间复杂度

归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是 **O(n*log2n)**。

空间复杂度

由前面的算法说明可知，算法处理过程中，需要一个大小为 n 的临时存储空间用以保存合并序列。

算法稳定性

在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。

归并排序和堆排序、快速排序的比较

若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。

若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。

若从平均情况下的排序速度考虑，应该选择快速排序。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

基数排序

要点

基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。

它是根据关键字中各位的值，通过对排序的 N 个元素进行若干趟“分配”与“收集”来实现排序的。

不妨通过一个具体的实例来展示一下，基数排序是如何进行的。

设有一个初始序列为: R {50, 123, 543, 187, 49, 30,0, 2, 11, 100}。

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的。

所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。

这时，得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序： {50, 30, 0, 100, 11, 2, 123,543, 187, 49}。

接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

算法分析

基数排序的性能

时间复杂度

通过上文可知，假设在基数排序中，r 为基数，d 为位数。则基数排序的时间复杂度为 **O(d(n+r))**。

我们可以看出，基数排序的效率和初始序列是否有序没有关联。

空间复杂度

在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要 n+r 个临时空间。

算法稳定性

在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。

示例代码

我的 Github 测试例

样本包含：数组个数为奇数、偶数的情况；元素重复或不重复的情况。且样本均为随机样本，实测有效。

设计模式概述

设计模式（Design pattern）代表了最佳的实践，通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

创建型模式

创建型模式简介

创建型模式抽象了实例化的过程。它将系统与它的对象创建、结合、表示的方式分离。

创建型模式都会将关于该系统使用哪些具体的类的信息封装起来。

在软件工程中，创建型模式是处理对象创建的设计模式，试图根据实际情况使用合适的方式创建对象。

基本的对象创建方式可能会导致设计上的问题，或增加设计的复杂度。创建型模式通过以某种方式控制对象的创建来解决问题。

创建型模式的指导思想是：

• 将系统使用的具体类封装起来。
• 隐藏这些具体类的实例创建和结合的方式。

创建型模式又分为对象创建型模式和类创建型模式。对象创建型模式处理对象的创建，类创建型模式处理类的创建。

• 对象创建型模式把对象创建的一部分推迟到另一个对象中。（代表模式：单例模式、建造者模式、原型模式、抽象工厂模式）
• 类创建型模式将它对象的创建推迟到子类中。（代表模式：工厂方法模式）

创建型模式应用

现代软件工程更加依赖对象的组合，而不是类的继承，强调从硬编码的行为转变到定义一组基本行为来组合成复杂的行为。

硬编码的行为不够灵活，因为如果想要改变设计的一部分，需要通过重写或者重新实现才能完成。

另外，硬编码没有提高重用性，而且难以跟踪错误。由于这些原因，创建型模式比硬编码的行为更有用。

创建型模式使设计变得更灵活，提供了不同的方式，从代码中移除了对需要实例化的具体类的引用。换句话说，这些模式增强了对象和类之间的独立性。

在以下情况中，可以考虑应用创建型模式：

• 一个系统需要和它的对象和产品的创建相互独立。
• 一组相关的对象被设计为一起使用。
• 隐藏一个类库的具体实现，仅暴露它们的接口。
• 创建独立复杂对象的不同表示。
• 一个类希望它的子类实现它所创建的对象。
• 类的实例化在运行时才指定。
• 一个类只能有一个实例，而且这个实例能在任何时候访问到。
• 实例应该能在不修改的情况下具有可扩展性。

创建型模式代表

创建型模式提供了创建对象的机制， 能够提升已有代码的灵活性和可复用性。

• 简单工厂模式 (Simple Factory)
• 工厂方法模式 (Factory Method)
• 抽象工厂模式 (Abstract Factory)
• 建造者模式 (Builder)
• 原型模式 (Prototype)
• 单例模式 (Singleton)

结构型模式

结构型模式介绍如何将对象和类组装成较大的结构， 并同时保持结构的灵活和高效。

• 适配器模式 (Adapter)
• 桥接模式 (Bridge)
• 组合模式 (Composite)
• 装饰模式 (Decorator)
• 外观模式 (Facade)
• 享元模式 (Flyweight)
• 代理模式 (Proxy)

行为型模式

行为模式负责对象间的高效沟通和职责委派。

• 模板方法模式 (Template Method)
• 命令模式 (Command)
• 迭代器模式 (Iterator)
• 观察者模式 (Observer)
• 解释器模式 (Interpreter)
• 中介者模式 (Mediator)
• 职责链模式 (Chain of Responsibility)
• 备忘录模式 (Memento)
• 策略模式 (Strategy)
• 访问者模式 (Visitor)
• 状态模式 (State)

📚 资料

• 《Head First 设计模式》
• 《大话设计模式》

🚪 传送

◾ 💧 钝悟的 IT 知识图谱 ◾

设计模式之状态模式

意图

状态模式（State） 是一种行为设计模式， 让你能在一个对象的内部状态变化时改变其行为， 使其看上去就像改变了自身所属的类一样。

适用场景

• 如果对象需要根据自身当前状态进行不同行为， 同时状态的数量非常多且与状态相关的代码会频繁变更的话， 可使用状态模式。
• 如果某个类需要根据成员变量的当前值改变自身行为， 从而需要使用大量的条件语句时， 可使用该模式。
• 当相似状态和基于条件的状态机转换中存在许多重复代码时， 可使用状态模式。

结构

结构说明

1. 上下文 （Context） 保存了对于一个具体状态对象的引用， 并会将所有与该状态相关的工作委派给它。 上下文通过状态接口与状态对象交互， 且会提供一个设置器用于传递新的状态对象。
2. 状态 （State） 接口会声明特定于状态的方法。 这些方法应能被其他所有具体状态所理解， 因为你不希望某些状态所拥有的方法永远不会被调用。
3. 具体状态 （Concrete States） 会自行实现特定于状态的方法。 为了避免多个状态中包含相似代码， 你可以提供一个封装有部分通用行为的中间抽象类。
   • 状态对象可存储对于上下文对象的反向引用。 状态可以通过该引用从上下文处获取所需信息， 并且能触发状态转移。
4. 上下文和具体状态都可以设置上下文的下个状态， 并可通过替换连接到上下文的状态对象来完成实际的状态转换。

结构代码范式

State : 定义一个接口以封装与 Context 的一个特定状态相关的行为。

1
2
3

abstract class State {
    public abstract void Handle(Context context);
}

ConcreteState : 每一个子类实现一个与 Context 的一个状态相关的行为。

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

class ConcreteStateA extends State {
    @Override
    public void Handle(Context context) {
        context.SetState(new ConcreteStateB());
    }
}

class ConcreteStateB extends State {
    @Override
    public void Handle(Context context) {
        context.SetState(new ConcreteStateA());
    }
}

Context : 维护一个 ConcreteState 子类的实例，这个实例定义当前的状态。

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

class Context {
    private State state;
    public Context(State state) {
        this.state = state;
    }

    public void SetState(State state) {
        this.state = state;
        System.out.println("当前状态：" + state.getClass().getName());
    }
    public State GetState() {
        return state;
    }

    public void Request() {
        state.Handle(this);
    }
}

客户端

1
2
3
4
5
6
7

public class StatePattern {
    public static void main(String[] args) {
        Context c = new Context(new ConcreteStateA());
        c.Request();
        c.Request();
    }
}

输出

1
2

当前状态：ConcreteStateB
当前状态：ConcreteStateA

伪代码

在本例中， 状态模式将根据当前回放状态， 让媒体播放器中的相同控件完成不同的行为。

播放器的主要对象总是会连接到一个负责播放器绝大部分工作的状态对象中。 部分操作会更换播放器当前的状态对象， 以此改变播放器对于用户互动所作出的反应。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

// 音频播放器（Audio­Player）类即为上下文。它还会维护指向状态类实例的引用，
// 该状态类则用于表示音频播放器当前的状态。
class AudioPlayer is
    field state: State
    field UI, volume, playlist, currentSong

    constructor AudioPlayer() is
        this.state = new ReadyState(this)

        // 上下文会将处理用户输入的工作委派给状态对象。由于每个状态都以不
        // 同的方式处理输入，其结果自然将依赖于当前所处的状态。
        UI = new UserInterface()
        UI.lockButton.onClick(this.clickLock)
        UI.playButton.onClick(this.clickPlay)
        UI.nextButton.onClick(this.clickNext)
        UI.prevButton.onClick(this.clickPrevious)

    // 其他对象必须能切换音频播放器当前所处的状态。
    method changeState(state: State) is
        this.state = state

    // UI 方法会将执行工作委派给当前状态。
    method clickLock() is
        state.clickLock()
    method clickPlay() is
        state.clickPlay()
    method clickNext() is
        state.clickNext()
    method clickPrevious() is
        state.clickPrevious()

    // 状态可调用上下文的一些服务方法。
    method startPlayback() is
        // ...
    method stopPlayback() is
        // ...
    method nextSong() is
        // ...
    method previousSong() is
        // ...
    method fastForward(time) is
        // ...
    method rewind(time) is
        // ...


// 所有具体状态类都必须实现状态基类声明的方法，并提供反向引用指向与状态相
// 关的上下文对象。状态可使用反向引用将上下文转换为另一个状态。
abstract class State is
    protected field player: AudioPlayer

    // 上下文将自身传递给状态构造函数。这可帮助状态在需要时获取一些有用的
    // 上下文数据。
    constructor State(player) is
        this.player = player

    abstract method clickLock()
    abstract method clickPlay()
    abstract method clickNext()
    abstract method clickPrevious()


// 具体状态会实现与上下文状态相关的多种行为。
class LockedState extends State is

    // 当你解锁一个锁定的播放器时，它可能处于两种状态之一。
    method clickLock() is
        if (player.playing)
            player.changeState(new PlayingState(player))
        else
            player.changeState(new ReadyState(player))

    method clickPlay() is
        // 已锁定，什么也不做。

    method clickNext() is
        // 已锁定，什么也不做。

    method clickPrevious() is
        // 已锁定，什么也不做。


// 它们还可在上下文中触发状态转换。
class ReadyState extends State is
    method clickLock() is
        player.changeState(new LockedState(player))

    method clickPlay() is
        player.startPlayback()
        player.changeState(new PlayingState(player))

    method clickNext() is
        player.nextSong()

    method clickPrevious() is
        player.previousSong()


class PlayingState extends State is
    method clickLock() is
        player.changeState(new LockedState(player))

    method clickPlay() is
        player.stopPlayback()
        player.changeState(new ReadyState(player))

    method clickNext() is
        if (event.doubleclick)
            player.nextSong()
        else
            player.fastForward(5)

    method clickPrevious() is
        if (event.doubleclick)
            player.previous()
        else
            player.rewind(5)

案例

使用示例： 在 Java 语言中， 状态模式通常被用于将基于 switch语句的大型状态机转换为对象。

这里是核心 Java 程序库中一些状态模式的示例：

• javax.faces.lifecycle.LifeCycle#execute() （由 Faces­Servlet控制： 行为依赖于当前 JSF 生命周期的阶段 （状态））

识别方法： 状态模式可通过受外部控制且能根据对象状态改变行为的方法来识别。

与其他模式的关系

• 桥接模式、 状态模式和策略模式 （在某种程度上包括适配器模式） 模式的接口非常相似。 实际上， 它们都基于组合模式——即将工作委派给其他对象， 不过也各自解决了不同的问题。 模式并不只是以特定方式组织代码的配方， 你还可以使用它们来和其他开发者讨论模式所解决的问题。
• 状态可被视为策略的扩展。 两者都基于组合机制： 它们都通过将部分工作委派给 “帮手” 对象来改变其在不同情景下的行为。 策略使得这些对象相互之间完全独立， 它们不知道其他对象的存在。 但状态模式没有限制具体状态之间的依赖， 且允许它们自行改变在不同情景下的状态。

参考资料

• 《Head First 设计模式》
• 《大话设计模式》
• 设计模式教程

设计模式之访问者模式

意图

访问者模式（Visitor） 是一种行为设计模式， 它能将算法与其所作用的对象隔离开来。

适用场景

• 如果你需要对一个复杂对象结构 （例如对象树） 中的所有元素执行某些操作， 可使用访问者模式。
• 可使用访问者模式来清理辅助行为的业务逻辑。
• 当某个行为仅在类层次结构中的一些类中有意义， 而在其他类中没有意义时， 可使用该模式。

结构

结构说明

1. 访问者 （Visitor） 接口声明了一系列以对象结构的具体元素为参数的访问者方法。 如果编程语言支持重载， 这些方法的名称可以是相同的， 但是其参数一定是不同的。
2. 具体访问者 （Concrete Visitor） 会为不同的具体元素类实现相同行为的几个不同版本。
3. 元素 （Element） 接口声明了一个方法来 “接收” 访问者。 该方法必须有一个参数被声明为访问者接口类型。
4. 具体元素 （Concrete Element） 必须实现接收方法。 该方法的目的是根据当前元素类将其调用重定向到相应访问者的方法。 请注意， 即使元素基类实现了该方法， 所有子类都必须对其进行重写并调用访问者对象中的合适方法。
5. 客户端 （Client） 通常会作为集合或其他复杂对象 （例如一个组合树） 的代表。 客户端通常不知晓所有的具体元素类， 因为它们会通过抽象接口与集合中的对象进行交互。

结构代码范式

Visitor : 为该对象结构中 ConcreteElement 的每一个类声明一个 Visit 操作。

1
2
3
4

abstract class Visitor {
    public abstract void VisitConcreteElementA(ConcreteElementA elementA);
    public abstract void VisitConcreteElementB(ConcreteElementB elementB);
}

ConcreteVisitor : 实现每个由 Visitor 声明的操作。每个操作实现算法的一部分，而该算法片段乃是对应于结构中对象的类。

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

class ConcreteVisitor1 extends Visitor {
    @Override
    public void VisitConcreteElementA(ConcreteElementA elementA) {
        System.out.println(this.getClass().getName() + " 访问 " + elementA.getClass().getName());
    }

    @Override
    public void VisitConcreteElementB(ConcreteElementB elementB) {
        System.out.println(this.getClass().getName() + " 访问 " + elementB.getClass().getName());
    }
}

class ConcreteVisitor2 extends Visitor {
    @Override
    public void VisitConcreteElementA(ConcreteElementA elementA) {
        System.out.println(this.getClass().getName() + " 访问 " + elementA.getClass().getName());
    }

    @Override
    public void VisitConcreteElementB(ConcreteElementB elementB) {
        System.out.println(this.getClass().getName() + " 访问 " + elementB.getClass().getName());
    }
}

Element : 定义一个 Accpet 操作，它以一个访问者为参数。

1
2
3

abstract class Element {
    public abstract void Accept(Visitor visitor);
}

ConcreteElement : 实现 Element 声明的 Accept 操作。

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

class ConcreteElementA extends Element {
    @Override
    public void Accept(Visitor visitor) {
        visitor.VisitConcreteElementA(this);
    }
}

class ConcreteElementB extends Element {
    @Override
    public void Accept(Visitor visitor) {
        visitor.VisitConcreteElementB(this);
    }
}

ObjectStructure : 可以枚举它的元素，可以提供一个高层的接口以允许访问者访问它的元素。

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

class ObjectStructure {
    private List<Element> elements = new ArrayList<Element>();

    public void Attach(Element element) {
        elements.add(element);
    }

    public void Detach(Element element) {
        elements.remove(element);
    }

    public void Accept(Visitor visitor) {
        for (Element elem : elements) {
            elem.Accept(visitor);
        }
    }
}

客户端

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

public class VisitorPattern {
    public static void main(String[] args) {
        ObjectStructure o = new ObjectStructure();
        o.Attach(new ConcreteElementA());
        o.Attach(new ConcreteElementB());

        ConcreteVisitor1 v1 = new ConcreteVisitor1();
        ConcreteVisitor2 v2 = new ConcreteVisitor2();

        o.Accept(v1);
        o.Accept(v2);
    }
}

输出

1
2
3
4

ConcreteVisitor1 访问 ConcreteElementA
ConcreteVisitor1 访问 ConcreteElementB
ConcreteVisitor2 访问 ConcreteElementA
ConcreteVisitor2 访问 ConcreteElementB

伪代码

在本例中， 访问者模式为几何图像层次结构添加了对于 XML 文件导出功能的支持。

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

// 元素接口声明了一个`accept（接收）`方法，它会将访问者基础接口作为一个参
// 数。
interface Shape is
    method move(x, y)
    method draw()
    method accept(v: Visitor)

// 每个具体元素类都必须以特定方式实现`accept`方法，使其能调用相应元素类的
// 访问者方法。
class Dot implements Shape is
    // ...

    // 注意我们正在调用的`visitDot（访问点）`方法与当前类的名称相匹配。
    // 这样我们能让访问者知晓与其交互的元素类。
    method accept(v: Visitor) is
        v.visitDot(this)

class Circle implements Shape is
    // ...
    method accept(v: Visitor) is
        v.visitCircle(this)

class Rectangle implements Shape is
    // ...
    method accept(v: Visitor) is
        v.visitRectangle(this)

class CompoundShape implements Shape is
    // ...
    method accept(v: Visitor) is
        v.visitCompoundShape(this)


// 访问者接口声明了一组与元素类对应的访问方法。访问方法的签名能让访问者准
// 确辨别出与其交互的元素所属的类。
interface Visitor is
    method visitDot(d: Dot)
    method visitCircle(c: Circle)
    method visitRectangle(r: Rectangle)
    method visitCompoundShape(cs: CompoundShape)

// 具体访问者实现了同一算法的多个版本，而且该算法能与所有具体类进行交互。
//
// 访问者模式在复杂对象结构（例如组合树）上使用时能发挥最大作用。在这种情
// 况下，它可以存储算法的一些中间状态，并同时在结构中的不同对象上执行访问
// 者方法。这可能会非常有帮助。
class XMLExportVisitor implements Visitor is
    method visitDot(d: Dot) is
        // 导出点（dot）的 ID 和中心坐标。

    method visitCircle(c: Circle) is
        // 导出圆（circle）的 ID 、中心坐标和半径。

    method visitRectangle(r: Rectangle) is
        // 导出长方形（rectangle）的 ID 、左上角坐标、宽和长。

    method visitCompoundShape(cs: CompoundShape) is
        // 导出图形（shape）的 ID 和其子项目的 ID 列表。


// 客户端代码可在不知晓具体类的情况下在一组元素上运行访问者操作。“接收”操
// 作会将调用定位到访问者对象的相应操作上。
class Application is
    field allShapes: array of Shapes

    method export() is
        exportVisitor = new XMLExportVisitor()

        foreach (shape in allShapes) do
            shape.accept(exportVisitor)

案例

使用示例： 访问者不是常用的设计模式， 因为它不仅复杂， 应用范围也比较狭窄。

这里是 Java 程序库代码中该模式的一些示例：

• javax.lang.model.element.AnnotationValue 和 Annotation­Value­Visitor
• javax.lang.model.element.Element 和 Element­Visitor
• javax.lang.model.type.TypeMirror 和 Type­Visitor
• java.nio.file.FileVisitor 和 Simple­File­Visitor
• javax.faces.component.visit.VisitContext 和 Visit­Callback

与其他模式的关系

• 你可以将访问者模式视为命令模式的加强版本， 其对象可对不同类的多种对象执行操作。
• 你可以使用访问者对整个组合模式树执行操作。
• 可以同时使用访问者和迭代器模式来遍历复杂数据结构， 并对其中的元素执行所需操作， 即使这些元素所属的类完全不同。

参考资料

• 《Head First 设计模式》
• 《大话设计模式》
• 设计模式教程

设计模式之策略模式

意图

策略模式（Strategy） 是一种行为设计模式， 它能让你定义一系列算法， 并将每种算法分别放入独立的类中， 以使算法的对象能够相互替换。

适用场景

• 当你想使用对象中各种不同的算法变体， 并希望能在运行时切换算法时， 可使用策略模式。
• 当你有许多仅在执行某些行为时略有不同的相似类时， 可使用策略模式。
• 如果算法在上下文的逻辑中不是特别重要， 使用该模式能将类的业务逻辑与其算法实现细节隔离开来。
• 当类中使用了复杂条件运算符以在同一算法的不同变体中切换时， 可使用该模式。

结构

结构说明

1. 上下文 （Context） 维护指向具体策略的引用， 且仅通过策略接口与该对象进行交流。
2. 策略 （Strategy） 接口是所有具体策略的通用接口， 它声明了一个上下文用于执行策略的方法。
3. 具体策略 （Concrete Strategies） 实现了上下文所用算法的各种不同变体。
4. 当上下文需要运行算法时， 它会在其已连接的策略对象上调用执行方法。 上下文不清楚其所涉及的策略类型与算法的执行方式。
5. 客户端 （Client） 会创建一个特定策略对象并将其传递给上下文。 上下文则会提供一个设置器以便客户端在运行时替换相关联的策略。

结构代码范式

Strategy : 定义所有算法的公共接口(AlgorithmInterface)。Context 使用这个接口去调用 ConcreteStrategy 定义的具体算法。

1
2
3

abstract class Strategy {
    public abstract void AlgorithmInterface();
}

ConcreteStrategy : 实现 Strategy 中的算法接口(AlgorithmInterface)。

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

class ConcreteStrategyA extends Strategy {
    @Override
    public void AlgorithmInterface() {
        System.out.println("算法A");
    }
}

class ConcreteStrategyB extends Strategy {
    @Override
    public void AlgorithmInterface() {
        System.out.println("算法B");
    }
}

class ConcreteStrategyC extends Strategy {
    @Override
    public void AlgorithmInterface() {
        System.out.println("算法C");
    }
}

Context : 用一个 ConcreteStrategy 来配置。维护一个对 Strategy 对象的引用。

1
2
3
4
5
6
7
8
9
10

class Context {
    Strategy strategy;
    public Context(Strategy strategy) {
        this.strategy = strategy;
    }

    public void ContextInterface() {
        strategy.AlgorithmInterface();
    }
}

客户端

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

public class StrategyPattern {
    public static void main(String[] args) {
        Context context1 = new Context(new ConcreteStrategyA());
        context1.ContextInterface();

        Context context2 = new Context(new ConcreteStrategyB());
        context2.ContextInterface();

        Context context3 = new Context(new ConcreteStrategyC());
        context3.ContextInterface();
    }
}

输出

1
2
3

算法A
算法B
算法C

伪代码

在本例中， 上下文使用了多个策略来执行不同的计算操作。

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

// 策略接口声明了某个算法各个不同版本间所共有的操作。上下文会使用该接口来
// 调用有具体策略定义的算法。
interface Strategy is
    method execute(a, b)

// 具体策略会在遵循策略基础接口的情况下实现算法。该接口实现了它们在上下文
// 中的互换性。
class ConcreteStrategyAdd implements Strategy is
    method execute(a, b) is
        return a + b

class ConcreteStrategySubtract implements Strategy is
    method execute(a, b) is
        return a - b

class ConcreteStrategyMultiply implements Strategy is
    method execute(a, b) is
        return a * b

// 上下文定义了客户端关注的接口。
class Context is
    // 上下文会维护指向某个策略对象的引用。上下文不知晓策略的具体类。上下
    // 文必须通过策略接口来与所有策略进行交互。
    private strategy: Strategy

    // 上下文通常会通过构造函数来接收策略对象，同时还提供设置器以便在运行
    // 时切换策略。
    method setStrategy(Strategy strategy) is
        this.strategy = strategy

    // 上下文会将一些工作委派给策略对象，而不是自行实现不同版本的算法。
    method executeStrategy(int a, int b) is
        return strategy.execute(a, b)


// 客户端代码会选择具体策略并将其传递给上下文。客户端必须知晓策略之间的差
// 异，才能做出正确的选择。
class ExampleApplication is
    method main() is

        创建上下文对象。

        读取第一个数。
        读取最后一个数。
        从用户输入中读取期望进行的行为。

        if (action == addition) then
            context.setStrategy(new ConcreteStrategyAdd())

        if (action == subtraction) then
            context.setStrategy(new ConcreteStrategySubtract())

        if (action == multiplication) then
            context.setStrategy(new ConcreteStrategyMultiply())

        result = context.executeStrategy(First number, Second number)

        打印结果。

案例

使用示例： 策略模式在 Java 代码中很常见。 它经常在各种框架中使用， 能在不扩展类的情况下向用户提供改变其行为的方式。

Java 8 开始支持 lambda 方法， 它可作为一种替代策略模式的简单方式。

这里有一些核心 Java 程序库中策略模式的示例：

• 对 java.util.Comparator#compare() 的调用来自 Collections#sort().
• javax.servlet.http.HttpServlet： service­()方法， 还有所有接受 Http­Servlet­Request和 Http­Servlet­Response对象作为参数的 do­XXX()方法。
• javax.servlet.Filter#doFilter()

识别方法： 策略模式可以通过允许嵌套对象完成实际工作的方法以及允许将该对象替换为不同对象的设置器来识别。

与其他模式的关系

• 桥接模式、 状态模式和策略模式 （在某种程度上包括适配器模式） 模式的接口非常相似。 实际上， 它们都基于组合模式——即将工作委派给其他对象， 不过也各自解决了不同的问题。 模式并不只是以特定方式组织代码的配方， 你还可以使用它们来和其他开发者讨论模式所解决的问题。
• 命令模式和策略看上去很像， 因为两者都能通过某些行为来参数化对象。 但是， 它们的意图有非常大的不同。
  • 你可以使用命令来将任何操作转换为对象。 操作的参数将成为对象的成员变量。 你可以通过转换来延迟操作的执行、 将操作放入队列、 保存历史命令或者向远程服务发送命令等。
  • 另一方面， 策略通常可用于描述完成某件事的不同方式， 让你能够在同一个上下文类中切换算法。
• 装饰模式可让你更改对象的外表， 策略则让你能够改变其本质。
• 模板方法模式基于继承机制： 它允许你通过扩展子类中的部分内容来改变部分算法。 策略基于组合机制： 你可以通过对相应行为提供不同的策略来改变对象的部分行为。 模板方法在类层次上运作， 因此它是静态的。 策略在对象层次上运作， 因此允许在运行时切换行为。
• 状态可被视为策略的扩展。 两者都基于组合机制： 它们都通过将部分工作委派给 “帮手” 对象来改变其在不同情景下的行为。 策略使得这些对象相互之间完全独立， 它们不知道其他对象的存在。 但状态模式没有限制具体状态之间的依赖， 且允许它们自行改变在不同情景下的状态。

参考资料

• 《Head First 设计模式》
• 《大话设计模式》
• 设计模式教程