设计模式之工厂方法模式

意图

工厂方法模式 (Factory Method)是一种创建型设计模式， 其在父类中提供一个创建对象的方法， 让子类决定实例化对象的类型。

• 工厂模式中，增加一种产品类，就要增加一个工厂类：因为每个工厂类只能创建一种产品的实例。
• 工厂模式遵循“开放-封闭原则”：工厂模式中，新增一种产品并不需要修改原有类，仅仅是扩展。

简单工厂模式相比于工厂方法模式

优点：工厂类中包含必要的逻辑判断，可根据客户端的选择条件动态实例化需要的类。对于客户端来说，去除了对具体产品的依赖。

缺点：违背了开放封闭原则。 每添加一个新的产品，都需要对原有类进行修改。增加维护成本，且不易于维护。

开放封闭原则：一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。

适用场景

• 当你在编写代码的过程中， 如果无法预知对象确切类别及其依赖关系时， 可使用工厂方法。
• 如果你希望用户能扩展你软件库或框架的内部组件， 可使用工厂方法。
• 如果你希望复用现有对象来节省系统资源， 而不是每次都重新创建对象， 可使用工厂方法。

结构

结构说明

1. 产品 （Product） 将会对接口进行声明。 对于所有由创建者及其子类构建的对象， 这些接口都是通用的。
2. 具体产品 （Concrete Products） 是产品接口的不同实现。
3. 创建者 （Creator） 类声明返回产品对象的工厂方法。 该方法的返回对象类型必须与产品接口相匹配。

• 你可以将工厂方法声明为抽象方法， 强制要求每个子类以不同方式实现该方法。 或者， 你也可以在基础工厂方法中返回默认产品类型。
• 注意， 尽管它的名字是创建者， 但他最主要的职责并不是创建产品。 一般来说， 创建者类包含一些与产品相关的核心业务逻辑。 工厂方法将这些逻辑处理从具体产品类中分离出来。 打个比方， 大型软件开发公司拥有程序员培训部门。 但是， 这些公司的主要工作还是编写代码， 而非生产程序员。

4. 具体创建者 （Concrete Creators） 将会重写基础工厂方法， 使其返回不同类型的产品。
   注意， 并不一定每次调用工厂方法都会创建新的实例。 工厂方法也可以返回缓存、 对象池或其他来源的已有对象。

结构代码范式

【Product】

定义产品对象的接口。

1
2
3

abstract class Product {
    public abstract void use();
}

【ConcreteProduct】

实现 Product 接口。

1
2
3
4
5
6
7
8
9
10

class ConcreteProduct extends Product {
    public ConcreteProduct() {
        System.out.println("创建 ConcreteProduct 产品");
    }

    @Override
    public void Use() {
        System.out.println("使用 ConcreteProduct 产品");
    }
}

【Creator】

声明工厂方法，它会返回一个产品类型的对象。 Creator 也可以实现一个默认的工厂方法 factoryMethod() ，以返回一个默认的具体产品类型。

1
2
3

interface Creator {
    public Product factoryMethod();
}

【ConcreteCreator】

覆写 Creator 中的工厂方法 factoryMethod() 。

1
2
3
4
5
6

class ConcreteCreator implements Creator {
    @Override
    public Product factoryMethod() {
        return new ConcreteProduct();
    }
}

【客户端】

1
2
3
4
5
6
7

public class factoryMethodPattern {
    public static void main(String[] args) {
        Creator factory = new ConcreteCreator();
        Product product = factory.factoryMethod();
        product.Use();
    }
}

【输出】

1
2

创建 ConcreteProduct 产品
使用 ConcreteProduct 产品

伪代码

以下示例演示了如何使用工厂方法开发跨平台 UI （用户界面） 组件， 并同时避免客户代码与具体 UI 类之间的耦合。

基础对话框类使用不同的 UI 组件渲染窗口。 在不同的操作系统下， 这些组件外观或许略有不同， 但其功能保持一致。 Windows 系统中的按钮在 Linux 系统中仍然是按钮。

如果使用工厂方法， 就不需要为每种操作系统重写对话框逻辑。 如果我们声明了一个在基本对话框类中生成按钮的工厂方法， 那么我们就可以创建一个对话框子类， 并使其通过工厂方法返回 Windows 样式按钮。 子类将继承对话框基础类的大部分代码， 同时在屏幕上根据 Windows 样式渲染按钮。

如需该模式正常工作， 基础对话框类必须使用抽象按钮 （例如基类或接口）， 以便将其扩展为具体按钮。 这样一来， 无论对话框中使用何种类型的按钮， 其代码都可以正常工作。

你可以使用此方法开发其他 UI 组件。 不过， 每向对话框中添加一个新的工厂方法， 你就离抽象工厂模式更近一步。 我们将在稍后谈到这个模式。

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

// 创建者类声明的工厂方法必须返回一个产品类的对象。创建者的子类通常会提供
// 该方法的实现。
class Dialog is
    // 创建者还可提供一些工厂方法的默认实现。
    abstract method createButton():Button

    // 请注意，创建者的主要职责并非是创建产品。其中通常会包含一些核心业务
    // 逻辑，这些逻辑依赖于由工厂方法返回的产品对象。子类可通过重写工厂方
    // 法并使其返回不同类型的产品来间接修改业务逻辑。
    method render() is
        // 调用工厂方法创建一个产品对象。
        Button okButton = createButton()
        // 现在使用产品。
        okButton.onClick(closeDialog)
        okButton.render()


// 具体创建者将重写工厂方法以改变其所返回的产品类型。
class WindowsDialog extends Dialog is
    method createButton():Button is
        return new WindowsButton()

class WebDialog extends Dialog is
    method createButton():Button is
        return new HTMLButton()


// 产品接口中将声明所有具体产品都必须实现的操作。
interface Button is
    method render()
    method onClick(f)

// 具体产品需提供产品接口的各种实现。
class WindowsButton implements Button is
    method render(a, b) is
        // 根据 Windows 样式渲染按钮。
    method onClick(f) is
        // 绑定本地操作系统点击事件。

class HTMLButton implements Button is
    method render(a, b) is
        // 返回一个按钮的 HTML 表述。
    method onClick(f) is
        // 绑定网络浏览器的点击事件。


class Application is
    field dialog: Dialog

    // 程序根据当前配置或环境设定选择创建者的类型。
    method initialize() is
        config = readApplicationConfigFile()

        if (config.OS == "Windows") then
            dialog = new WindowsDialog()
        else if (config.OS == "Web") then
            dialog = new WebDialog()
        else
            throw new Exception("错误！未知的操作系统。")

    // 当前客户端代码会与具体创建者的实例进行交互，但是必须通过其基本接口
    // 进行。只要客户端通过基本接口与创建者进行交互，你就可将任何创建者子
    // 类传递给客户端。
    method main() is
        this.initialize()
        dialog.render()

案例

使用示例： 工厂方法模式在 Java 代码中得到了广泛使用。 当你需要在代码中提供高层次的灵活性时， 该模式会非常实用。

核心 Java 程序库中有该模式的应用：

• java.util.Calendar#getInstance()
• java.util.ResourceBundle#getBundle()
• java.text.NumberFormat#getInstance()
• java.nio.charset.Charset#forName()
• java.net.URLStreamHandlerFactory#createURLStreamHandler(String) （根据协议返回不同的单例对象）
• java.util.EnumSet#of()
• javax.xml.bind.JAXBContext#createMarshaller() 及其他类似的方法。

识别方法： 工厂方法可通过构建方法来识别， 它会创建具体类的对象， 但以抽象类型或接口的形式返回这些对象。

还是以 简单工厂模式 里的例子来进行说明。

如何实现一个具有加减乘除基本功能的计算器？

两种模式的 Product 和 ConcreteProduct 角色代码没有区别，不再赘述。

差异在于 Factory 角色部分，以及客户端部分，请在代码中体会。

【Creator 角色】

1
2
3
4

// Creator 角色，定义返回产品实例的公共工厂方法
interface OperationFactory {
    public Operation factoryMethod();
}

【ConcreteCreator 角色】

和简单工厂模式相比，每一种产品都会有一个具体的工厂类负责生产实例。

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

// ConcreteCreator 角色，具体实现 Creator 中的方法
class AddFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Add();
    }
}

// ConcreteCreator 角色，具体实现 Creator 中的方法
class SubFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Sub();
    }
}

// ConcreteCreator 角色，具体实现 Creator 中的方法
class MulFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Mul();
    }
}

// ConcreteCreator 角色，具体实现 Creator 中的方法
class DivFactory implements OperationFactory {
    @Override
    public Operation factoryMethod() {
        return new Div();
    }
}

【Client 角色】

与简单工厂模式中无需关注具体创建不同，工厂模式中需要指定具体工厂，以负责生产具体对应的产品。

1
2
3
4
5
6
7
8
9
10
11

// Client 角色，需要指定具体工厂，以负责生产具体产品
public class factoryMethodPattern {
    public static void main(String[] args) {
        OperationFactory factory = new SubFactory();
        Operation oper = factory.factoryMethod();
        oper.numA = 3;
        oper.numB = 2;
        double result = oper.getResult();
        System.out.println("result = " + result);
    }
}

与其他模式的关系

• 在许多设计工作的初期都会使用工厂方法模式 （较为简单， 而且可以更方便地通过子类进行定制）， 随后演化为使用抽象工厂模式、 原型模式或生成器模式 （更灵活但更加复杂）。
• 抽象工厂模式通常基于一组工厂方法， 但你也可以使用原型模式来生成这些类的方法。
• 你可以同时使用工厂方法和迭代器模式来让子类集合返回不同类型的迭代器， 并使得迭代器与集合相匹配。
• 原型并不基于继承， 因此没有继承的缺点。 另一方面， 原型需要对被复制对象进行复杂的初始化。 工厂方法基于继承， 但是它不需要初始化步骤。
• 工厂方法是模板方法模式的一种特殊形式。 同时， 工厂方法可以作为一个大型模板方法中的一个步骤。

参考资料

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

设计模式之简单工厂模式

简介

简单工厂模式思想

简单工厂模式 (Simple Factory) 又叫静态工厂方法（Static Factory Method）模式。

简单工厂模式通常是定义一个工厂类，这个类可以根据不同变量返回不同类的产品实例。

简单工厂模式是一种对象创建型模式。但是简单工厂模式不属于23 种 Gof 设计模式之一。

简单工厂模式要点

优点：简单工厂模式的工厂类是整个模式的关键。其中包含了必要的逻辑判断，根据外部信息，决定究竟应该创建哪个具体类的对象。通过使用简单工厂模式，用户无需了解对象如何创建的，只要传入必要信息就可以了。

缺点：工厂类集中了所有实例的创建逻辑，违背了高内聚责任分配原则。随着系统中具体产品类不断增多，势必要不断修改工厂类，不易维护和扩展。同时，这也违背了开放封闭原则。

开放封闭原则：一个软件实体如类、模块和函数应该对扩展开放，对修改关闭。

实例

如何实现一个具有加减乘除基本功能的计算器？

对于这四种运算来说，都需要两个操作数，差别仅在于返回的结果不同。

由此，我们可以抽象化它们的共性，提炼出一个父类。这个类中包含两个操作数，一个返回结果方法，这个方法期望在子类中得以实现。

以下通过具体代码来说明。

【Product (Operation) 】

产品角色，简单工厂模式所创建的所有对象的父类，它负责描述所有实例所共有的公共接口。

1
2
3
4
5
6

// Product角色，所有实例所共有的公共接口
abstract class Operation {
    public int numA;
    public int numB;
    public abstract int GetResult();
}

【ConcreteProduct 组】

具体产品角色，实现 Product 中的接口。

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

// ConcreteProduct 角色，实现 Product 中的接口
class Add extends Operation {
    @Override
    public int GetResult() {
        return numA + numB;
    }
}

//ConcreteProduct 角色，实现 Product 中的接口
class Sub extends Operation {
    @Override
    public int GetResult() {
        return numA - numB;
    }
}

//ConcreteProduct 角色，实现 Product 中的接口
class Mul extends Operation {
    @Override
    public int GetResult() {
        return numA * numB;
    }
}

//ConcreteProduct 角色，实现 Product 中的接口
class Div extends Operation {
    @Override
    public int GetResult() {
        if (numB == 0) {
            System.out.println("ERROR!");
            return -1;
        }
        return numA / numB;
    }
}

【Factory (OperationFactory) 】

工厂角色，简单工厂模式的核心，它负责实现创建所有实例的内部逻辑。工厂类的创建产品类的方法可以被外界直接调用，创建所需的产品对象。

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

// 工厂角色，简单工厂模式的核心，它负责实现创建所有实例的内部逻辑
class OperationFactory {
    public static Operation CreateOperation (char operate) {
        Operation oper = null;
        switch(operate) {
        case '+':
            oper = new Add();
            break;
        case '-':
            oper = new Sub();
            break;
        case '*':
            oper = new Mul();
            break;
        case '/':
            oper = new Div();
            break;
        default:
            break;
        }
        return oper;
    }
}

【客户端】

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

public class SimpleFactoryPattern {
    public static void main(String[] args) {
        int numA = 10;
        int numB = 3;
        int result = 0;
        Operation oper = OperationFactory.CreateOperation('+');
        oper.numA = numA;
        oper.numB = numB;
        result = oper.GetResult();
        System.out.println(numA + " + " + numB + " = " + result);
    }
}

【输出】

1

10 + 3 = 13

参考资料

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

设计模式之单例模式

意图

单例模式（Singleton）是一种创建型设计模式， 让你能够保证一个类只有一个实例， 并提供一个访问该实例的全局节点。

单例 （Singleton） 类声明了一个名为 get­Instance 获取实例的静态方法来返回其所属类的一个相同实例。

单例的构造函数必须对客户端 （Client） 代码隐藏。 调用 get­Instance 方法必须是获取单例对象的唯一方式。

所有单例的实现都包含以下两个相同的步骤：

• 将默认构造函数设为私有， 防止其他对象使用单例类的 new运算符。
• 新建一个静态构建方法作为构造函数。 该函数会 “偷偷” 调用私有构造函数来创建对象， 并将其保存在一个静态成员变量中。 此后所有对于该函数的调用都将返回这一缓存对象。

如果你的代码能够访问单例类， 那它就能调用单例类的静态方法。 无论何时调用该方法， 它总是会返回相同的对象。

单例模式的优点：

• ✔️️️ 你可以保证一个类只有一个实例。
• ✔️️️ 你获得了一个指向该实例的全局访问节点。
• ✔️️️ 仅在首次请求单例对象时对其进行初始化。

单例模式的缺点：

• ❌ 违反了单一职责原则。 该模式同时解决了两个问题。
• ❌ 单例模式可能掩盖不良设计， 比如程序各组件之间相互了解过多等。
• ❌ 该模式在多线程环境下需要进行特殊处理， 避免多个线程多次创建单例对象。
• ❌ 单例的客户端代码单元测试可能会比较困难， 因为许多测试框架以基于继承的方式创建模拟对象。 由于单例类的构造函数是私有的， 而且绝大部分语言无法重写静态方法， 所以你需要想出仔细考虑模拟单例的方法。 要么干脆不编写测试代码， 或者不使用单例模式。

适用场景

• 如果程序中的某个类对于所有客户端只有一个可用的实例， 可以使用单例模式。
  ⚡ 单例模式禁止通过除特殊构建方法以外的任何方式来创建自身类的对象。 该方法可以创建一个新对象， 但如果该对象已经被创建， 则返回已有的对象。
• 如果你需要更加严格地控制全局变量， 可以使用单例模式。
  ⚡ 单例模式与全局变量不同， 它保证类只存在一个实例。 除了单例类自己以外， 无法通过任何方式替换缓存的实例。

请注意， 你可以随时调整限制并设定生成单例实例的数量， 只需修改 获取实例 方法， 即 getInstance 中的代码即可实现。

举例来说，一些资源管理器常常设计成单例模式。

在计算机系统中，需要管理的资源包括软件外部资源，譬如每台计算机可以有若干个打印机，但只能有一个 Printer Spooler， 以避免两个打印作业同时输出到打印机中。

每台计算机可以有若干通信端口，系统应当集中管理这些通信端口，以避免一个通信端口同时被两个请求同时调用。任务管理器中难以启动两个相同的 task。

结构

1. 单例 （Singleton） 类声明了一个名为 get­Instance获取实例的静态方法来返回其所属类的一个相同实例。
   • 单例的构造函数必须对客户端 （Client） 代码隐藏。 调用 获取实例方法必须是获取单例对象的唯一方式。

伪代码

在本例中， 数据库连接类即是一个单例。

该类不提供公有构造函数， 因此获取该对象的唯一方式是调用 获取实例方法。 该方法将缓存首次生成的对象， 并为所有后续调用返回该对象。

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

// 数据库类会对`getInstance（获取实例）`方法进行定义以让客户端在程序各处
// 都能访问相同的数据库连接实例。
class Database is
    // 保存单例实例的成员变量必须被声明为静态类型。
    private static field instance: Database

    // 单例的构造函数必须永远是私有类型，以防止使用`new`运算符直接调用构
    // 造方法。
    private constructor Database() is
        // 部分初始化代码（例如到数据库服务器的实际连接）。
        // ...

    // 用于控制对单例实例的访问权限的静态方法。
    public static method getInstance() is
        if (Database.instance == null) then
            acquireThreadLock() and then
                // 确保在该线程等待解锁时，其他线程没有初始化该实例。
                if (Database.instance == null) then
                    Database.instance = new Database()
        return Database.instance

    // 最后，任何单例都必须定义一些可在其实例上执行的业务逻辑。
    public method query(sql) is
        // 比如应用的所有数据库查询请求都需要通过该方法进行。因此，你可以
        // 在这里添加限流或缓冲逻辑。
        // ...

class Application is
    method main() is
        Database foo = Database.getInstance()
        foo.query("SELECT ...")
        // ...
        Database bar = Database.getInstance()
        bar.query("SELECT ...")
        // 变量 `bar` 和 `foo` 中将包含同一个对象。

案例

使用示例： 许多开发者将单例模式视为一种反模式。 因此它在 Java 代码中的使用频率正在逐步减少。

尽管如此， Java 核心程序库中仍有相当多的单例示例：

• java.lang.Runtime#getRuntime()
• java.awt.Desktop#getDesktop()
• java.lang.System#getSecurityManager()

识别方法： 单例可以通过返回相同缓存对象的静态构建方法来识别。

数据库连接类

数据库连接类即是一个单例。

该类不提供公有构造函数， 因此获取该对象的唯一方式是调用 获取实例方法。 该方法将缓存首次生成的对象， 并为所有后续调用返回该对象。

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

// 数据库类会对`getInstance（获取实例）`方法进行定义以让客户端在程序各处
// 都能访问相同的数据库连接实例。
class Database is
    // 保存单例实例的成员变量必须被声明为静态类型。
    private static field instance: Database

    // 单例的构造函数必须永远是私有类型，以防止使用`new`运算符直接调用构
    // 造方法。
    private constructor Database() is
        // 部分初始化代码（例如到数据库服务器的实际连接）。
        // ...

    // 用于控制对单例实例的访问权限的静态方法。
    public static method getInstance() is
        if (Database.instance == null) then
            acquireThreadLock() and then
                // 确保在该线程等待解锁时，其他线程没有初始化该实例。
                if (Database.instance == null) then
                    Database.instance = new Database()
        return Database.instance

    // 最后，任何单例都必须定义一些可在其实例上执行的业务逻辑。
    public method query(sql) is
        // 比如应用的所有数据库查询请求都需要通过该方法进行。因此，你可以
        // 在这里添加限流或缓冲逻辑。
        // ...

class Application is
    method main() is
        Database foo = Database.getInstance()
        foo.query("SELECT ...")
        // ...
        Database bar = Database.getInstance()
        bar.query("SELECT ...")
        // 变量 `bar` 和 `foo` 中将包含同一个对象。

懒汉式

懒汉式的实现思路是：你不找懒汉，懒汉根本就懒得去初始化自己。

instance 初始时没有初始化，只有当第一次调 getInstance() 时才创建实例。

缺点：当有两个线程调 getInstance() 方法，当它们同时执行到 if (null == instance) 这行代码，instance 为 null。

继续向下执行，会生成两个实例，违背了单例模式的初衷。

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

public class LazySingleton {
    private LazySingleton() {
        System.out.println("Singleton()");
    }

    private static LazySingleton instance = null;

    public static LazySingleton getInstance() {
        if (null == instance) {
            instance = new LazySingleton();
        }
        return instance;
    }
}

饿汉式

懒汉式的实现思路是：饿汉根本等不及别人来找他，不管三七二十一先初始化了自身的实例，生怕自己饿着了。

类默认先直接初始化一个实例，以后调用 getInstance() 总是返回这个已创建好的实例。

缺点：在没有必要获取实例时，已经预先产生了开销。

优点：规避了懒汉式方法的线程问题，不用显示编写线程安全代码。

1
2
3
4
5
6
7
8
9
10
11

public class HungerSinleton {
    private HungerSinleton() {
        System.out.println("Singleton()");
    }

    private static HungerSinleton instance = new HungerSinleton();

    public static HungerSinleton getInstance() {
        return instance;
    }
}

双重锁的形式

如果既不想在没有调用 getInstance() 方法时产生开销，又不想发生线程安全问题，就可以采用双重锁的形式。

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

public class SyncSingleton {
    private SyncSingleton() {
        System.out.println("Singleton()");
    }

    private static SyncSingleton instance = null;

    public static SyncSingleton getInstance() {
        if (null == instance) {
            synchronized(SyncSingleton.class) {
                if (null == instance) {
                    instance = new SyncSingleton();
                }
            }
        }
        return instance;
    }
}

注：在外面判断了 instance 实例是否存在，为什么在锁定后又要在内部又判断一次？

这是因为，如果 instance 为 null 时有两个线程同时调用 getInstance()，由于 synchronized 机制，只允许一个线程进入，另一个需要等待。

这时如果没有第二道 instance 是否为 null 的判断，就可能发生第一个线程创建一个实例，而第二个线程又创建一个实例的情况。

与其他模式的关系

• 外观模式类通常可以转换为单例模式类， 因为在大部分情况下一个外观对象就足够了。
• 如果你能将对象的所有共享状态简化为一个享元对象， 那么享元模式就和单例类似了。 但这两个模式有两个根本性的不同。
  1. 只会有一个单例实体， 但是享元类可以有多个实体， 各实体的内在状态也可以不同。
  2. 单例对象可以是可变的。 享元对象是不可变的。
• 抽象工厂模式、 生成器模式和原型模式都可以用单例来实现。

参考资料

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

数组和链表

数组和链表分别代表了连续空间和不连续空间的存储方式，它们是线性表（Linear List）的典型代表。其他所有的数据结构，比如栈、队列、二叉树、B+ 树等，实际上都是这两者的结合和变化。

数组

数组用 连续 的内存空间来存储数据。

数组的访问

数组元素的访问是以行或列索引的单一下标表示。

在上面的例子中，数组 a 中有 5 个元素。也就是说，a 的长度是 6 。我们可以使用 a[0] 来表示数组中的第一个元素。因此，a[0] = A 。类似地，a[1] = B，a[2] = C，依此类推。

数组的插入

数组的删除

数组的特性

数组设计之初是在形式上依赖内存分配而成的，所以必须在使用前预先分配好空间大小。这使得数组有以下特性：

1. 用连续的内存空间来存储数据。
2. **数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)**。
3. **数组的插入、删除操作，平均时间复杂度为 O(n)**。
4. 空间大小固定，一旦建立，不能再改变。扩容只能采用复制数组的方式。
5. 在旧式编程语言中（如有中阶语言之称的 C），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险。

多维数组

数组是有下标和值组成集合。

如果数组的下标有多个维度，即为多维数组。比如：二维数组可以视为“数组元素为一维数组”的一维数组；三维数组可以视为“数组元素为二维数组”的一维数组；依次类推。

下图是由 M 个行向量，N 个列向量组成的二维数组.

链表

链表用不连续的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。

区别于数组，链表中的元素不是存储在内存中连续的一片区域，链表中的数据存储在每一个称之为“结点”复合区域里，在每一个结点除了存储数据以外，还保存了到下一个节点的指针（Pointer）。由于不必按顺序存储，链表在插入数据的时候可以达到 O(1) 的复杂度，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。

链表具有以下特性：

• 链表允许插入和移除任意位置上的节点，其时间复杂度为 O(1)
• 链表没有数组的随机访问特性，链表只支持顺序访问，其时间复杂度为 O(n)。
• 数组的空间大小是固定的，而链表的空间大小可以动态增长。相比于数组，链表支持扩容，显然更为灵活，但是由于多了指针域，空间开销也更大。
• 链表相比于数组，多了头指针、尾指针（非必要），合理使用可以大大提高访问效率。

链表有多种类型：

• 单链表
• 双链表
• 循环链表

单链表

单链表中的每个结点不仅包含数据值，还包含一个指针，指向其后继节点。通过这种方式，单链表将所有结点按顺序组织起来。

与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按 索引 来 访问元素 平均要花费 O(N) 时间，其中 N 是链表的长度。

单链表插入

如果我们想在给定的结点 prev 之后添加新值，我们应该：

（1）使用给定值初始化新结点 cur；

（2）将 cur 的 next 字段链接到 prev 的下一个结点 next ；

（3）将 prev 中的 next 字段链接到 cur 。

与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

单链表删除

如果我们想从单链表中删除现有结点 cur，可以分两步完成：

（1）找到 cur 的上一个结点 prev 及其下一个结点 next ；

（2）接下来链接 prev 到 cur 的下一个节点 next 。

在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。

空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

双链表

双链表中的每个结点不仅包含数据值，还包含两个指针，分别指向指向其前驱节点和后继节点。

单链表的访问是单向的，而双链表的访问是双向的。显然，双链表比单链表操作更灵活，但是空间开销也更大。

双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

双链表插入

如果我们想在给定的结点 prev 之后添加新值，我们应该：

（1）使用给定值初始化新结点 cur；

（2）链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；

（3）用 cur 重新链接 prev 和 next。

与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

双链表删除

如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同，使用 prev 字段可以很容易地在常量时间内获得前一个结点。

因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是 O(1)。

循环链表

循环单链表

循环单链表是一种特殊的单链表。它和单链表唯一的区别就在最后结点。

• 单链表的最后一个结点的后继指针 next 指向空地址。
• 循环链表的最后一个结点的后继指针 next 指向第一个节点（如果有头节点，就指向头节点）。

循环双链表

数组 vs. 链表

• 存储方式
  • 数组用 连续 的内存空间来存储数据。
  • 链表用 不连续 的内存空间来存储数据；并通过一个指针按顺序将这些空间串起来，形成一条链。
• 访问方式
  • 数组支持随机访问。根据下标随机访问的时间复杂度为 O(1)
  • 链表不支持随机访问，只能顺序访问，时间复杂度为 O(n)。
• 空间大小
  • 数组空间大小固定，扩容只能采用复制数组的方式。
  • 链表空间大小不固定，扩容灵活。
• 效率比较
  • 数组的 查找 效率高于链表。
  • 链表的 添加、删除 效率高于数组。

数组和链表的基本操作示例

关于数组和链表的基本操作，网上和各种书籍、教程中已经有大量的示例，感兴趣可以自行搜索。本文只是简单展示一下数组和链表的基本操作。

一维数组的基本操作

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

public class Main {
    public static void main(String[] args) {
        // 1. Initialize
        int[] a0 = new int[5];
        int[] a1 = {1, 2, 3};
        // 2. Get Length
        System.out.println("The size of a1 is: " + a1.length);
        // 3. Access Element
        System.out.println("The first element is: " + a1[0]);
        // 4. Iterate all Elements
        System.out.print("[Version 1] The contents of a1 are:");
        for (int i = 0; i < a1.length; ++i) {
            System.out.print(" " + a1[i]);
        }
        System.out.println();
        System.out.print("[Version 2] The contents of a1 are:");
        for (int item: a1) {
            System.out.print(" " + item);
        }
        System.out.println();
        // 5. Modify Element
        a1[0] = 4;
        // 6. Sort
        Arrays.sort(a1);
    }
}

二维数组的基本操作

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

public class TwoDimensionArray {
    private static void printArray(int[][] a) {
        for (int i = 0; i < a.length; ++i) {
            System.out.println(a[i]);
        }
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; a[i] != null && j < a[i].length; ++j) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        System.out.println("Example I:");
        int[][] a = new int[2][5];
        printArray(a);
        System.out.println("Example II:");
        int[][] b = new int[2][];
        printArray(b);
        System.out.println("Example III:");
        b[0] = new int[3];
        b[1] = new int[5];
        printArray(b);
    }
}

单链表的基本操作

单链表节点的数据结构

1
2
3
4
5
6
7
8

public class ListNode<E> {
    E value;
    ListNode<E> next; // 指向后继节点
}

public class SingleLinkList<E> {
    private ListNode<E> head; // 头节点
}

（1）从头部添加节点（即头插法）

1
2
3
4
5

void addHead(E value) {
    ListNode<E> newNode = new ListNode<>(value, null);
    newNode.next = this.head.next;
    this.head.next = newNode;
}

（2）从尾部添加节点（即尾插法）

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

void addTail(E value) {
    // init new node
    ListNode<E> newNode = new ListNode<>(value, null);

    // find the last node
    ListNode<E> node = this.head;
    while (node.next != null) {
        node = node.next;
    }

    // add new node to tail
    node.next = newNode;
}

（3）删除节点

找到要删除元素的前驱节点，将前驱节点的 next 指针指向下一个节点。

1
2
3
4
5
6
7
8
9
10
11

public void remove(E value) {
    ListNode<E> prev = this.head;
    while (prev.next != null) {
        ListNode<E> curr = prev.next;
        if (curr.value.equals(value)) {
            prev.next = curr.next;
            break;
        }
        prev = prev.next;
    }
}

（4）查找节点

从头开始查找，一旦发现有数值与查找值相等的节点，直接返回此节点。如果遍历结束，表明未找到节点，返回 null。

1
2
3
4
5
6
7
8
9
10

public ListNode<E> find(E value) {
    ListNode<E> node = this.head.next;
    while (node != null) {
        if (node.value.equals(value)) {
            return node;
        }
        node = node.next;
    }
    return null;
}

双链表的基本操作

双链表节点的数据结构：

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

static class DListNode<E> {
    E value;
    DListNode<E> prev; // 指向前驱节点
    DListNode<E> next; // 指向后继节点
}

public class DoubleLinkList<E> {
    /** 头节点 */
    private DListNode<E> head;
    /** 尾节点 */
    private DListNode<E> tail;
}

（1）从头部添加节点

1
2
3
4
5
6
7
8
9

public void addHead(E value) {
    DListNode<E> newNode = new DListNode<>(null, value, null);

    this.head.next.prev = newNode;
    newNode.next = this.head.next;

    this.head.next = newNode;
    newNode.prev = this.head;
}

（2）从尾部添加节点

1
2
3
4
5
6
7
8
9

public void addTail(E value) {
    DListNode<E> newNode = new DListNode<>(null, value, null);

    this.tail.prev.next = newNode;
    newNode.prev = this.tail.prev;

    this.tail.prev = newNode;
    newNode.next = this.tail;
}

（3）删除节点

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

public void remove(E value) {
    DListNode<E> prev = this.head;
    while (prev.next != this.tail) {
        DListNode<E> curr = prev.next;
        if (curr.value.equals(value)) {
            prev.next = curr.next;
            curr.next.prev = prev;
            curr.next = null;
            curr.prev = null;
            break;
        }
        prev = prev.next;
    }
}

（4）查找节点

1
2
3
4
5
6
7
8
9
10

public DListNode<E> find(E value) {
    DListNode<E> node = this.head.next;
    while (node != this.tail) {
        if (node.value.equals(value)) {
            return node;
        }
        node = node.next;
    }
    return null;
}

练习

• 数组
  • 724. 寻找数组的中心下标
  • 35. 搜索插入位置
  • 56. 合并区间
• 链表
  • 设计链表
  • 环形链表
  • 环形链表 II
  • 相交链表
  • 删除链表的倒数第 N 个节点
  • 反转链表
  • 移除链表元素
  • 奇偶链表
  • 回文链表
  • 合并两个有序链表
  • 两数相加
  • 扁平化多级双向链表
  • 复制带随机指针的链表
  • 旋转链表

参考资料

• 数据结构与算法之美
• 数据结构（C 语言版）
• 数据结构（C++语言版）
• Leetcode：数组和字符串
• Leetcode：链表

图

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

什么是图

• 阶（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 测试例

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