算法思想与设计模式的基本介绍

1. 数据结构与算法思想

1.1 数据结构概述

1.1.1 数据结构是什么

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。本文将介绍以下八个常见的数据结构。

1.1.2 数据结构研究内容

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般有以下几种常用运算：

• 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
• 插入：往数据结构中增加新的节点。
• 删除：把指定的结点从数据结构中去掉。
• 更新：改变指定节点的一个或多个字段的值。
• 排序：把节点按某种指定的顺序重新排列。例如递增或递减。

1.2 常见数据结构及算法思想

1.2.1 常见数据结构

[1] 数组

数组是一种线性结构，而且在物理内存中也占据着一块连续空间。

• 优点：访问数据简单。
• 缺点：添加和删除数据比较耗时间。
• 使用场景：频繁查询，对存储空间要求不大，很少增加和删除的情况。

数据访问：由于数据是存储在连续空间内，所以每个数据的内存地址都是通过数据小标算出，所以可以直接访问目标数据（这叫做“随机访问”）。比如下方，可以直接使用a[2]访问Red。

数据添加：数据添加需要移动其他数据。首先增加足够的空间，然后把已有的数据一个个移开。

数据删除：反过来，如果想要输出数据Green，也是一样挨个把数据往反方向移动。

[2] 链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域（内存空间），另一个是指向下一个结点地址的指针域。

• 优点：数据添加和删除方便
• 缺点：访问比较耗费时间
• 适用场景：数据量较小，需要频繁增加，删除操作的场景

数组和链表数据结构对比列表如下：

	访问	添加	删除
链表	慢	快	快
数组	快	慢	慢

数据访问：因为数据都是分散存储的，所以想要访问数据，只能从第一个数据开始，顺着指针的指向逐一往下访问。

数据添加：将Blue的指针指向的位置变成Green，然后再把Green的指针指向Yellow。

数据删除：只要改变指针的指向就可以了，比如删除Yellow，只需把Green指针指向的位置从Yellow编程Red即可。虽然Yellow本身还存储在内存中，但是不管从哪里都无法访问这个数据，所以也就没有特意去删除它的必要了。今后需要用到Yellow所在的存储空间时，只要用新数据覆盖掉就可以了。

[3] 栈

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。从栈顶放入元素的操作叫入栈，取出元素叫出栈。

• 特点：后进先出（Last In First Out，简称LIFO）

[4] 队列

队列中的添加和删除数据的操作分别是在两端进行的。队列可以在一端添加元素，在另一端取出元素。

• 特点：先进先出（First In First Out，简称FIFO）

[1] 数据入队：队列的插入操作，叫做入队。它是将数据元素从队尾进行插入的过程。

[2] 数据出队：队列的删除操作，叫做 出队。它是将队首元素进行删除的过程

[3] 清空队列：队列的清空操作，就是一直出队，直到队列为空的过程，当队首和队尾重合时，就代表队尾为空了。

[4] 获取队首数据：对于一个队列来说只能获取队首数据 。

[5] 获取队列元素个数：队列元素个数一般用一个额外变量存储，入队时加一，出队时减一。这样获取队列元素的时候就不需要遍历整个队列。

[6] 队列的判空：当队列元素个数为零时，就是一个空队，空队不允许出队操作。

[5] 树

它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。二叉树是树的特殊一种，具有如下特点：

• 每个结点最多有两颗子结点。
• 左子树和右子树是有顺序的，次序不能颠倒。
• 即使某结点只有一个子树，也要区分左右子树。

二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。

二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构在二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如MySQL的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树，这些二叉树的功能强大，但算法上比较复杂。

[6] 堆

堆是一种图的树形结构，被用于实现“优先队列”。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆的树形结构中，各个顶点被称为“结点”，数据就存储在这些结点中。

标准定义上，我们认为一颗树满足以下的两点，就是一个堆。

• 一颗完全二叉树
• 每个节点的值大于等于（或小于等于）其子树中每个节点的值

根据子节点与父节点值的大小关系，可以把堆分为：

• 最大堆：任意父节点都比其子节点的值要大
• 最小堆：任意父节点都比其子节点的值要小

比如下图中， 1、2 为最大堆，3 是最小堆，4 不是堆。

树的存储方式一般有链式存储和线性存储，分别对应我们常见的链表和数组两种方式，对于完全二叉树而言，用数组来存储是非常节省存储空间的，因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，所以堆我们一般也用数组来存储。

1）堆的插入：往堆中插入一个元素后，为了保持堆的特性，我们需要对插入元素的位置进行调整，这个过程叫做堆化（heapify），以最大堆为例：

堆化的过程其实非常简单，比如上图中我们往最大堆中插入一个元素 “22”，为了保持堆的特性，只需要顺着节点所在的路径，向上与其父节点进行对比交换，直到满足大小关系即可。

2）堆的删除：先删除叶子节点（最后一个元素），把它放到堆顶（与堆顶元素交换），然后从上往下进行堆化。

[7] 散列表

散列表（Hash Table），也叫哈希表，是实现字典操作的一种有效数据结构。用的是数组支持按照下标随机访数据的时候，时间复杂度为O(1)特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

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

[8] 图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。按照顶点指向的方向可分为无向图和有向图。

邻接矩阵是图的常用存储表示，它的底层依赖一个二维数组。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

优点是邻接矩阵的存储方式简单直接，可以高效的获取两个顶点的关系，计算方便（如：求解最短路径 Floyd-Warshall 算法），缺点是比较浪费存储空间。

1.2.2 常见算法思想

[1] 递推法

递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

[2] 递归法

程序调用自身的编程技巧称为递归。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：递归就是在过程或函数里调用自身。在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

[3] 穷举法

穷举法，或称为暴力破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

[4] 贪心算法

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

贪婪算法是一种改进了的分级处理方法，其核心是根据题意选取一种量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量，如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。 一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。

[5] 分治法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征：

• 该问题的规模缩小到一定的程度就可以容易地解决；
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
• 利用该问题分解出的子问题的解可以合并为该问题的解；
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

[6] 动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

[7] 迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令进行重复执行，在每次执行这组指令时，都从变量的原值推出它的一个新值。

[8] 分支界限法

分支界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限，因此这种算法一般可以求得最优解。

与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。

[9] 回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

1.3 常见排序算法

1.3.1 排序算法概述

[1] 术语说明

排序：对一序列对象根据某个关键字进行排序。常见术语如下：

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
• 内排序：所有排序操作都在内存中完成。
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
• 时间复杂度： 一个算法执行所耗费的时间。
• 空间复杂度：运行完一个程序所需内存的大小。

[2] 算法对比

十大常见排序算法的对比如下：

说明：

• n: 数据规模
• k: “桶”的个数
• In-place: 占用常数内存，不占用额外内存
• Out-place: 占用额外内存

[3] 算法分类

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。比较排序的优势是：适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

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

1.3.2 排序算法原理及实现

排序算法的代码我已放在了Github，有需要的自取：https://github.com/Logistic98/sort-algorithm (opens new window)

[1] 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1）算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

2）动图演示

3）代码实现

/**
 * 冒泡排序
 */
public class BubbleSort implements Sort {
    @Override
    public void sort(int[] array) {
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
    }
}

4）算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

[2] 选择排序

选择排序（Selection Sort）是表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1）算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1..n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

2）动图演示

3）代码实现

/**
 * 选择排序
 */
public class SelectionSort implements Sort{
    @Override
    public void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) {   // 找到最小的数
                    minIndex = j; // 将最小数的索引保存
                }
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }
}

4）算法分析

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

[3] 插入排序

插入排序（Insertion-Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

1）算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

2）动图演示

3）代码实现

/**
 * 插入排序
 */
public class InsertSort implements Sort {
    @Override
    public void sort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
    }
}

4）算法分析

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

[4] 希尔排序

希尔排序（Shell Sort）是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

1）算法描述

我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们使用希尔增量作为示例。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 按增量序列个数k，对序列进行k 趟排序；
• 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

2）动图演示

3）代码实现

/**
 * 希尔排序
 */
public class ShellSort implements Sort {
    @Override
    public void sort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }
}

4）算法分析

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)

[5] 快速排序

快速排序（Quick Sort）的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1）算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

2）动图演示

3）代码实现

/**
 * 快速排序
 */
public class QuickSort implements Sort {
    @Override
    public void sort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private void quick(int[] array, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(array, left, right);
            quick(array, left, partitionIndex - 1);
            quick(array, partitionIndex + 1, right);
        }
    }

    private int partition(int[] array, int left, int right) {
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (array[i] < array[pivot]) {
                swap(array, i, index);
                index++;
            }
        }
        swap(array, pivot, index - 1);
        return index - 1;
    }

    private void swap(int array[], int x, int y) {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

4）算法分析

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

[6] 其他排序算法

1）归并排序

归并排序（Merge Sort）和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

2）堆排序

堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)

3）计数排序

计数排序（Counting Sort）的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)

4）桶排序

桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)

5）基数排序

基数排序（Radix Sort）也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数。基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)

1.3.3 排序算法的效率测试

可以写成一个测试类工具包，能够更简便地研究排序算法的时间复杂度。

SortUtils.java

import java.text.SimpleDateFormat;
import java.util.Random;

/**
 * 整数排序测试工具类
 */
public class SortUtils {

    /**
     * 生成一个乱序的数组
     *
     * @param count       数组的数量
     * @param startRanger 数字范围起始值
     * @param endRanger   数字范围终止值
     * @return 乱序的整数数组
     */
    public static int[] generateRandomArray(int count, int startRanger, int endRanger) {
        if (startRanger <= endRanger) {
            int[] arr = new int[count];
            Random random = new Random();
            for (int i = 0; i < count; i++) {
                arr[i] = startRanger + random.nextInt(endRanger - startRanger );
            }
            return arr;
        } else {
            return null;
        }

    }

    /**
     * 生成一个从0开始的近乎顺序的整型数组
     *
     * @param count     数组的数量
     * @param swapCount 数字范围起始值
     * @return 近乎顺序的整型数组
     */
    public static int[] generateNearlyOrderedArray(int count, int swapCount) {

        int[] arr = new int[count];
        for (int i = 0; i < count; i++) {
            arr[i] = i;
        }
        Random random = new Random();
        for (int i = 0; i < swapCount; i++) {
            int x = random.nextInt(count);
            int y = random.nextInt(count);
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
        return arr;

    }

    /**
     * 对整型数组做完全拷贝
     *
     * @param source 源数组
     * @return 数组拷贝
     */
    public static int[] copyArray(int[] source) {
        if (source != null) {
            int dest[] = new int[source.length];
            for (int i = 0; i < source.length; i++) {
                dest[i] = source[i];
            }
            return dest;
        } else {
            return null;
        }
    }

    /**
     * 判断整型数组是否已经升序排列
     *
     * @param arr 整型数组
     * @return 已经升序排列为true否则为false
     */
    public static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 遍历打印数组
     * @param arr 整型数组
     */
    public static void printArray(int[] arr) {
        if (arr!=null) {
            System.out.print("[");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i]);
                if (i != arr.length - 1) {
                    System.out.print(",");
                } else {
                    System.out.println("]");
                }
            }
        }else{
            System.out.println("数组为空!");
        }
    }

    /**
     * 通过排序接口，调用各种排序算法进行测试
     * @param sortName 排序算法名称
     * @param sort 排序统一接口
     * @param arr 整型数组
     */
    public static void testSort(final String sortName,Sort sort,int[] arr){
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        Long start = System.currentTimeMillis();
        //System.out.println(sortName+"排序开始时间：" + sdf.format(start));
        sort.sort(arr);
        Long end = System.currentTimeMillis();
        //System.out.println(sortName+"排序结束时间：" + sdf.format(end));
        System.out.println(sortName+"排序耗用了" + (end - start) + "毫秒");
        //断言判断该数组是否已实现升序排序
        assert(isSorted(arr));
    }

}

Sort.java

/**
 * 整型数组排序统一接口定义
 */
public interface Sort {

    /**
     * 整型排序
     * @param arr 待排序数组
     */
    void sort(int[] arr);
}

SortTest.java

/**
 * 整数排序测试类
 */
public class SortTest {

    public static void main(String[] args) {
        int count=100000;

        System.out.println("========== 随机乱序 ==========");
        // 产生一个随机乱序的数组
        int[] randArr = SortUtils.generateRandomArray(count, 0, count);
        SortUtils.testSort("1.【冒泡排序】",new BubbleSort(),SortUtils.copyArray(randArr));
        SortUtils.testSort("2.【选择排序】",new SelectionSort(),SortUtils.copyArray(randArr));
        SortUtils.testSort("3.【插入排序】",new InsertSort(),SortUtils.copyArray(randArr));
        SortUtils.testSort("4.【希尔排序】",new ShellSort(),SortUtils.copyArray(randArr));
        SortUtils.testSort("5.【快速排序】",new QuickSort(),SortUtils.copyArray(randArr));

        System.out.println("========== 近乎顺序 ==========");
        // 产生一个近乎顺序的数组
        int[] orderArr = SortUtils.generateNearlyOrderedArray(count, 100);
        SortUtils.testSort("1.【冒泡排序】",new BubbleSort(),SortUtils.copyArray(orderArr));
        SortUtils.testSort("2.【选择排序】",new SelectionSort(),SortUtils.copyArray(orderArr));
        SortUtils.testSort("3.【插入排序】",new InsertSort(),SortUtils.copyArray(orderArr));
        SortUtils.testSort("4.【希尔排序】",new ShellSort(),SortUtils.copyArray(orderArr));
        SortUtils.testSort("5.【快速排序】",new QuickSort(),SortUtils.copyArray(orderArr));
    }
}

放入具体的排序算法后，执行main方法，测试排序所需耗时。显而易见，在数据量比较大的情况下，不同排序算法的耗时差异是非常大的。

2. 设计模式与开发原则

2.1 设计模式概述

2.1.1 什么是设计模式

设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。 设计模式于己于他人于系统都是多赢的，设计模式使代码编写真正工程化，是软件工程的基石，如同大厦的一块块砖石一样。项目中合理的运用设计模式可以完美的解决很多问题，每种模式在现在中都有相应的原理来与之对应，每一个模式描述了一个在我们周围不断重复发生的问题，以及该问题的核心解决方案，这也是它能被广泛应用的原因。

简而言之：

• 模式：在某些场景下，针对某类问题的某种通用的解决方案。
• 场景：项目所在的环境
• 问题：约束条件，项目目标等
• 解决方案：通用、可复用的设计，解决约束达到目标。

2.1.2 设计模式分类

创建型模式：对象实例化的模式，创建型模式用于解耦对象的实例化过程。

结构型模式：把类或对象结合在一起形成一个更大的结构。

行为型模式：类和对象如何交互，及划分责任和算法。

2.1.3 各设计模式的关键点

创建型模式

• 单例模式（Singleton）：某个类只能有一个实例，提供一个全局的访问点。
• 工厂方法模式（Factory Method）：定义一个创建对象的接口，让子类决定实例化那个类。
• 抽象工厂模式（Abstract Factory）：创建相关或依赖对象的家族，而无需明确指定具体类。
• 建造者模式（BuilderPattern）：封装一个复杂对象的构建过程，并可以按步骤构造。
• 原型模式（Prototype）：通过复制现有的实例来创建新的实例。

结构型模式

• 适配器模式（Adapter）：将一个类的方法接口转换成客户希望的另外一个接口。
• 桥接模式（Bridge）：将抽象部分和它的实现部分分离，使它们都可以独立的变化。
• 组合模式（Composite）：将对象组合成树形结构以表示“部分-整体”的层次结构。
• 装饰模式（Decorator）：动态的给对象添加新的功能。
• 外观模式（Facade）：对外提供一个统一的方法，来访问子系统中的一组接口。
• 亨元模式（Flyweight）：通过共享技术来有效的支持大量细粒度的对象。
• 代理模式（Proxy）：为其他对象提供一个代理以便控制这个对象的访问。

行为型模式

• 访问者模式（Visitor）：在不改变数据结构的前提下，增加作用于一组对象元素的新功能。
• 模板模式（Template）：定义一个算法结构，而将一些步骤延迟到子类实现。
• 策略模式（Strategy）：定义一系列算法，把他们封装起来，并且使它们可以相互替换。
• 状态模式（State）：允许一个对象在其对象内部状态改变时改变它的行为。
• 观察者模式（Observer）：对象间的一对多的依赖关系。
• 备忘录模式（Memento）：在不破坏封装的前提下，保持对象的内部状态。
• 中介者模式（Mediator）：用一个中介对象来封装一系列的对象交互。
• 迭代器模式（Iterator）：一种遍历访问聚合对象中各个元素的方法，不暴露该对象的内部结构。
• 解释器模式（Interpreter）：给定一个语言，定义它的文法的一种表示，并定义一个解释器。
• 命令模式（Command）：将命令请求封装为一个对象，使得可以用不同的请求来进行参数化。
• 责任链模式（Chain Of Responsibilities）：将请求的发送者和接收者解耦，使的多个对象都有处理这个请求的机会。

2.2 设计模式详细介绍

2.2.1 创建型设计模式

通俗解释：创建型设计模式专注于如何实例化对象或相关对象组。

维基百科：在软件工程中，创建设计模式是处理对象创建机制的设计模式，试图以适合于该情况的方式创建对象。对象创建的基本形式可能导致设计问题或增加设计的复杂性。创建设计模式通过某种方式控制此对象创建来解决此问题。

[1] 单例模式

单例模式，它的定义就是确保某一个类只有一个实例，并且提供一个全局访问点。

单例模式具备典型的3个特点：1）只有一个实例。 2）自我实例化。 3）提供全局访问点。

因此当系统中只需要一个实例对象或者系统中只允许一个公共访问点，除了这个公共访问点外，不能通过其他访问点访问该实例时，可以使用单例模式。

单例模式的主要优点就是节约系统资源、提高了系统效率，同时也能够严格控制客户对它的访问。也许就是因为系统中只有一个实例，这样就导致了单例类的职责过重，违背了“单一职责原则”，同时也没有抽象类，所以扩展起来有一定的困难。其UML结构图如下：

[2] 工厂方法模式

作为抽象工厂模式的孪生兄弟，工厂方法模式定义了一个创建对象的接口，但由子类决定要实例化的类是哪一个。

工厂方法模式非常符合“开闭原则”，当需要增加一个新的产品时，我们只需要增加一个具体的产品类和与之对应的具体工厂即可，无须修改原有系统。同时在工厂方法模式中用户只需要知道生产产品的具体工厂即可，无须关系产品的创建过程，甚至连具体的产品类名称都不需要知道。虽然他很好的符合了“开闭原则”，但是由于每新增一个新产品时就需要增加两个类，这样势必会导致系统的复杂度增加。其UML结构图如下：

[3] 抽象工厂模式

所谓抽象工厂模式就是提供一个接口，用于创建相关或者依赖对象的家族，而不需要明确指定具体类。他允许客户端使用抽象的接口来创建一组相关的产品，而不需要关系实际产出的具体产品是什么。这样一来，客户就可以从具体的产品中被解耦。它的优点是隔离了具体类的生成，使得客户端不需要知道什么被创建了，而缺点就在于新增新的行为会比较麻烦，因为当添加一个新的产品对象时，需要更加需要更改接口及其下所有子类。其UML结构图如下：

[4] 建造者模式

对于建造者模式而言，它主要是将一个复杂对象的构建与表示分离，使得同样的构建过程可以创建不同的表示。适用于那些产品对象的内部结构比较复杂的情况。

建造者模式将复杂产品的构建过程封装分解在不同的方法中，使得创建过程非常清晰，能够让我们更加精确的控制复杂产品对象的创建过程，同时它隔离了复杂产品对象的创建和使用，使得相同的创建过程能够创建不同的产品。但是如果某个产品的内部结构过于复杂，将会导致整个系统变得非常庞大，不利于控制，同时若几个产品之间存在较大的差异，则不适用建造者模式，毕竟这个世界上存在相同点大的两个产品并不是很多，所以它的使用范围有限。其UML结构图如下：

[5] 原型模式

我们应用程序可能有某些对象的结构比较复杂，但我们又需要频繁的使用它们，如果这个时候我们来不断的新建这个对象势必会大大损耗系统内存，这个时候我们需要使用原型模式来对这个结构复杂又要频繁使用的对象进行克隆。所以原型模式就是用原型实例指定创建对象的种类，并且通过复制这些原型创建新的对象。

它主要应用于那些创建新对象成本过大的情况。主要优点是简化了新对象的创建过程，提高了效率，同时原型模式提供了简化的创建结构。其UML结构图如下：

原型模式包含如下角色：

• Prototype：抽象原型类
• ConcretePrototype：具体原型类
• Client：客户类

2.2.2 结构型设计模式

通俗解释：结构型设计模式大多关注对象组成，或者换句话说，实体如何相互使用。或者另一种解释是，它们有助于回答“如何构建软件组件”。

维基百科：在软件工程中，结构设计模式是通过识别实现实体之间关系的简单方法来简化设计的设计模式。

[1] 适配器模式

在应用程序中我们可能需要将两个不同接口的类进行通信，在不修改这两个类的前提下我们可能会需要某个中间件来完成这个衔接的过程，这个中间件就是适配器。所谓适配器模式就是将一个类的接口，转换成客户期望的另一个接口，它可以让原本两个不兼容的接口能够无缝完成对接。

作为中间件的适配器将目标类和适配者解耦，增加了类的透明性和可复用性。其UML结构图如下：

适配器模式包含如下角色：

• Target：目标抽象类
• Adapter：适配器类
• Adaptee：适配者类
• Client：客户类

[2] 桥接模式

如果说某个系统能够从多个角度来进行分类，且每一种分类都可能会变化，那么我们需要做的就是将这多个角度分离出来，使得他们能独立变化，减少他们之间的耦合，这个分离过程就使用了桥接模式。所谓桥接模式就是将抽象部分和实现部分隔离开，使得他们能够独立变化。

桥接模式将继承关系转化成关联关系，封装了变化，完成了解耦，减少了系统中类的数量，也减少了代码量。其UML结构图如下：

桥接模式包含如下角色：

• Abstraction：抽象类
• RefinedAbstraction：扩充抽象类
• Implementor：实现类接口
• ConcreteImplementor：具体实现类

[3] 组合模式

组合模式组合多个对象形成树形结构以表示“整体-部分”的结构层次。它定义了如何将容器对象和叶子对象进行递归组合，使得客户在使用的过程中无须进行区分，可以对他们进行一致的处理。在使用组合模式中需要注意一点也是组合模式最关键的地方：叶子对象和组合对象实现相同的接口，这就是组合模式能够将叶子节点和对象节点进行一致处理的原因。

虽然组合模式能够清晰地定义分层次的复杂对象，也使得增加新构件也更容易，但是这样就导致了系统的设计变得更加抽象，如果系统的业务规则比较复杂的话，使用组合模式就有一定的挑战了。其UML结构图如下：

组合模式包含如下角色：

• Component: 抽象构件
• Leaf: 叶子构件
• Composite: 容器构件
• Client: 客户类

[4] 装饰模式

我们可以通过继承和组合的方式来给一个对象添加行为，虽然使用继承能够很好拥有父类的行为，但是它存在几个缺陷：1）对象之间的关系复杂的话，系统变得复杂不利于维护。2）容易产生“类爆炸”现象。3）是静态的。在这里我们可以通过使用装饰者模式来解决这个问题。

装饰者模式，动态地将责任附加到对象上。若要扩展功能，装饰者提供了比继承更加有弹性的替代方案。虽然装饰者模式能够动态将责任附加到对象上，但是他会产生许多的细小对象，增加了系统的复杂度。其UML结构图如下：

装饰模式包含如下角色：

• Component: 抽象构件
• ConcreteComponent: 具体构件
• Decorator: 抽象装饰类
• ConcreteDecorator: 具体装饰类

[5] 外观模式

类与类之间的耦合越低，那么可复用性就越好，如果两个类不必彼此通信，那么就不要让这两个类发生直接的相互关系，如果需要调用里面的方法，可以通过第三者来转发调用。外观模式提供了一个统一的接口，用来访问子系统中的一群接口。它让一个应用程序中子系统间的相互依赖关系减少到了最少，它给子系统提供了一个简单、单一的屏障，客户通过这个屏障来与子系统进行通信。通过使用外观模式，实现了客户与子系统之间的松耦合。但是它违背了“开闭原则”，因为增加新的子系统可能需要修改外观类或客户端的源代码。其UML结构图如下：

外观模式包含如下角色：

• Facade: 外观角色
• SubSystem:子系统角色

[6] 亨元模式

在一个系统中对象会使得内存占用过多，特别是那些大量重复的对象，这就是对系统资源的极大浪费。享元模式对对象的重用提供了一种解决方案，它使用共享技术对相同或者相似对象实现重用。享元模式就是运行共享技术有效地支持大量细粒度对象的复用。系统使用少量对象，而且这些都比较相似，状态变化小，可以实现对象的多次复用。

这里有一点要注意：享元模式要求能够共享的对象必须是细粒度对象。享元模式通过共享技术使得系统中的对象个数大大减少了，同时享元模式使用了内部状态和外部状态，同时外部状态相对独立，不会影响到内部状态，所以享元模式能够使得享元对象在不同的环境下被共享。同时正是分为了内部状态和外部状态，享元模式会使得系统变得更加复杂，同时也会导致读取外部状态所消耗的时间过长。其UML结构图如下：

享元模式包含如下角色：

• Flyweight: 抽象享元类
• ConcreteFlyweight: 具体享元类
• UnsharedConcreteFlyweight: 非共享具体享元类
• FlyweightFactory: 享元工厂类

[7] 代理模式

代理模式就是给一个对象提供一个代理，并由代理对象控制对原对象的引用。它使得客户不能直接与真正的目标对象通信。代理对象是目标对象的代表，其他需要与这个目标对象打交道的操作都是和这个代理对象在交涉。

代理对象可以在客户端和目标对象之间起到中介的作用，这样起到了保护了目标对象的作用，同时也在一定程度上面减少了系统的耦合度。其UML结构图如下：

代理模式包含如下角色：

• Subject: 抽象主题角色
• Proxy: 代理主题角色
• RealSubject: 真实主题角色

2.2.3 行为型设计模式

通俗解释：行为型设计模式关注对象之间的职责分配。它们与结构型设计模式的不同之处在于，它们不仅指定了结构，还概述了它们之间的消息传递/通信模式。或者换句话说，他们协助回答“如何在软件组件中运行行为”。

维基百科：在软件工程中，行为设计模式是识别对象之间的共同通信模式并实现这些模式的设计模式。通过这样做，这些模式增加了执行该通信的灵活性。

[1] 访问者模式

在软件开发中我们可能会对同一个对象有不同的处理，如果我们都做分别的处理，将会产生灾难性的错误。对于这种问题，访问者模式提供了比较好的解决方案。访问者模式即表示一个作用于某对象结构中的各元素的操作，它使我们可以在不改变各元素的类的前提下定义作用于这些元素的新操作。

访问者模式的目的是封装一些施加于某种数据结构元素之上的操作，一旦这些操作需要修改的话，接受这个操作的数据结构可以保持不变。为不同类型的元素提供多种访问操作方式，且可以在不修改原有系统的情况下增加新的操作方式。同时我们还需要明确一点那就是访问者模式是适用于那些数据结构比较稳定的，因为它是将数据的操作与数据结构进行分离了，如果某个系统的数据结构相对稳定，但是操作算法易于变化的话，就比较适用适用访问者模式，因为访问者模式使得算法操作的增加变得比较简单了。其UML结构图如下：

访问者模式包含如下角色：

• Vistor: 抽象访问者
• ConcreteVisitor: 具体访问者
• Element: 抽象元素
• ConcreteElement: 具体元素
• ObjectStructure: 对象结构

[2] 模板模式

有些时候我们做某几件事情的步骤都差不多，仅有那么一小点的不同，如果我们都将这些步骤都逐一去做的话，费时费力不讨好。所以我们可以将这些步骤分解、封装起来，然后利用继承的方式来继承即可，不同的可以自己重写实现，这就是模板方法模式提供的解决方案。

所谓模板方法模式就是在一个方法中定义一个算法的骨架，而将一些步骤延迟到子类中。模板方法使得子类可以在不改变算法结构的情况下，重新定义算法中的某些步骤。

在模板方法模式中，我们可以将相同部分的代码放在父类中，而将不同的代码放入不同的子类中。也就是说我们需要声明一个抽象的父类，将部分逻辑以具体方法以及具体构造函数的形式实现，然后声明一些抽象方法让子类来实现剩余的逻辑，不同的子类可以以不同的方式来实现这些逻辑。所以模板模式的模板其实就是一个普通的方法，只不过这个方法是将算法实现的步骤封装起来的。其UML结构图如下：

模板方法模式包含如下角色：

• AbstractClass: 抽象类
• ConcreteClass: 具体子类

[3] 策略模式

我们有很多中方法来实现一个功能，但是我们需要一种简单、高效的方式来实现它，使得系统能够非常灵活，这就是策略模式。所谓策略模式就是定义了算法族，分别封装起来，让他们之前可以互相转换。

在策略模式中，它将这些解决问题的方法定义成一个算法群，每一个方法都对应着一个具体的算法，这里的一个算法我就称之为一个策略。虽然策略模式定义了算法，但是它并不提供算法的选择，即什么算法对于什么问题最合适这是策略模式所不关心的，所以对于策略的选择还是要客户端来做。客户必须要清楚的知道每个算法之间的区别和在什么时候什么地方使用什么策略是最合适的，这样就增加客户端的负担。

同时策略模式也非常完美的符合了“开闭原则”，用户可以在不修改原有系统的基础上选择算法或行为，也可以灵活地增加新的算法或行为。但是一个策略对应一个类将会是系统产生很多的策略类。其UML结构图如下：

策略模式包含如下角色：

• Context: 环境类
• Strategy: 抽象策略类
• ConcreteStrategy: 具体策略类

[4] 状态模式

在很多情况下我们对象的行为依赖于它的一个或者多个变化的属性，这些可变的属性我们称之为状态，也就是说行为依赖状态，即当该对象因为在外部的互动而导致它的状态发生变化，从而它的行为也会做出相应的变化。对于这种情况，我们是不能用行为来控制状态的变化，而应该站在状态的角度来思考行为，即是什么状态就要做出什么样的行为，这个就是状态模式。

所谓状态模式就是允许对象在内部状态发生改变时改变它的行为，对象看起来好像修改了它的类。在状态模式中我们可以减少大块的if…else语句，它是允许态转换逻辑与状态对象合成一体，但是减少if…else语句的代价就是会换来大量的类，所以状态模式势必会增加系统中类或者对象的个数。

同时状态模式是将所有与某个状态有关的行为放到一个类中，并且可以方便地增加新的状态，只需要改变对象状态即可改变对象的行为。但是这样就会导致系统的结构和实现都会比较复杂，如果使用不当就会导致程序的结构和代码混乱，不利于维护。其UML结构图如下：

状态模式包含如下角色：

• Context: 环境类
• State: 抽象状态类
• ConcreteState: 具体状态类

[5] 观察者模式

观察者模式定义了对象之间的一对多依赖关系，这样一来，当一个对象改变状态时，它的所有依赖者都会收到通知并且自动更新。

在这里，发生改变的对象称之为观察目标，而被通知的对象称之为观察者。一个观察目标可以对应多个观察者，而且这些观察者之间没有相互联系，所以么可以根据需要增加和删除观察者，使得系统更易于扩展。所以观察者提供了一种对象设计，让主题和观察者之间以松耦合的方式结合。其UML结构图如下：

观察者模式包含如下角色：

• Subject: 目标
• ConcreteSubject: 具体目标
• Observer: 观察者
• ConcreteObserver: 具体观察者

[6] 备忘录模式

备忘录模式给我们的软件提供后悔药的机制，通过它可以使系统恢复到某一特定的历史状态。

所谓备忘录模式就是在不破坏封装的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，这样可以在以后将对象恢复到原先保存的状态。它实现了对信息的封装，使得客户不需要关心状态保存的细节。保存就要消耗资源，所以备忘录模式的缺点就在于消耗资源。如果类的成员变量过多，势必会占用比较大的资源，而且每一次保存都会消耗一定的内存。其UML结构图如下：

备忘录模式包含如下角色：

• Originator: 原发器
• Memento: 备忘录
• Caretaker: 负责人

[7] 中介者模式

在我们的系统中有时候会存在着对象与对象之间存在着很强、复杂的关联关系，如果让他们之间有直接的联系的话，必定会导致整个系统变得非常复杂，而且可扩展性很差。在前面我们就知道如果两个类之间没有不必彼此通信，我们就不应该让他们有直接的关联关系，如果实在是需要通信的话，我们可以通过第三者来转发他们的请求。同样，这里我们利用中介者来解决这个问题。

所谓中介者模式就是用一个中介对象来封装一系列的对象交互，中介者使各对象不需要显式地相互引用，从而使其耦合松散，而且可以独立地改变它们之间的交互。在中介者模式中，中介对象用来封装对象之间的关系，各个对象可以不需要知道具体的信息通过中介者对象就可以实现相互通信。它减少了对象之间的互相关系，提供了系统可复用性，简化了系统的结构。

在中介者模式中，各个对象不需要互相知道了解，他们只需要知道中介者对象即可，但是中介者对象就必须要知道所有的对象和他们之间的关联关系，正是因为这样就导致了中介者对象的结构过于复杂，承担了过多的职责，同时它也是整个系统的核心所在，它有问题将会导致整个系统的问题。所以如果在系统的设计过程中如果出现“多对多”的复杂关系群时，千万别急着使用中介者模式，而是要仔细思考是不是您设计的系统存在问题。其UML结构图如下：

中介者模式包含如下角色：

• Mediator: 抽象中介者
• ConcreteMediator: 具体中介者
• Colleague: 抽象同事类
• ConcreteColleague: 具体同事类

[8] 迭代器模式

能够游走于集合内的每一个元素，同时还可以提供多种不同的遍历方式，这就是迭代器模式的设计动机。在实际的开发过程中，我们可能会需要根据不同的需求以不同的方式来遍历整个对象，但是我们又不希望在聚合对象的抽象接口中充斥着各种不同的遍历操作，于是就希望有某个东西能够以多种不同的方式来遍历一个聚合对象，这时迭代器模式出现了。

所谓迭代器模式就是提供一种方法顺序访问一个聚合对象中的各个元素，而不是暴露其内部的表示。迭代器模式是将迭代元素的责任交给迭代器，而不是聚合对象，我们甚至在不需要知道该聚合对象的内部结构就可以实现该聚合对象的迭代。通过迭代器模式，使得聚合对象的结构更加简单，它不需要关注它元素的遍历，只需要专注它应该专注的事情，这样就更加符合单一职责原则了。其UML结构图如下：

迭代器模式包含如下角色：

• Iterator: 抽象迭代器
• ConcreteIterator: 具体迭代器
• Aggregate: 抽象聚合类
• ConcreteAggregate: 具体聚合类

[9] 解释器模式

所谓解释器模式就是定义语言的文法，并且建立一个解释器来解释该语言中的句子。解释器模式描述了如何构成一个简单的语言解释器，主要应用在使用面向对象语言开发的编译器中。它描述了如何为简单的语言定义一个文法，如何在该语言中表示一个句子，以及如何解释这些句子。其UML结构图如下：

解释器模式包含如下角色：

• AbstractExpression: 抽象表达式
• TerminalExpression: 终结符表达式
• NonterminalExpression: 非终结符表达式
• Context: 环境类
• Client: 客户类

[10] 命令模式

有些时候我们想对某个对象发送一个请求，我们并不需要知道该请求的具体接收者是谁、具体的处理过程是如何的，而我们只知道在程序运行中指定具体的请求接收者即可，对于这样将请求封装成对象的模式我们称之为命令模式。所谓命令模式将请求封装成对象，以便使用不同的请求、队列或者日志来参数化其他对象，同时命令模式支持可撤销的操作。

命令模式可以将请求的发送者和接收者之间实现完全的解耦，发送者和接收者之间没有直接的联系，发送者只需要知道如何发送请求命令即可，其余的可以一概不管，甚至命令是否成功都无需关心。同时我们可以非常方便的增加新的命令，但是可能会因此导致系统中会存在过多的具体命令类。其UML结构图如下：

命令模式包含如下角色：

• Command: 抽象命令类
• ConcreteCommand: 具体命令类
• Invoker: 调用者
• Receiver: 接收者
• Client:客户类

[11] 责任链模式

责任链模式描述的是请求如何沿着对象所组成的链进行传递的。它将对象组成一条链，发送者将请求发给链的第一个接收者，并且沿着这条链传递，直到有一个对象来处理它或者直到最后也没有对象处理而留在链末尾端。

避免请求发送者与接收者耦合在一起，让多个对象都有可能接收请求，将这些对象连接成一条链，并且沿着这条链传递请求，直到有对象处理它为止，这就是责任链模式。在责任链模式中，使得每一个对象都有可能来处理请求，从而实现了请求的发送者和接收者之间的解耦。同时责任链模式简化了对象的结构，它使得每个对象都只需要引用它的后继者即可，而不必了解整条链，这样既提高了系统的灵活性也使得增加新的请求处理类也比较方便。但是在责任链中我们不能保证所有的请求都能够被处理，而且不利于观察运行时特征。其UML结构图如下：

责任链模式包含如下角色：

• Handler: 抽象处理者
• ConcreteHandler: 具体处理者
• Client: 客户类

2.3 开发原则概述

在程序设计时，我们应该将程序功能最小化，每个类只干一件事。若有类似功能基础之上添加新功能，则要合理使用继承。对于多方法的调用，要会运用接口，同时合理设置接口功能与数量。最后类与类之间做到低耦合高内聚。

以下是七大开发原则：

设计原则	一句话归纳	目的
开闭原则	对扩展开放，对修改关闭	降低维护带来的新风险
依赖倒置原则	高层不应该依赖低层，要面向接口编程	更利于代码结构的升级扩展
单一职责原则	一个类只干一件事，实现类要单一	便于理解，提高代码的可读性
接口隔离原则	一个接口只干一件事，接口要精简单一	功能解耦，高聚合、低耦合
迪米特法则	不该知道的不要知道，一个类应该保持对其它对象最少的了解，降低耦合度	只和朋友交流，不和陌生人说话，减少代码臃肿
里氏替换原则	不要破坏继承体系，子类重写方法功能发生改变，不应该影响父类方法的含义	防止继承泛滥
合成复用原则	尽量使用组合或者聚合关系实现代码复用，少使用继承	降低代码耦合

实际上，这些原则的目的只有一个：降低对象之间的耦合，增加程序的可复用性、可扩展性和可维护性。

2.4 开发原则详细介绍

2.4.1 开闭原则

Open Closed Principle，OCP：软件实体应当对扩展开放，对修改关闭。即, 当应用的需求改变时，在不修改软件实体的源代码或者二进制代码的前提下，可以扩展模块的功能，使其满足新的需求。作用如下：

• 对软件测试的影响：测试时只需要对扩展的代码进行测试就可以了，因为原有的测试代码仍然能够正常运行。
• 提高代码的可复用性：粒度越小，被复用的可能性就越大；在面向对象的程序设计中，根据原子和抽象编程可以提高代码的可复用性。
• 提高软件的可维护性：稳定性高和延续性强，从而易于扩展和维护。

2.4.2 里氏替换原则

Liskov Substitution Principle，LSP：继承必须确保基类所拥有的性质在子类中仍然成立。即, 子类可以扩展父类的功能，但不能改变父类原有的功能。作用如下：

• 是实现开闭原则的重要方式之一。
• 克服了继承中重写父类造成的可复用性变差的缺点。
• 类的扩展不会给已有的系统引入新的错误，降低了代码出错的可能性。

2.4.3 依赖倒置原则

Dependence Inversion Principle，DIP：要面向接口编程，不要面向实现编程。即高层模块不应该依赖低层模块，两者都应该依赖其抽象；抽象不应该依赖细节，细节应该依赖抽象。作用如下：

• 可以降低类间的耦合性。
• 可以减少并行开发引起的风险。
• 可以提高代码的可读性和可维护性。

2.4.4 单一职责原则

Single Responsibility Principle，SRP：单一职责原则规定一个类应该有且仅有一个引起它变化的原因，否则类应该被拆分。如果一个对象承担了太多的职责，至少存在以下两个缺点：

• 一个职责的变化可能会削弱或者抑制这个类实现其他职责的能力；
• 当客户端需要该对象的某一个职责时，不得不将其他不需要的职责全都包含进来，从而造成冗余代码或代码的浪费。

遵循该原则有以下作用：

• 降低类的复杂度。一个类只负责一项职责，其逻辑肯定要比负责多项职责简单得多。
• 提高类的可读性。复杂性降低，自然其可读性会提高。
• 提高系统的可维护性。可读性提高，那自然更容易维护了。
• 变更引起的风险降低。变更是必然的，如果单一职责原则遵守得好，当修改一个功能时，可以显著降低对其他功能的影响。

2.4.5 接口隔离原则

Interface Segregation Principle，ISP：客户端不应该被迫依赖于它不使用的方法，一个类对另一个类的依赖应该建立在最小的接口上。

与单一职责原则的区别：

• 单一职责原则注重的是职责，而接口隔离原则注重的是对接口依赖的隔离。
• 单一职责原则主要是约束类，它针对的是程序中的实现和细节；接口隔离原则主要约束接口，主要针对抽象和程序整体框架的构建。

遵循该原则有以下作用：

• 将臃肿庞大的接口分解为多个粒度小的接口，可以预防外来变更的扩散，提高系统的灵活性和可维护性。
• 接口隔离提高了系统的内聚性，减少了对外交互，降低了系统的耦合性。
• 使用多个专门的接口还能够体现对象的层次，因为可以通过接口的继承，实现对总接口的定义。
• 能减少项目工程中的代码冗余。过大的大接口里面通常放置许多不用的方法，当实现这个接口的时候，被迫设计冗余的代码。

2.4.6 迪米特法则

Law of Demeter，LoD, 又叫作最少知识原则，如果两个软件实体无须直接通信，那么就不应当发生直接的相互调用，可以通过第三方转发该调用。其目的是降低类之间的耦合度，提高模块的相对独立性。作用如下：

• 降低了类之间的耦合度，提高了模块的相对独立性。
• 由于亲合度降低，从而提高了类的可复用率和系统的扩展性。

2.4.7 合成复用原则

Composite Reuse Principle，CRP, 又叫组合/聚合复用原则，在软件复用时，要尽量先使用组合或者聚合等关联关系来实现，其次才考虑使用继承关系来实现。作用如下：

• 通常类的复用分为继承复用和合成复用两种，继承复用虽然有简单和易实现的优点，但它也存在以下缺点:
  • 继承复用破坏了类的封装性。因为继承会将父类的实现细节暴露给子类，父类对子类是透明的，所以这种复用又称为“白箱”复用。
  • 子类与父类的耦合度高。父类的实现的任何改变都会导致子类的实现发生变化，这不利于类的扩展与
  • 它限制了复用的灵活性。从父类继承而来的实现是静态的，在编译时已经定义，所以在运行时不可能发生变化。
• 采用组合或聚合复用时，可以将已有对象纳入新对象中，使之成为新对象的一部分，新对象可以调用已有对象的功能，它有以下优点:
  • 它维持了类的封装性。因为成分对象的内部细节是新对象看不见的，所以这种复用又称为“黑箱”复用。
  • 新旧类之间的耦合度低。这种复用所需的依赖较少，新对象存取成分对象的唯一方法是通过成分对象的接口。
  • 复用的灵活性高。这种复用可以在运行时动态进行，新对象可以动态地引用与成分对象类型相同的对象。

3. Java8函数式编程Lambda表达式

3.1 Lambda表达式基本介绍

3.1.1 简介

Lambda表达式是一个匿名函数，Lambda表达式基于数学中的λ得名。编程中提到的Lambda表达式，通常是指在需要一个函数，但是又不想费神去命名一个函数的场合下使用，也就是指匿名函数。

如果接口只有一个方法，这时使用匿名内部类时，代码看上去既不清晰也不简洁。在这种情况下，你会希望将函数作为参数传递进去，来让代码看起来更加简洁。Lambda表达式可以实现这种需求，将函数作为方法参数或者将代码作为数据，可以使单方法接口更加简洁。

Java8 中的 Lambda 表达式通常使用 (arguments) -> (expression) 语法书写。以下是 Lambda 表达式的重要特征：

• 可选参数：Lambda 表达式可以有零个或多个参数。
• 可选类型声明：不需要声明参数类型，编译器可以统一识别参数值。
• 可选的参数圆括号：一个参数无需定义圆括号，但多个参数需要定义圆括号。
• 可选的大括号：如果主体包含了一个语句，就不需要使用大括号。
• 可选的返回关键字：如果主体只有一个表达式返回值则编译器会自动返回值，大括号需要指定明表达式返回了一个数值。

Lambda表达式是不是语法糖的说明：

• Labmda表达式不是匿名内部类的语法糖，但是它也是一个语法糖，实现方式其实是依赖了几个JVM底层提供的lambda相关API。
• 如果是匿名内部类的语法糖，那么编译之后会有两个class文件，但是包含Labmda表达式的类编译后只有一个文件。

3.1.2 通俗理解

我们知道，对于一个Java变量，我们可以赋给其一个“值”。

如果你想把“一块代码*赋给一个Java变量，应该怎么做呢？

比如，我想把右边那块代码，赋给一个叫做aBlockOfCode的Java变量：

在Java 8之前，这个是做不到的。但是Java 8问世之后，利用Lambda特性，就可以做到了。

当然，这个并不是一个很简洁的写法。所以，为了使这个赋值操作更加elegant, 我们可以移除一些没用的声明。

这样，我们就成功的非常优雅的把“一块代码”赋给了一个变量。而“这块代码”，或者说“这个被赋给一个变量的函数”，就是一个Lambda表达式。

但是这里仍然有一个问题，就是变量aBlockOfCode的类型应该是什么？

在Java 8里面，所有的Lambda的类型都是一个接口，而Lambda表达式本身，也就是”那段代码“，需要是这个接口的实现。这是理解Lambda的一个关键所在，简而言之就是，Lambda表达式本身就是一个接口的实现。直接这样说可能还是有点让人困扰，我们继续看看例子。我们给上面的aBlockOfCode加上一个类型：

这种只有一个接口函数需要被实现的接口类型，我们叫它“函数式接口”。为了避免后来的人在这个接口中增加接口函数导致其有多个接口函数需要被实现，变成"非函数接口”，我们可以在这个上面加上一个声明@FunctionalInterface, 这样别人就无法在里面添加新的接口函数了：

这样，我们就得到了一个完整的Lambda表达式声明：

3.1.3 作用

最直观的作用就是使得代码变得异常简洁。我们可以对比一下Lambda表达式和传统的Java对同一个接口的实现：

这两种写法本质上是等价的。但是显然，Java 8中的写法更加优雅简洁。并且，由于Lambda可以直接赋值给一个变量，我们就可以直接把Lambda作为参数传给函数，而传统的Java必须有明确的接口实现的定义，初始化才行。

3.1.4 语法规则

Lambda 表达式在 Java 语言中引入了一个新的语法元素和操作符。这个操作符为 “->”，该操作符被称 为 Lambda 操作符或箭头操作符。

它将 Lambda 分为两个部分：

• 左侧：指定了 Lambda 表达式需要的所有参数
• 右侧：指定了 Lambda 体，即 Lambda 表达式要执行的功能。

Lambda 表达式的参数列表的数据类型可以省略不写，因为JVM编译器通过上下文推断出，数据类型，即“类型推断”。

1）语法格式一：无参，无返回值，Lambda 体只需一条语句。示例：

Runnable r1 = () -> System.out.println("Hello Lambda!");

2）语法格式二：Lambda 需要一个参数。示例：

Consumer<String> con =（x）-> System.out.println(x);

Lambda 只需要一个参数时，参数的小括号可以省略。示例：

Consumer<String> con = x -> System.out.println(x);

3）语法格式三：Lambda 需要两个参数，并且有返回值。示例：

Comparator<Integer> com = (x, y) -> {
   System.out.println("函数式接口");
   return Integer.compare(x, y);
};

当 Lambda 体只有一条语句时，return 与大括号可以省略。示例：

Comparator<Integer> com = (x, y) -> Integer.compare(x, y);

3.2 Lambda表达式的使用

使用Lambda表达式创建线程的时候，并不需要关心接口名，方法名，参数名。只需要关注它的参数类型，参数个数，返回值即可。

3.2.1 实现Runnable

开始使用Java 8时，首先做的就是使用Lambda表达式替换匿名类，而实现Runnable接口是匿名类的最好示例。看一下Java 8之前的Runnable实现方法，需要4行代码，而使用lambda表达式只需要一行代码，用() -> {}代码块替代了整个匿名类。

        // Java 8之前：
        new Thread(new Runnable() {
            @Override
            public void run() {
            System.out.println("Before Java8, too much code for too little to do");
            }
        }).start();

        // Java 8方式：
        new Thread( () -> System.out.println("In Java8, Lambda expression rocks !!") ).start();

3.2.2 遍历列表

列表现在有了一个 forEach() 方法，它可以迭代所有对象，并将你的Lambda代码应用在其中。

        // Java 8之前：
        List<String> features = Arrays.asList("Lambdas", "Default Method", "Stream API", "Date and Time API");
        for (String feature : features) {
            System.out.println(feature);
        }

        // Java 8之后：
        List<String> features = Arrays.asList("Lambdas", "Default Method", "Stream API", "Date and Time API");
        features.forEach(System.out::println); // 即相当于 features.forEach(n -> System.out.println(n));

使用 Java 8 的方法引用更方便，方法引用由::双冒号操作符标示，双冒号（::）操作符是 Java 中的方法引用。当们使用一个方法的引用时，目标引用放在 :: 之前，目标引用提供的方法名称放在 :: 之后，即目标引用::方法。

3.2.3 函数式接口Predicate

除了在语言层面支持函数式编程风格，Java 8也添加了一个包，叫做 java.util.function。它包含了很多类，用来支持Java的函数式编程。其中一个便是Predicate，使用 java.util.function.Predicate 函数式接口以及lambda表达式，可以向 API 方法添加逻辑，用更少的代码支持更多的动态行为。下面是Java 8 Predicate 的例子，展示了过滤集合数据的多种常用方法，Predicate接口非常适用于做过滤。

    // Java 8之前
    public static void filter(List<String> names, Predicate condition) {
        for(String name: names)  {
            if(condition.test(name)) {
                System.out.println(name + " ");
            }
        }
    }

    // Java 8之后
    public static void filter(List<String> names, Predicate condition) {
        names.stream().filter((name) -> (condition.test(name))).forEach((name) -> {
            System.out.println(name + " ");
        });
    }
    
    public static void main(String[] args){
        List<String> languages = Arrays.asList("Java", "Scala", "C++", "Haskell", "Lisp");
      
        System.out.println("=== Languages which starts with J :");
        filter(languages, (str)->str.toString().startsWith("J"));
      
        System.out.println("=== Languages which ends with a ");
        filter(languages, (str)->str.toString().endsWith("a"));

        System.out.println("=== Print all languages :");
        filter(languages, (str)->true);

        System.out.println("=== Print no language : ");
        filter(languages, (str)->false);

        System.out.println("=== Print language whose length greater than 4:");
        filter(languages, (str)->str.toString().length() > 4);
    }

3.2.4 Map 和 Reduce

[1] Map

本例介绍最广为人知的函数式编程概念Map，它允许你将对象进行转换。例如在本例中，我们将 costBeforeTax 列表的每个元素转换成为税后的值。将Lambda表达式传到 map() 方法，后者将其应用到流中的每一个元素，然后用 forEach() 将列表元素打印出来。使用流API的收集器类，可以得到所有含税的开销。有 toList() 这样的方法将 map 或任何其他操作的结果合并起来。由于收集器在流上做终端操作，因此之后便不能重用流了。你甚至可以用流API的 reduce() 方法将所有数字合成一个，下一个例子将会讲到。

        // 不使用lambda表达式 为每个订单加上12%的税
        List<Integer> costBeforeTax = Arrays.asList(100, 200, 300, 400, 500);
        for (Integer cost : costBeforeTax) {
            double price = cost + .12*cost;
            System.out.println(price);
        }

        // 使用lambda表达式 为每个订单加上12%的税
        List<Integer> costBeforeTax = Arrays.asList(100, 200, 300, 400, 500);
        costBeforeTax.stream().map((cost) -> cost + .12*cost).forEach(System.out::println);

[2] Reduce

在上个例子中，可以看到map将集合类（例如列表）元素进行转换的。还有一个 reduce() 函数可以将所有值合并成一个。Map和Reduce操作是函数式编程的核心操作，因为其功能，reduce 又被称为折叠操作。另外，reduce 并不是一个新的操作，你有可能已经在使用它，在SQL中类似 sum()、avg() 或者 count() 的聚集函数，实际上就是 reduce 操作，因为它们接收多个值并返回一个值。流API定义的 reduceh() 函数可以接受Lambda表达式，并对所有值进行合并。IntStream这样的类有类似 average()、count()、sum()的内建方法来做 reduce 操作，也有mapToLong()、mapToDouble() 方法来做转换。这并不会限制你，你可以用内建方法，也可以自己定义。在这个Java 8的Map Reduce示例里，我们首先对所有价格应用 12% 的VAT，然后用 reduce() 方法计算总和。

        // 不使用lambda表达式 为每个订单加上12%的税并求和
        List<Integer> costBeforeTax = Arrays.asList(100, 200, 300, 400, 500);
        double total = 0;
        for (Integer cost : costBeforeTax) {
            double price = cost + .12*cost;
            total = total + price;
        }
        System.out.println("Total : " + total);

        // 使用lambda表达式 为每个订单加上12%的税
        List<Integer> costBeforeTax = Arrays.asList(100, 200, 300, 400, 500);
        double bill = costBeforeTax.stream().map((cost) -> cost + .12*cost).reduce((sum, cost) -> sum + cost).get();
        System.out.println("Total : " + bill);

3.2.5 过滤创建一个 String 列表

过滤是 Java 开发者在大规模集合上的一个常用操作，而现在使用 Lambda 表达式和流 API 过滤大规模数据集合是非常的简单。流提供了一个 filter() 方法，接受一个 Predicate 对象，即可以传入一个 lambda 表达式作为过滤逻辑。下面的例子是用 Lambda 表达式过滤 Java 集合。

        // 使用lambda表达式 过滤字符串列表中每个字符串长度大于2的元素
        List<String> strList = Arrays.asList("abc", "bcd", "defg", "jk");
        List<String> filtered = strList.stream().filter(x -> x.length()> 2).collect(Collectors.toList());
        System.out.printf("Original List : %s, filtered list : %s %n", strList, filtered);

3.2.6 对列表的每个元素应用函数

如果需要对列表的每个元素使用某个函数，例如逐一乘以某个数、除以某个数或者做其它操作。这些操作都很适合用 map() 方法，可以将转换逻辑以lambda表达式的形式放在 map() 方法里，就可以对集合的各个元素进行转换了，如下所示。

        // 使用lambda表达式 将字符串换成大写并用逗号链接起来
        List<String> list = Arrays.asList("USA", "Japan", "France", "Germany", "Italy", "U.K.","Canada");
        String g7Countries = list.stream().map(String::toUpperCase).collect(Collectors.joining(", "));
        System.out.println(g7Countries);

3.2.7 复制不同的值，创建一个子列表

本例展示了如何利用流的 distinct() 方法来对集合进行去重。

        // 使用lambda表达式 用所有不同的数字创建一个平方列表
        List<Integer> numbers = Arrays.asList(9, 10, 3, 4, 7, 3, 4);
        List<Integer> distinct = numbers.stream().map( i -> i*i).distinct().collect(Collectors.toList());
        System.out.printf("Original List : %s,  Square Without duplicates : %s %n", numbers, distinct);

3.2.8 计算集合元素的统计值

IntStream、LongStream 和 DoubleStream 等流的类中，有个非常有用的方法叫 summaryStatistics() 。可以返回 IntSummaryStatistics、LongSummaryStatistics 或者 DoubleSummaryStatistics，描述流中元素的各种摘要数据。在本例中，我们用这个方法来计算列表的最大值和最小值，它也有 getSum() 和 getAverage() 方法来获得列表的所有元素的总和及平均值。

        // 使用lambda表达式 获取数字的个数、最小值、最大值、总和以及平均值
        List<Integer> primes = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29);
        IntSummaryStatistics stats = primes.stream().mapToInt((x) -> x).summaryStatistics();
        System.out.println("Highest prime number in List : " + stats.getMax());
        System.out.println("Lowest prime number in List : " + stats.getMin());
        System.out.println("Sum of all prime numbers : " + stats.getSum());
        System.out.println("Average of all prime numbers : " + stats.getAverage());

3.3 Stream对象的使用

Stream对象提供多个非常有用的方法，这些方法可以分成两类：

• 中间操作：将原始的Stream转换成另外一个Stream；如filter返回的是过滤后的Stream。
• 终端操作：产生的是一个结果或者其它的复合操作；如count或者forEach操作。

3.3.1 Stream对象的中间操作

方法	说明
sequential	返回一个相等的串行的Stream对象，如果原Stream对象己经是串行就可能会返回原对象
parallel	返回一个相等的并行的Stream对象，如果原Stream对象己经是并行的就会返回原对象
unordered	返回一个不关心顺序的Stream对象，如果原对象己经是这类型的对象就会返回原对象
onClose	返回一个相等的Steam对象，同时新的Stream对象在执行Close方法时会调用传入的Runnable对象
close	关闭Stream对象
filter	元素过滤:对Stream对象按指定的Predicate进行过滤，返回的Stream对象中仅包含未被过滤的元素
map	元素一对一转换：使用传入的Function对象对Stream中的所有元素进行处理，返回的Stream对象中的元素为原元素处理后的结果
mapToInt	元素一对一转换：将原Stream中的使用传入的IntFunction加工后返回一个IntStream对象
flatMap	元素一对多转换：对原Stream中的所有元素进行操作,每个元素会有一个或者多个结果,然后将返回的所有元素组合成一个统一的Stream并返回;
distinct	去重：返回一个去重后的Stream对象
sorted	排序：返回排序后的Stream对象
peek	使用传入的Consumer对象对所有元素进行消费后，返回一个新的包含所有原来元素的Stream对象
limit	获取有限个元素组成新的Stream对象返回
skip	抛弃前指定个元素后使用剩下的元素组成新的Stream返回
takeWhile	如果Stream是有序的，那么返回最长命中序列（符合传入的Predicate的最长命中序列）组成的Stream；如果是无序的，那么返回的是所有符合传入的Predicate的元素序列组成的Stream
dropWhile	与takeWhile相反，如果是有序的，返回除最长命中序列外的所有元素组成的Stream；如果是无序的，返回所有未命中的元素组成的Stream

3.3.2 Stream对象的终端操作

方法	说明
iterator	返回Stream中所有对象的迭代器
spliterator	返回对所有对象进行的spliterator对象
forEach	对所有元素进行迭代处理，无返回值
forEachOrdered	按Stream的Encounter所决定的序列进行迭代处理，无返回值
toArray	返回所有元素的数组
reduce	使用一个初始化的值，与Stream中的元素一一做传入的二合运算后返回最终的值。每与一个元素做运算后的结果，再与下一个元素做运算，它不保证会按序列执行整个过程
collect	根据传入参数做相关汇聚计算
min	返回所有元素中最小值的Optional对象；如果Stream中无任何元素，那么返回的Optional对象为Empty
max	返回所有元素中最大值的Optional对象；如果Stream中无任何元素，那么返回的Optional对象为Empty
count	所有元素个数
anyMatch	只要其中有一个元素满足传入的Predicate时返回True，否则返回False
allMatch	所有元素均满足传入的Predicate时返回True，否则False
noneMatch	所有元素均不满足传入的Predicate时返回True，否则False
findFirst	返回第一个元素的Optioanl对象，如果无元素返回的是空的Optional；如果Stream是无序的，那么任何元素都可能被返回
findAny	返回任意一个元素的Optional对象，如果无元素返回的是空的Optioanl
isParallel	判断是否当前Stream对象是并行的

4. 参考资料

[1] 这几种常见的数据结构，你必须知道 from 稀土掘金 (opens new window)

[2] 八种常见数据结构介绍 from CSDN (opens new window)

[3] 使用Python实现常见的数据结构之原理讲解 from 博客园 (opens new window)

[4] 使用Python实现常见的数据结构 from 博客园 (opens new window)

[5] 常见数据结构与算法的Python实现及学习笔记 from Github (opens new window)

[6] 所有算法都用 Python 实现 from Github (opens new window)

[7] 数据结构和算法介绍 from 智能后端和架构 (opens new window)

[8] 常见的数据结构 from 盖若 (opens new window)

[9] 用Python实现数据结构和算法原理的代码 from Github (opens new window)

[10] 深入数据结构：“堆” from 稀土掘金 (opens new window)

[11] 图解数据结构js篇-栈结构（Stack）from 稀土掘金 (opens new window)

[12] 数据结构与算法(十一)——图（Graph）from xeh的学习笔记 (opens new window)

[13] 算法数据结构：散列表 from 稀土掘金 (opens new window)

[14] 用一个测试类简化排序算法时间复杂度的研究 from 博客园 (opens new window)

[15] 十大经典排序算法最强总结（含JAVA代码实现）from 博客园 (opens new window)

[16] 烂熟于心的基础排序算法 from Chancel's Blog (opens new window)

[17] JAVA设计模式总结之23种设计模式 from 博客园 (opens new window)

[18] Java 23种设计模式全归纳 from Github (opens new window)

[19] Java常用设计模式 from refactoringguru (opens new window)

[20] 设计模式超简单的解释 from Github (opens new window)

[21] 如何学习设计模式 from CSDN (opens new window)

[22] 用 Java 实现的设计模式 from Github (opens new window)

[23] 软件设计模式——七大设计原则 from 普通人 (opens new window)

[24] Lambda 表达式有何用处？如何使用？from 知乎 (opens new window)

[25] Java 8 - 函数编程(lambda表达式) from 全栈技术体系 (opens new window)

[26] Java 8 Lambda表达式介绍（一） from cnblogs (opens new window)

[27] Java 8 Lambda表达式介绍（二） from cnblogs (opens new window)

[28] Java 8 Lambda 表达式简介 from DEV (opens new window)

[29] Java 8 Lambda表达式快速入门 from GIthub (opens new window)

[30] Java SE 8：Lambda 快速入门 from 官方文档 (opens new window)

[31] Java 8：一文掌握 Lambda 表达式 from 知乎 (opens new window)

[32] Lambda 表达式使用例子 from CSDN (opens new window)