算法与设计模式

---

课程目标

• 帮助建立算法与设计模式的联系
• 理解常见算法背后的设计思想，并能在实际开发中灵活运用。

---

学习价值

• 是通过大厂面试的必备硬核能力
• 是升职加薪必备的基础能力
• 是成为高阶测试开发工程师的必经之路

---

招聘需求

• 阿里巴巴招聘需求:
  • 薪资: 20K+
  • 要求: 具备很强的逻辑思维能力和较高的分析、处理问题的能力

• 字节测试开发实习生招聘需求：
  • 具备较强的逻辑思维能力、沟通协作能力和学习能力

---

算法的学习路径

• 学习路径

---

实战案例

---

查找算法

• 顺序查找
• 二分查找

---

排序

• 冒泡排序
• 递归算法
• 快速排序

---

设计模式

---

设计模式原则

• 设计模式原则

---

设计模式分类

• 创建型设计模式共五种：工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。
• 结构型设计模式共七种：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。
• 行为型设计模式共十一种：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。

---

设计模式的使用时机

• 但代码将要成为“狗屎码”时，请使用设计模式。
  • 重复代码：多个地方出现相似逻辑 → 考虑模板方法模式或策略模式。
  • 过长的分支逻辑：多个分支逻辑 → 考虑状态模式、策略模式或工厂模式。
  • 类臃肿：一个类承担过多职责 → 装饰器模式或职责链模式拆分功能。
• 需要解耦的时候
  • 组件间强依赖：希望减少直接依赖 → 观察者模式（事件通知）、中介者模式（通过中介交互）
  • 创建对象依赖具体类：需要隔离对象创建 → 抽象工厂模式或工厂方法模式。
• 需要提升扩展性时
  • 未来可能新增功能：通过扩展而非修改代码实现 → 装饰器模式（动态添加功能）、访问者模式（新增操作）。
  • 支持多种算法或行为：运行时切换 → 策略模式。
  • 需要动态组合对象：如树形结构 → 组合模式。
• 性能或资源管理需求
• 系统复杂度升高时
• 接口兼容性问题

---

何时避免设计模式？

• 问题足够简单：直接编码比套用模式更清晰。
• 过度设计风险：未来需求不明确时，避免提前引入复杂模式。
• 团队理解成本：模式增加理解难度，需权衡可维护性。

---

设计模式案例

---

需要动态切换排序-策略模式

完整代码实现

python代码

import random
from abc import ABC, abstractmethod  # 引入抽象基类模块
import time  # 引入时间模块用于性能测试

# 抽象策略接口 SortStrategy
class SortStrategy(ABC):
    @abstractmethod
    def sort(self, data: list) -> tuple[list, float]:
        """子类必须实现的方法"""
        pass


# 冒泡排序策略实现
class BubbleSort(SortStrategy):
    def sort(self, data):
        """子类实现冒泡排序"""
        n = len(data)  # 数据长度
        for i in range(n):
            for j in range(0, n - i - 1):
                # 比较相邻元素并交换
                if data[j] > data[j + 1]:
                    data[j], data[j + 1] = data[j + 1], data[j]
        return data  # 返回排序后的数据列表


# 快速排序策略实现
class QuickSort(SortStrategy):
    def sort(self, data):
        """子类实现快速排序"""
        # 如果数据长度小于等于1，则返回原数据（递归终止条件）
        if len(data) <= 1:
            return data
        # 选择中间位置的元素作为基准点
        pivot = data[len(data) // 2]
        # 分割数据为三个部分：
        left = [x for x in data if x < pivot]   # 左侧元素小于基准点
        middle = [x for x in data if x == pivot]  # 中间元素等于基准点
        right = [x for x in data if x > pivot]  # 右侧元素大于基准点
        # 递归调用排序，并将结果合并
        return self.sort(left) + middle + self.sort(right)


# 策略模式上下文类 Sorter
class Sorter:
    def __init__(self, strategy: SortStrategy):
        """构造函数指定策略"""
        self._strategy = strategy  # 初始化策略

    def execute(self, data):
        return self._strategy.sort(data.copy())  # 执行策略排序方法，传入数据副本防止修改原始数据


# 性能测试函数
def time_sort(func, data):
    start = time.time()  # 记录开始时间
    func(data)  # 调用传入的函数
    return time.time() - start  # 返回耗时


if __name__ == '__main__':
    # 测试数据：生成10000个随机数
    data = [random.randint(0, 10000) for _ in range(10000)]
    # 创建Sorter对象并执行排序
    sorter = Sorter(QuickSort())  # 使用快速排序策略初始化Sorter
    # 执行快排测试性能
    print(time_sort(sorter.execute, data))  # 输出排序耗时
    # 更换策略
    sorter._strategy = BubbleSort()  # 将策略更换为冒泡排序
    # 执行冒泡排序测试性能
    print(time_sort(sorter.execute, data))  # 输出排序耗时

---

java 代码

import java.util.ArrayList;
import java.util.List;

// 定义排序策略的公共接口，所有具体排序算法都需要实现该接口
interface SortStrategy {
    int[] sort(int[] data); // 排序方法，接收整型数组并返回排序后的结果
}
// 实现冒泡排序的具体策略类
class BubbleSort implements SortStrategy {
    public int[] sort(int[] data) {
        System.out.println("执行冒泡排序"); // 打印日志用于调试
        int n = data.length; // 获取数组长度
        // 双层循环进行相邻元素比较与交换
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (data[j] > data[j+1]) {  
                    // 如果前一个元素比后一个大，则交换
                    int temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }
            }
        }
        return data; // 返回排序后的数组
    }
}

// 实现快速排序的具体策略类
class QuickSort implements SortStrategy {
    public int[] sort(int[] data) {
        System.out.println("执行快速排序"); // 打印日志用于调试
        quickSort(data, 0, data.length-1);  // 调用递归快排函数
        return data; // 返回排序后的数组
    }

    // 快速排序主逻辑
    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high); // 分区操作获取基准点位置
            quickSort(arr, low, pi-1); // 对左半部分递归排序
            quickSort(arr, pi+1, high); // 对右半部分递归排序
        }
    }

    // 交换两个数组元素的方法
    private void swap(int[] list, int i,int j){
        // 交换操作
        int temp = list[i]; 
        list[i] = list[j];
        list[j] = temp;
    }

    // 分区操作：将小于基准值的放在左边，大于基准值的放在右边
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 选取最右端元素作为基准
        int i = low-1;  // 指针i记录小于pivot的边界
        for (int j=low; j<high; j++) {
            if (arr[j] < pivot) { // 当前元素小于基准值时
                i++;
                swap(arr, i, j); // 交换到i的位置
            }
        }
        swap(arr, i+1, high);  // 将基准值放到正确位置
        return i+1; // 返回基准值索引
    }
}

// 上下文类，负责持有当前排序策略并调用其排序方法
class Sorter {
    private SortStrategy strategy;

    // 构造函数设置初始策略
    public Sorter(SortStrategy strategy) {
        this.strategy = strategy;
    }

    // 执行排序操作，对原始数据进行克隆避免修改原数据
    public int[] execute(int[] data) {
        return strategy.sort(data.clone());
    }

    // 动态更换排序策略
    public void setStrategy(SortStrategy strategy) {
        this.strategy = strategy;
    }
}

// 提供时间测量功能的工具类
class TimeSort {
    // 接收Runnable对象，计算其执行耗时（单位：秒）
    public static double timeSort(Runnable func) {
        long start = System.currentTimeMillis();  // 记录开始时间
        func.run(); // 执行传入的函数
        return (System.currentTimeMillis() - start) / 1000.0;  // 返回耗时（秒）
    }
}

// 主程序
public class DemoJava {
    public static void main(String[] args) {
        // 随机产生10000个随机数
        List<Integer> randomNumbers = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            randomNumbers.add((int)(Math.random() * 10000));
        }
        // 将List转换为int数组
        int[] data = randomNumbers.stream().mapToInt(Integer::intValue).toArray();
//        System.out.println("原始数据：" + java.util.Arrays.toString(data));

        // 创建使用快速排序的Sorter实例，并测试性能
        Sorter sorter = new Sorter(new QuickSort());
        double quickSortTime = TimeSort.timeSort(() -> sorter.execute(data));
//        System.out.println("排序后的数据：" + java.util.Arrays.toString(sorter.execute(data)));
        System.out.println("QuickSort took: " + quickSortTime + " seconds");

        // 更换为冒泡排序策略，并再次测试性能
        sorter.setStrategy(new BubbleSort());
        double bubbleSortTime = TimeSort.timeSort(() -> sorter.execute(data));
//        System.out.println("排序后的数据：" + java.util.Arrays.toString(sorter.execute(data)));
        System.out.println("BubbleSort took: " + bubbleSortTime + " seconds");
    }
}

---

流程固化-模板方法模式

完整代码实现

python代码

import random
from abc import ABC, abstractmethod


class SortTemplate(ABC):
    def sort_and_print(self, data):
        """模板方法（固定流程）"""
        print("=== 开始排序流程 ===")
        self.pre_process(data)  # 钩子方法
        self.do_sort(data)  # 抽象方法
        self.validate(data)  # 默认验证
        self.print_result(data)  # 固定输出
        print("=== 流程结束 ===\n")

    @abstractmethod
    def do_sort(self, data):
        """子类必须实现的排序算法"""
        pass

    def pre_process(self, data):
        """钩子方法：预处理（可选覆盖）"""
        print(f"[默认预处理] 数据长度: {len(data)}")

    def validate(self, data):
        """默认方法：验证是否有序"""
        for i in range(len(data) - 1):
            if data[i] > data[i + 1]:
                raise RuntimeError("排序结果验证失败！")
        print("[验证通过] 数组已有序")

    def print_result(self, data):
        """固定方法：打印结果"""
        print("排序结果:", " ".join(map(str, data)))


class QuickSort(SortTemplate):
    def do_sort(self, data):
        """快速排序（原地修改）"""
        print("[算法] 快速排序")
        # 调用递归快速排序
        self._quick_sort(data, 0, len(data) - 1)

    def _quick_sort(self, data, low, high):
        """递归快速排序"""
        # 如果low >= high，则说明数组已排序完毕
        if low < high:
            pi = self._partition(data, low, high) # 分区操作获取基准点位置
            self._quick_sort(data, low, pi - 1) # 对左半部分递归排序
            self._quick_sort(data, pi + 1, high) # 对右半部分递归排序

    def _partition(self, data, low, high):
        """分区操作：将小于基准值的放在左边，大于基准值的放在右边"""
        pivot = data[high] # 选取最右端元素作为基准
        i = low - 1 # 指针i记录小于pivot的边界
        for j in range(low, high): # 遍历数组
            if data[j] < pivot: # 当前元素小于基准值时
                i += 1 # 移动指针i
                data[i], data[j] = data[j], data[i] # 交换到i的位置
        data[i + 1], data[high] = data[high], data[i + 1] # 将基准值放到正确位置
        return i + 1 # 返回基准值索引

    def pre_process(self, data):
        """覆盖预处理钩子方法"""
        print(f"[快速排序预处理] 检测到 {len(data)} 个元素")


class BubbleSort(SortTemplate):
    def do_sort(self, data):
        """冒泡排序实现"""
        print("[算法] 冒泡排序")
        # 调用冒泡排序实现
        self._bubble_sort(data)

    def _bubble_sort(self, data):
        """冒泡排序实现"""  
        for i in range(len(data) - 1): # 外层循环控制排序轮数，共 len(data) - 1 轮（n个元素最多需要n-1次完全比较）
            # 内层循环控制每一轮的比较次数，随着i递增，已排好序的元素不再参与比较
            # 每次遍历将当前未排序部分中最大的元素“冒泡”到数组末尾  
            for j in range(len(data) - 1 - i):
                # 比较相邻元素，如果前一个元素大于后一个元素，则交换位置
                if data[j] > data[j + 1]: 
                    data[j], data[j + 1] = data[j + 1], data[j]

    def pre_process(self, data):
        """覆盖预处理钩子方法"""
        print(f"[冒泡排序预处理] 检测到 {len(data)} 个元素")


if __name__ == '__main__':
    data = [random.randint(1, 100) for i in range(100)]
    QuickSort().sort_and_print(data)
    BubbleSort().sort_and_print(data)

---

java 代码实现

// SortTemplate.java
// 定义排序模板抽象类，封装排序流程框架
abstract class SortTemplate {

    // 模板方法（final防止子类修改流程）
    public final void sortAndPrint(int[] data) {
        System.out.println("=== 开始排序流程 ===");
        preProcess(data);       // 钩子方法（可选预处理）
        doSort(data);           // 抽象方法（子类实现排序算法）
        validate(data);        // 默认结果验证
        printResult(data);      // 固定输出逻辑
        System.out.println("=== 流程结束 ===\n");
    }

    // 抽象方法：子类必须实现的排序算法
    protected abstract void doSort(int[] data);

    // 钩子方法：预处理（子类可选覆盖）默认打印数据长度
    protected void preProcess(int[] data) {
        System.out.println("[默认预处理] 数据长度: " + data.length);
    }

    // 默认方法：验证数组是否有序（升序）
    protected void validate(int[] data) {
        for (int i = 0; i < data.length - 1; i++) {
            if (data[i] > data[i + 1]) {
                throw new RuntimeException("排序结果验证失败！");
            }
        }
        System.out.println("[验证通过] 数组已有序");
    }

    // 固定方法：打印结果
    private void printResult(int[] data) {
        System.out.print("排序结果: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

//BubbleSort.java
// 冒泡排序类，继承排序模板类
public class BubbleSort extends SortTemplate {
    // 实现抽象方法：定义冒泡排序的具体算法
    @Override
    protected void doSort(int[] data) {
        System.out.println("[算法] 冒泡排序");
        bubbleSort(data);
    }

    private void bubbleSort(int[] data) {
        // 外层循环控制排序轮数，共 data.length - 1 轮
        for (int i = 0; i < data.length - 1; i++) {
            // 内层循环控制每一轮的比较次数，随着i递增，已排好序的元素不再参与比较
            for (int j = 0; j < data.length - 1 - i; j++) {
                // 比较相邻元素，如果前元素大于后元素，则交换位置
                if (data[j] > data[j + 1]) {
                    swap(data, j, j + 1);  // 交换相邻元素
                }
            }
        }
    }

    // 元素交换方法
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 覆盖预处理钩子方法,提供冒泡排序专用的预处理信息
    @Override
    protected void preProcess(int[] data) {
        System.out.println("[冒泡排序预处理] 检测到 " + data.length + " 个元素");
    }
}

// QuickSort.java
// 快速排序类，继承排序模板类
class QuickSort extends SortTemplate {
     // 实现抽象方法：定义快速排序的具体算法
    @Override
    protected void doSort(int[] data) {
        System.out.println("[算法] 快速排序");
        quickSort(data, 0, data.length - 1);
    }

    // 快速排序主逻辑
    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high); // 获取基准点位置
            quickSort(arr, low, pivot - 1); // 对左半部分递归排序
            quickSort(arr, pivot + 1, high); // 对右半部分递归排序
        }
    }

    // 分区函数：将小于基准值的放左边，大于基准值的放右边
    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最右端元素作为基准
        int i = low - 1; // 小于基准值的边界指针
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j); // 将小元素移动到左侧
            }
        }
        swap(arr, i + 1, high); // 将基准值放到正确位置
        return i + 1;  // 返回基准值索引
    }

    // 元素交换方法
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 覆盖预处理钩子方法,提供快速排序专用的预处理信息
    @Override
    protected void preProcess(int[] data) {
        System.out.println("[快速排序预处理] 检测到 " + data.length + " 个元素");
    }
}

// Main.java
// 主程序入口
public class Main {
    public static void main(String[] args) {
        int[] data = new int[]{5, 4, 3, 2, 1}; // 初始化测试数据
        // 创建冒泡排序实例
        SortTemplate bubbleSort = new BubbleSort();
        // 创建快速排序实例
        SortTemplate quickSort = new QuickSort();
        // 执行排序、输出全过程
        bubbleSort.sortAndPrint(data);
        quickSort.sortAndPrint(data);
    }
}

---

总结

• 关键算法的掌握
  • 查找算法：顺序查找（O(n)） vs 二分查找（O(log n)）
  • 排序算法：冒泡排序（O(n²)） vs 快速排序（O(n log n)）
  • 递归思想：分治策略的应用
• 设计模式的应用
  • 策略模式：动态切换算法实现
  • 模板方法：固化算法流程框架
  • 遵循开闭原则：对扩展开放，对修改关闭