算法简述
- 归并排序，是创建在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个典型应用，且各层分治递归可以同时独立进行.
- 归并排序可以采用递归和迭代两种方式来实现
- 算法复杂度
- 比较次数介于½nlgn与nlgn之间
- 赋值操作次数是2nlgn
- 空间复杂度为O(n)
归并排序-递归实现
算法描述
- 将长度为n的序列进行拆分，得到lg(n)+1级(递归栈深度)的子序列，最后一级共n个子序列，每个序列一个元素
- 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
- 将上述序列再次递归，形成floor(n/4)个子序列，每个序列包含4个元素
- 重复步骤3，直到所有元素排序完毕
分析算法
分析算法的结果意味着预测算法需要的资源。虽然我们有时主要关心像内存、通信带宽或计算机硬件这些资源，但通常我们想度量的是计算时间。一般来说，通过分析求解某个问题的几种候选算法，我们可以选出一种最有效的算法。这种分析可能指出不止一个可行的候选算法，但是在这个过程中，我们往往可以抛弃几个较差的算法。一般来说，算法需要的时间与输入的规模同步增长，所以通常把一个程序的运行时间描述成其输入规模的函数。
- 输入规模：输入规模的最佳概念依赖于研究的问题。对于许多问题，最自然的度量是输入中的项数，有时用两个数来描述一个算法的输入规模更为合适，如基于图的算法。
- 运行时间：一个算法在特定输入的运行时间是指执行的基本操作数或步数。其中步数，采用以下观点，执行每一行代码需要常量执行时间。
算法简述
- 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 插入排序算法时间复杂度为O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
- 插入排序算法空间复杂度为O(1)，原位排序。
- 插入排序根据不同的具体实现方式又可以分为: 直接插入排序，二分插入排序，2-路插入排序，表插入排序
- 折半插入排序只是减少了比较次数，移动次数并没有改变，说以算法的时间复杂度仍为O(n^2)
简述
工厂方法模式是工厂模式的一种，是常用的创建对象模式。在工厂方法模式中具体工厂负责生产具体产品，每一个具体工厂对应一种具体产品。工厂方法具有唯一性，一般情况下，一个具体工厂中只有一个或者一组重载的工厂方法。工厂方法模式的核心在于: 定义一个用于创建对象的接口，让子类决定实例化哪一个类。工厂方法，使一个类的实例化延时到其子类。
工厂方法模式主要包括四部分:
- 抽象工厂：核心工厂类不负责具体产品的创建，仅负责具体工厂子类必须实现的接口。
- 具体工厂：具体工厂是对抽象工厂的实现，一个具体产品对象的创建，在这里得到实例化，包含与应用程序密切相关的逻辑。
- 抽象产品：产品对象共同的父类，定义了其子类的一些公共属性与方法以及具体产品必须实现的接口。
- 具体产品：是对抽象产品所定义接口的具体实现，体现了面向对象编程多态的特性。某个具体产品一般都有与之对应的具体工厂创建。