vue-admin-template 对接后端API JWT认证

发表于 2020-07-11 更新于 2026-05-09

本文是一篇实战教程，详细记录了如何将 vue-admin-template 项目从使用前端 Mock 数据，切换为对接真实的、基于 JWT 认证的后端 API（本例后端为 FastAPI）。涵盖环境配置、请求封装、登录认证、用户信息获取及页面路由调整等核心环节。

一、概述与目标

项目背景：vue-admin-template 是一个极简的 Vue.js 后台管理基础模板，默认使用前端 Mock 数据模拟接口。

对接目标：

配置前端请求指向真实后端地址。
实现基于 JWT Token 的登录认证流程。
修改用户信息获取逻辑，匹配后端数据结构。
调整前端页面（如个人中心）和路由。

最终效果：前端能成功调用后端 API 完成登录、获取数据，并实现完整的权限控制流程。

后台效果演示

二、核心对接步骤

1. 配置后端 API 基础地址

前端通过环境变量 VUE_APP_BASE_API 控制请求的基础 URL。

打开项目根目录下的环境配置文件 .env.development（开发环境）。

修改变量值为你的后端 API 地址：

1 2	# 例如，后端服务运行在本地 8010 端口 VUE_APP_BASE_API = 'http://127.0.0.1:8010/api/admin/v1'

生产环境配置在 .env.production 文件中。

2. 修改登录认证逻辑

（1）调整登录接口 (src/api/user.js)
找到 login 函数，修改 url 和 method 以匹配后端登录接口。

export function login(data) {
  return request({
    url: '/auth/login/access-token', // 根据后端接口修改
    method: 'post',
    data // 通常包含 username/email 和 password
  })
}

（2）修改账号验证规则 (src/utils/validate.js)
默认模板验证用户名只能是 admin 或 editor。需要改为验证邮箱（或其他你的登录凭证）。

/**
 * 验证邮箱格式
 * @param {string} str
 * @returns {Boolean}
 */
export function validEmail(str) {
  const emailReg = /^(\w-*\.*)+@(\w-?)+(\.\w{2,})+$/
  return emailReg.test(str)
}

// 在 `src/views/login/index.vue` 中，将 `validUsername` 的调用替换为 `validEmail`

（3）调整 Axios 请求拦截器 (src/utils/request.js)
后端通常要求在请求头中携带 Token 进行认证。

// request interceptor
service.interceptors.request.use(
  config => {
    if (store.getters.token) {
      // 根据后端约定修改 header 字段名，例如 'Authorization' 或 'token'
      config.headers['token'] = getToken() // 将默认的 'X-Token' 改为 'token'
    }
    return config
  },
  error => {
    return Promise.reject(error)
  }
)

（4）调整 Axios 响应拦截器 (src/utils/request.js)
根据后端统一的响应格式修改成功/失败的判断逻辑。假设后端成功时 code 为 200。

service.interceptors.response.use(
  response => {
    const res = response.data

    // 判断请求是否成功（根据后端返回的 code）
    if (res.code !== 200) { // 将默认的 20000 改为 200
      // 处理错误...
      return Promise.reject(new Error(res.message || 'Error'))
    } else {
      return res // 直接返回 res，其中包含 data, code, message
    }
  },
  error => {
    // 处理 HTTP 错误...
    return Promise.reject(error)
  }
)

3. 处理用户信息

登录成功后，前端会请求用户信息。需要修改 Vuex 中的处理逻辑以匹配后端返回的数据结构。

**修改 src/store/modules/user.js**：
在 getInfo action 中，根据后端返回的字段名进行赋值。

// 假设后端返回数据格式: { code:200, data: { nickname: 'xxx', avatar: 'xxx' } }
getInfo({ commit, state }) {
  return new Promise((resolve, reject) => {
    getInfo(state.token).then(response => {
      const { data } = response

      if (!data) {
        reject('Verification failed, please Login again.')
      }

      const { nickname, avatar } = data // 解构出后端返回的字段

      commit('SET_NAME', nickname) // 修改字段映射
      commit('SET_AVATAR', avatar)
      resolve(data)
    }).catch(error => {
      reject(error)
    })
  })
}

三、页面与路由调整

1. 创建个人中心页面

在 src/views/ 目录下创建 profile 文件夹。
在文件夹内创建 index.vue 组件文件，作为个人中心主页。

2. 添加个人中心路由

在路由配置文件（如 src/router/index.js 或对应的模块文件）中添加路由。

{
  path: '/profile',
  component: Layout, // 使用主布局
  redirect: '/profile/index',
  hidden: true, // 不在侧边栏显示
  children: [
    {
      path: 'index',
      component: () => import('@/views/profile/index'),
      name: 'Profile',
      meta: { title: '个人中心', icon: 'user', noCache: true }
    }
  ]
}

3. 修改导航栏下拉菜单 (`src/layout/components/Navbar.vue`)

将用户下拉菜单中的链接指向首页和个人中心。

<template>
  <!- 简化示例 ->
  <router-link to="/">
    <el-dropdown-item>首页</el-dropdown-item>
  </router-link>
  <router-link to="/profile">
    <el-dropdown-item>我的主页</el-dropdown-item>
  </router-link>
  <el-dropdown-item divided @click.native="logout">
    <span style="display:block;">退出</span>
  </el-dropdown-item>
</template>

四、测试与验证

启动服务：确保后端 API 服务已运行。
登录测试：在前端登录页面，使用后端有效的账号（邮箱）和密码登录。观察网络请求，确认 Token 被正确设置和携带。
页面跳转：登录后，点击右上角用户头像，检查下拉菜单中的“我的主页”是否能正确跳转到个人中心页面。
数据请求：测试其他数据接口（如 Table 列表），确认能正常获取并渲染后端返回的数据。

五、关键注意事项

**跨域问题 (CORS)**：开发时，确保后端已正确配置 CORS，允许前端域名/端口进行跨域请求。
Token 存储与刷新：本文示例将 Token 存储在 Cookie 和 Vuex 中。生产环境需要考虑 Token 的自动刷新机制。
接口格式统一：确保前端 Axios 拦截器中关于响应成功 (code) 的判断与后端所有接口的返回格式严格一致。
路由权限：如果后端返回的用户角色/权限信息结构有变，需要同步修改 src/permission.js 和侧边栏生成逻辑。

六、参考资源

vue-element-admin 文档：https://panjiachen.gitee.io/vue-element-admin-site/zh/guide/
本文示例项目地址：https://www.charmcode.cn/article/2020-07-11_Vue_Jwt_FastAPI (作者个人网站)

Git子库

发表于 2020-04-29 更新于 2026-05-09 分类于 Git

原文链接:Git应用详解第十讲：Git子库：submodule与subtree

一个中大型项目往往会依赖几个模块，git提供了子库的概念。可以将这些子模块存放在不同的仓库中，通过submodule或subtree实现仓库的嵌套。本讲为Git应用详解的倒数第二讲，胜利离我们不远了！

一、`submodule`

submodule：子模块的意思，表示将一个版本库作为子库引入到另一个版本库中：

1.引入子库

需要使用如下命令：

`git submodule add 子库地址保存目录`

比如：

1	git submodule add git@github.com:AhuntSun/git_child.git mymodule

执行上述命令会将地址对应的远程仓库作为子库，保存到当前版本库的mymodule目录下：

随后查看当前版本库的状态：

可以发现新增了两个文件。查看其中的.gitmodules文件：

可以看到当前文件的路径和子模块的url，随后将这两个新增文件添加、提交并推送。在当前仓库git_parent对应的远程仓库中多出了两个文件：

其中mymodule文件夹上的3bd7f76 对应的是子仓库git_child中的最新提交：

点击mymodule文件夹，会自动跳转到子仓库中：

通过上述分析，可以得出结论：两个仓库已经关联起来了，并且仓库git_child为仓库git_parent的子仓库；

2.同步子库变化

当被依赖的子版本库发生变化时：在子版本库git_child中新增文件world.txt并提交到远程仓库：

这个时候依赖它的父版本库git_parent要如何感知这一变化呢？

方法一

这个时候git_parent只需要进入存放子库git_child的目录mymodule，执行git pull就能将子版本库git_child的更新拉取到本地：

方法二

当父版本库git_parent依赖的多个子版本库都发生变化时，可以采用如下方法遍历更新所有子库：首先回到版本库主目录，执行以下指令：

1	git submodule foreach git pull

该命令会遍历当前版本库所依赖的所有子版本库，并将它们的更新拉取到父版本库git_parent：

拉取完成后，查看状态，发现mymodule目录下文件发生了变化，所以需要执行一次添加、提交、推送操作：

3.复制父版本库

如果将使用了submodule添加依赖了子库的父版本库git_parent，克隆一份到本地的话。在克隆出来的新版本库git_parent2中，原父版本库存放依赖子库的目录虽在，但是内容不在：

进入根据git_parent复制出来的仓库git_parent2，会发现mymodule目录为空：

解决方法：可采用多条命令的分步操作，也可以通过参数将多步操作进行合并。

分步操作

这是在执行了clone操作后的额外操作，还需要做两件事：

手动初始化submodule：
1
git submodule init
手动拉取依赖的子版本库；：
1
git submodule update --recursive

执行完两步操作后，子版本库中就有内容了。由此完成了git_parent的克隆；

合并操作

分步操作相对繁琐，还可以通过添加参数的方式，将多步操作进行合并。通过以下指令基于git_parent克隆一份git_parent3：

1	git clone git@github.com:AhuntSun/git_parent.git git_parent3 --recursive

--recursive表示递归地克隆git_parent依赖的所有子版本库。

4.删除子版本库

git没有提供直接删除submodule子库的命令，但是我们可以通过其他指令的组合来达到这一目的，分为三步：

将submodule从版本库中删除：
1
git rm --cache mymodule

git rm的作用为删除版本库中的文件，并将这一操作纳入暂存区；

将submodule从工作区中删除；

最后将.gitmodules目录删除；

完成三步操作后，再进行添加，提交，推送即可完成删除子库的操作：

二、`subtree`

1.简介

subtree与submodule的作用是一样的，但是subtree出现得比submodule晚，它的出现是为了弥补submodule存在的问题：

第一：submodule不能在父版本库中修改子版本库的代码，只能在子版本库中修改，是单向的；
第二：submodule没有直接删除子版本库的功能；

而subtree则可以实现双向数据修改。官方推荐使用subtree替代submodule。

2.创建子库

首先创建两个版本库：git_subtree_parent和git_subtree_child然后在git_subtree_parent中执行git subtree会列出该指令的一些常见的参数：

3.建立关联

首先需要给git_subtree_parent添加一个子库git_subtree_child:

第一步：添加子库的远程地址：

1	git remote add subtree-origin git@github.com:AhuntSun/git_subtree_child.git

添加完成后，父版本库中就有两个远程地址了：

这里的subtree-origin就代表了远程仓库git_subtree_child的地址。

第二步：建立依赖关系：

1 2	git subtree add --prefix=subtree subtree-origin master --squash //其中的--prefix=subtree可以写成：--p subtree 或 --prefix subtree

该命令表示将远程地址为subtree-origin的，子版本库上master分支的，文件克隆到subtree目录下；

注意：是在某一分支（如master）上将subtree-origin代表的远程仓库的某一分支（如master）作为子库拉取到subtree文件夹中。可切换到其他分支重复上述操作，也就是说子库的实质就是子分支。

--squash是可选参数，它的含义是合并，压缩的意思。

如果不增加这个参数，则会把远程的子库中指定的分支（这里是master）中的提交一个一个地拉取到本地再去创建一个合并提交；
如果增加了这个参数，会将远程子库指定分支上的多次提交合并压缩成一次提交再拉取到本地，这样拉取到本地的，远程子库中的，指定分支上的，历史提交记录就没有了。

拉取完成后，父版本库中会增添一个subtree目录，里面是子库的文件，相当于把依赖的子库代码拉取到了本地：

此时查看一下父版本库的提交历史：

会发现其中没有子库李四的提交信息，这是因为--squash参数将他的提交压缩为一次提交，并由父版本库张三进行合并和提交。所以父版本库多出了两次提交。

随后，我们在父版本库中进行一次推送：

结果远程仓库中多出了一个存放子版本库文件的subtree目录，并且完全脱离了版本库git_subtree_child，仅仅是属于父版本库git_subtree_parent的一个目录。而不像使用submodule那样，是一个点击就会自动跳转到依赖子库的指针：

subtree的远程父版本库：

submodule的远程父版本库：

即submodule与subtree子库的区别为：

4.同步子库变化

在子库中创建一个新文件world并推送到远程子库：

在父库中通过如下指令更新依赖的子库内容：

1	git subtree pull --prefix=subtree subtree-origin master --squash

此时查看一下提交历史：

发现没有子库李四的提交信息，这都是--squash的作用。子库的修改交由父库来提交。

5.参数`--squash`

该参数的作用为：防止子库指定分支上的提交历史污染父版本库。比如在子库的master分支上进行了三次提交分别为：a、b、c，并推送到远程子库。

首先，复习一下合并分支时遵循的三方合并原则：

当提交4和6需要合并的时候，git会先寻找二者的公共父提交节点，如图中的2，然后在提交2的基础上进行2、4、6的三方合并，合并后得到提交7。

父仓库执行pull操作时：如果添加参数--squash，就会把远程子库master分支上的这三次提交合并为一次新的提交abc；随后再与父仓库中子库的master分支进行合并，又产生一次提交X。整个pull的过程一共产生了五次提交，如下图所示：

存在的问题：

由于--squash指令的合并操作，会导致远程master分支上的合并提交abc与本地master分支上的最新提交2，找不到公共父节点，从而合并失败。同时push操作也会出现额外的问题。

最佳实践：要么全部操作都使用--squash指令，要么全部操作都不使用该参数，这样就不会出错。

错误示范：

为了验证，重新创建两个仓库A和B，并通过subtree将B设置为A的子库。这次全程都没有使用参数--squash，重复上述操作：

首先，修改子库文件；
然后，通过下列指令，在不使用参数--squash的情况下，将远程子库A变化的文件拉取到本地：

1	git subtree pull --prefix=subtree subtree-origin master

此时查看提交历史：

可以看到子库儿子的提交信息污染了父版本库的提交信息，验证了上述的结论。

所以要么都使用该指令，要么都不使用才能避免错误；如果不需要子库的提交日志，推荐使用--squash指令。

补充：echo 'new line' >> test.txt：表示在test.txt文件末尾追加文本new line；如果是一个>表示替换掉test.txt内的全部内容。

6.修改子库

subtree的强大之处在于，它可以在父版本库中修改依赖的子版本库。以下为演示：

进入父版本库存放子库的subtree目录，修改子库文件child.txt，并推送到远程父仓库：

此时远程父版本库中存放子库文件的subtree目录发生了变化，但是独立的远程子库git_subtree_child并没有发生变化。

修改独立的远程子库：

可执行以下命令，同步地修改远程子版本库：
1
git subtree push --prefix=subtree subtree-origin master
如下图所示，父库中的子库文件child.txt新增的child2内容，同步到了独立的远程子库中：
修改独立的本地子库：

回到本地子库git_subtree_child，将对应的远程子库进行的修改拉取到本地进行合并同步：

由此无论是远程的还是本地的子库都被修改了。

实际上使用subtree后，在外部看起来父仓库和子仓库是一个整体的仓库。执行clone操作时，不会像submodule那样需要遍历子库来单独克隆。而是可以将整个父仓库和它所依赖的子库当做一个整体进行克隆。

存在的问题

父版本库拉取远程子库进行更新同步会出现的问题：

子仓库第一次修改：

经历了上述操作，本地子库与远程子库的文件达到了同步，其中文件child.txt的内容都是child~4。在此基础上本地子库为该文件添加child5~6：

然后推送到远程子库。
父仓库第一次拉取：

随后父版本库通过下述指令，拉取远程子库，与本地父仓库git_subtree_parent中的子库进行同步：
1
git subtree pull --p subtree subtree-origin master --squash
结果出现了合并失败的情况：

我们查看冲突产生的文件：

发现父版本库中的子库与远程子库内容上并无冲突，但是却发生了冲突，这是为什么呢？

探究冲突产生的原因之前我们先解决冲突，先删除多余的内容：

随后执行git add命令和git commit命令标识解决了冲突：

解决完冲突后将该文件推送到独立的远程子库，发现文件并没有发生更新，也就是说git认为我们并没有解决冲突：
子仓库第二次修改与父仓库第二次拉取：

再次修改本地子库的文件并推送到对应的远程仓库，父版本库再次将远程子库更新的文件拉取到本地进行同步：

这次却成功了！为什么同样的操作，有的时候成功有的时候失败呢？

解决方案

原因出现在--squash指令中。实际上，--squash指令把子库中的提交信息合并了，导致父仓库在执行git pull操作时找不到公共的父节点，从而导致即使文件没有冲突的内容，也会出现合并冲突的情况。其实不使用--squash也会有这种问题，问题的根本原因仍然是三方合并时找不到公共父节点。我们打开gitk：

从图中不难看出，当使用subtree时，子库与父库之间是没有公共节点的，所以时常会因为找不到公共节点而出现合并冲突的情况，此时只需要解决冲突，手动合并即可。

不使用subtree时，普通的版本库中的各分支总会有一个公共节点：

再次强调：使用--squash指令时一定要小心，要么都使用它，要么都不使用。

7.抽离子库

`git subtree split`

当开发过程中出现某些子库完全可以复用到其他项目中时，我们希望将它独立出来。

方法一：可以手动将文件拷贝出来。缺点是，这样会丢失关于该子库的提交记录；
方法二：

使用
1
git subtree split
指令，该指令会把关于独立出来的子库的每次提交都记录起来。但是，这样存在弊端：
- 比如该独立子库为company.util，当一次提交同时修改了company.util和company.server两个子库时。
- 通过上述命令独立出来的子库util只会记录对自身修改的提交，而不会记录对company.server的修改，这样在别人看来这次提交就只修改了util，这是不完整的。

C#时间戳

发表于 2020-04-28 更新于 2026-05-09 分类于编程技术， DotNet

来源：https://blog.guoqianfan.com/2019/11/24/timestamp-in-csharp/

什么是时间戳

时间戳默认是Unix时间戳。

首先要清楚JavaScript与Unix的时间戳的区别：

JavaScript时间戳：是指格林威治时间1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒)起至现在的总毫秒数。

Unix时间戳：是指格林威治时间1970年01月01日00时00分00秒(北京时间1970年01月01日08时00分00秒)起至现在的总秒数。

可以看出JavaScript时间戳是总毫秒数，Unix时间戳是总秒数。

比如同样是的 2016/11/03 12:30:00 ，转换为JavaScript时间戳为 1478147400000；转换为Unix时间戳为 1478147400。

从上面也可以看出时间戳与时区无关。

Unix时间戳相互转换

C# DateTime转换为Unix时间戳

.NET 4.6新方法

只能在 .NET 4.6及更高版本里才能使用。

1 2	long timeStamp = DateTimeOffset.Now.ToUnixTimeSeconds(); Console.WriteLine(timeStamp);

通用的老方法

1
2
3

System.DateTime startTime = TimeZone.CurrentTimeZone.ToLocalTime(new System.DateTime(1970, 1, 1)); 
long timeStamp = (long)(DateTime.Now - startTime).TotalSeconds; 
System.Console.WriteLine(timeStamp);

Unix时间戳转换为C# DateTime

.NET 4.6新方法

由时间戳转换的DateTimeOffset的时区默认是+00:00，此时我们需要转为本地时区，否则后续使用可能会有问题。

转为本地时区：DateTimeOffset.LocalDateTime。

示例代码如下：


DateTimeOffset dto = DateTimeOffset.FromUnixTimeMilliseconds(1573696406184);

DateTime dt01 = dto.DateTime;

DateTime dt02 = dto.LocalDateTime;

通用的老方法

long unixTimeStamp = 1478162177;
System.DateTime startTime = TimeZone.CurrentTimeZone.ToLocalTime(new System.DateTime(1970, 1, 1)); 
DateTime dt = startTime.AddSeconds(unixTimeStamp);
System.Console.WriteLine(dt.ToString("yyyy/MM/dd HH:mm:ss:ffff"));

备注

DateTimeOffset使用Now还是UtcNow

对于DateTimeOffset，发现有2个获取当前时间的属性：DateTimeOffset.Now和DateTimeOffset.UtcNow。

如果只是获取时间戳，这2个使用哪个都可以，得到的值是一样的。

因为DateTimeOffset里面有时区信息，获取时间戳时会使用时区进行转换的，所以获得的时间戳一样。

而也是因为时区的原因，DateTimeOffset的其他操作可能会不一样。例如DateTimeOffset.DateTime就不一样，此时推荐使用DateTimeOffset.LocalDateTime来获得本地时区的时间。

测试代码如下：


Console.WriteLine("none：{0}", DateTimeOffset.Now);

Console.WriteLine("utc：{0}", DateTimeOffset.UtcNow);


Console.WriteLine("none：{0}", DateTimeOffset.Now.ToUnixTimeSeconds());

Console.WriteLine("utc：{0}", DateTimeOffset.UtcNow.ToUnixTimeSeconds());

DateTime转换为DateTimeOffset

可以直接把DateTime赋值给DateTimeOffset，内部会自动进行隐式转换。这里涉及到时区，请往下看。

DateTime的时区信息(Kind属性)

DateTime的时区信息存放在Kind属性里。Kind属性的数据类型是DateTimeKind枚举，只有3个值：

Unspecified：未指定/未规定
Utc：UTC时间
Local：本地时区

不同情况下得到的DateTime的Kind是不同的，具体如下：

DateTime.Now：DateTime.Kind是 **Local(本地时区)**。
DateTime.UtcNow：DateTime.Kind是 **Utc**。
DateTime.Parse()：
- 【默认】在未指定时区时，DateTime.Kind是 Unspecified
- 指定时区：指定时区后DateTime.Kind就是相对应的值。
  
  指定时区有2种方式：
  - 【默认+优先】待转换的字符串里有时区信息。例如：2019/11/24 17:40:32 +08:00
  - 使用DateTimeStyles参数来指定时区。DateTimeStyles是枚举类型，更多信息自己查看定义，这里不再多说。

Local和Utc都会把相应的时区传递过去。对于 Unspecified(未指定)，会被当做本地时区来处理（结果已验证，源码没看懂）。

测试代码


DateTime dtNow = DateTime.Now;

DateTime dtUtcNow = DateTime.UtcNow;

DateTime dtParse = DateTime.Parse("2019-11-24 17:40:13");


DateTimeOffset dtoNow = dtNow;

DateTimeOffset dtoUtcNow = dtUtcNow;

DateTimeOffset dtoParse = dtParse;

Console.WriteLine("DateTime：");
Console.WriteLine("dtNow：{0}(Kind：{1})", dtNow, dtNow.Kind);
Console.WriteLine("dtUtcNow：{0}(Kind：{1})", dtUtcNow, dtUtcNow.Kind);
Console.WriteLine("dtParse：{0}(Kind：{1})", dtParse, dtParse.Kind);

Console.WriteLine();

Console.WriteLine("DateTimeOffset：");
Console.WriteLine("dtoNow：{0}", dtoNow);
Console.WriteLine("dtoUtcNow：{0}", dtoUtcNow);
Console.WriteLine("dtoParse：{0}", dtoParse);

输出结果如下：

DateTime：
dtNow：2019/11/24 17:40:32(Kind：Local)
dtUtcNow：2019/11/24 9:40:32(Kind：Utc)
dtParse：2019/11/24 17:40:13(Kind：Unspecified)

DateTimeOffset：
dtoNow：2019/11/24 17:40:32 +08:00
dtoUtcNow：2019/11/24 9:40:32 +00:00
dtoParse：2019/11/24 17:40:13 +08:00

DateTimeOffset.Parse的默认时区

DateTimeOffset.Parse的默认时区是当前时区。

1 2	Console.WriteLine("parse：{0}", DateTimeOffset.Parse("2019-6-14 15:38:49"));

参考

C# DateTime与时间戳转换：https://www.cnblogs.com/polk6/p/6024892.html
如何将Unix时间戳转换为DateTime，反之亦然？：https://stackoverflow.com/questions/249760/how-can-i-convert-a-unix-timestamp-to-datetime-and-vice-versa
DateTimeOffset源码：https://source.dot.net/#System.Private.CoreLib/DateTimeOffset.cs

一、核心概念：什么是内核模块？

内核模块（Kernel Module）是 Linux 内核的一种可动态加载/卸载的扩展组件。它们允许在不重新编译整个内核的情况下，为系统添加新的硬件支持、文件系统或内核功能。模块通常以 .ko（Kernel Object）为扩展名。

主要优势：

灵活性：按需加载，减少内核内存占用。
可维护性：更新驱动或功能时无需重启系统。
模块化：保持内核核心精简，通过模块扩展功能。

二、模块管理工具对比

Linux 提供了两套工具来管理内核模块，各有其适用场景。

工具	命令	特点	适用场景
智能管理工具	`modprobe`	1. 自动处理模块依赖关系 2. 使用模块名（无需路径） 3. 从标准模块目录搜索	日常使用首选，特别是加载复杂驱动
基础加载工具	`insmod`	1. 需指定模块完整路径 2. 不处理依赖关系 3. 直接系统调用	低级操作，调试或已知无依赖的简单模块
基础卸载工具	`rmmod`	1. 使用模块名卸载 2. 不处理依赖关系	卸载由 `insmod` 加载的模块
查看工具	`lsmod`	显示当前已加载的所有模块	状态检查

三、使用 `modprobe`（推荐方法）

modprobe 是智能化的模块管理工具，它会读取 /lib/modules/$(uname -r)/modules.dep 文件中的依赖关系，自动加载所需的所有模块。

3.1 准备工作：生成模块依赖关系

在首次使用或安装新模块后，建议先更新模块依赖数据库：

1	sudo depmod -a

此命令会扫描 /lib/modules/$(uname -r)/ 目录下的所有模块，生成 modules.dep 文件，其中记录了模块间的依赖关系。

3.2 加载模块

# 加载指定模块（自动处理依赖）
sudo modprobe vfat

# 加载所有模块（不常用）
sudo modprobe -a

注意：只需提供模块名（如 vfat），无需 .ko 后缀和路径。

3.3 卸载模块

1 2	# 卸载指定模块（自动尝试卸载依赖模块） sudo modprobe -r vfat

3.4 常用 `modprobe` 参数详解

参数	功能
`-a`, `--all`	加载所有模块。
`-r`, `--remove`	卸载指定模块。
`-l`, `--list`	列出所有可用模块（带完整路径）。
`-c`, `--show-conf`	显示所有模块的配置信息（如别名）。
`-d`, `--debug`	启用调试模式。
`-v`, `--verbose`	显示详细执行信息。
`--help`	显示帮助信息。

3.5 实用示例

# 1. 查看模块配置信息（如别名）
sudo modprobe -c | grep vfat
# 输出示例：alias fs-vfat vfat

# 2. 列出所有可用模块
sudo modprobe -l
# 输出示例：/lib/modules/5.4.0-xx/kernel/fs/vfat/vfat.ko

# 3. 带详细信息加载模块
sudo modprobe -v vfat

四、使用 `insmod` 与 `rmmod`（基础方法）

这对工具提供了更底层的控制，但需要手动处理依赖关系。

4.1 加载模块 (`insmod`)

1 2	# 必须指定模块的完整路径 sudo insmod /lib/modules/$(uname -r)/kernel/drivers/block/floppy.ko

关键限制：如果 floppy.ko 依赖其他模块（如特定总线驱动），insmod 会直接失败并报错，而不会自动加载依赖项。

4.2 卸载模块 (`rmmod`)

1 2	# 使用模块名（不含.ko后缀和路径） sudo rmmod floppy

重要：只能卸载当前未被使用且没有其他模块依赖的模块。

4.3 `insmod` 常用参数

参数	功能
`-f`	强制加载，忽略内核版本检查（危险）。
`-k`	将模块标记为“自动卸载”。
`-o <名称>`	指定加载后模块的名称（可不同于文件名）。
`-p`	仅测试模块是否能加载，不实际加载。
`-s`	将操作信息写入系统日志。
`-v`	显示详细信息。

示例：强制加载并输出详细信息

1	sudo insmod -f -v /path/to/module.ko

五、模块状态查看与系统集成

5.1 查看已加载模块

# 查看所有已加载模块
lsmod

# 配合grep过滤
lsmod | grep vfat

输出格式：

1
2
3

Module                  Size  Used by
vfat                   24576  0
fat                    73728  1 vfat

Module：模块名称。
Size：模块占用的内存大小（字节）。
Used by：被哪些模块或进程使用（数字表示引用计数）。

5.2 模块配置文件

模块的别名、黑名单等配置位于：

/etc/modprobe.d/ 目录下的 .conf 文件
/etc/modules-load.d/ 目录（定义启动时自动加载的模块）

示例：创建文件 /etc/modprobe.d/blacklist.conf 可禁用特定模块

1 2	# 禁用有问题的无线网卡驱动 blacklist acer_wmi

5.3 开机自动加载模块

方法一：编辑 /etc/modules 文件（传统方法）

sudo nano /etc/modules
# 添加模块名，每行一个
vfat
nvidia

方法二：使用 modules-load.d 目录（现代方法）

1
2
3

# 创建配置文件
echo "vfat" | sudo tee /etc/modules-load.d/vfat.conf
echo "nvidia" | sudo tee /etc/modules-load.d/nvidia.conf

六、故障排除与最佳实践

6.1 常见错误与解决

错误：insmod: ERROR: could not insert module: Invalid module format
原因：模块编译时的内核版本与当前运行内核不匹配。
解决：重新编译模块或寻找对应版本的模块。
错误：modprobe: FATAL: Module xxx not found
原因：模块未安装或不在标准搜索路径。
解决：
1. 检查模块是否存在：find /lib/modules -name "*.ko" | grep xxx
2. 运行 sudo depmod -a 更新数据库。
错误：rmmod: ERROR: Module xxx is in use
原因：模块正在被进程或其他模块使用。
解决：先停止相关进程，或使用 modprobe -r 尝试智能卸载。

6.2 依赖关系解析示例

假设模块 A.ko 依赖于 B.ko：

# 使用 insmod 会失败
sudo insmod /path/to/A.ko  # 失败：未加载 B.ko

# 需要先加载依赖
sudo insmod /path/to/B.ko
sudo insmod /path/to/A.ko  # 成功

# 使用 modprobe 自动处理
sudo modprobe A  # 自动先加载 B.ko，再加载 A.ko

6.3 最佳实践总结

**日常操作首选 modprobe**：让系统自动处理复杂的依赖关系。
**调试时使用 insmod/rmmod**：当需要精确控制加载顺序或排查依赖问题时。
始终更新依赖数据库：安装新内核或模块后，运行 sudo depmod -a。
检查模块使用情况：卸载前使用 lsmod | grep <模块名> 查看引用计数。
利用配置目录：将自定义设置放在 /etc/modprobe.d/ 中，便于管理。

七、总结对比

操作	`modprobe` 方式	`insmod/rmmod` 方式
加载模块	`sudo modprobe <模块名>`	`sudo insmod <完整路径>`
卸载模块	`sudo modprobe -r <模块名>`	`sudo rmmod <模块名>`
依赖处理	自动，读取 `modules.dep`	手动，需按顺序加载
模块查找	搜索标准目录（`/lib/modules/`）	需提供完整路径
适用场景	生产环境、日常管理	开发调试、低级操作

最终建议：对于大多数用户和管理员，modprobe 是更安全、便捷的选择。只有在深入了解模块依赖关系，或进行系统级调试时，才需要使用 insmod 和 rmmod 这对底层工具。

FreeBSD使用pkg包管理器完全指南

发表于 2019-12-26 更新于 2026-05-09

一、核心概念：Ports 与 Packages

FreeBSD 提供了两种安装第三方软件的方式：

方式	描述	特点
Ports Collection	从源代码编译安装。	高度可定制（可启用/禁用功能），但编译耗时。
Packages (pkg)	安装预编译的二进制包。	快速、便捷，是管理附加软件的首选方式。

关键路径差异：通过 pkg 安装的软件，其二进制文件和大多数配置文件位于 /usr/local/ 目录下（例如 /usr/local/bin, /usr/local/etc），这与 Linux 发行版常见的 /usr/ 和 /etc 不同。

二、安装与初始配置

1. 安装 `pkg` 工具

在全新的 FreeBSD 系统上，pkg 工具本身并未预装。首次使用任何 pkg 命令（如 pkg install）时，系统会提示你安装它：

1
2
3

pkg install wget
# 输出：The package management tool is not yet installed...
# 输入 `y` 确认安装。

也可以直接运行以下命令来引导安装：

1	pkg bootstrap

2. 配置文件 (`/usr/local/etc/pkg.conf`)

pkg 的行为可通过此文件进行全局定制。文件采用 UCL 格式，包含大量注释说明。

常用配置项：
- ASSUME_ALWAYS_YES: true：默认对所有确认提示回答“是”，适用于脚本。
- AUTOCLEAN: true：安装/升级后自动清理过时的缓存包。
定义命令别名：在文件底部的 ALIAS 部分，可以为常用命令组合创建快捷方式。
查看手册：man pkg.conf

三、日常包管理操作

1. 搜索软件包

在安装前，需要确定软件包的正确名称。

# 基本搜索（在包名和描述中查找）
pkg search apache

# 精确搜索并显示详细信息
pkg search -R apache24
# 输出包括：包名、版本、维护者、描述、依赖等。

2. 安装与卸载

# 安装软件包（及其依赖）
pkg install apache24

# 安装时不询问确认（适用于脚本）
pkg install -y nginx

# 卸载软件包
pkg delete nginx
# 或
pkg remove nginx

注意：卸载一个被其他包依赖的包时，依赖包也会被一同卸载。

3. 查询已安装的包

# 列出所有已安装的包
pkg info

# 查看特定包的详细信息
pkg info nginx

# 列出特定包安装的文件
pkg info -l nginx

# 查询某个文件由哪个包提供
pkg which /usr/local/bin/curl

4. 更新与升级

# 更新本地包仓库目录（非升级软件）
pkg update

# 升级所有已安装的包到最新版本
pkg upgrade

# 升级特定包
pkg upgrade nginx

四、高级管理与维护

1. 包缓存管理

pkg 会将下载的包文件缓存到 /var/cache/pkg。

# 仅下载包而不安装（可用于离线安装）
pkg fetch nginx
# 下载包及其所有依赖
pkg fetch -d nginx

# 清理已被新版替换的旧缓存包
pkg clean

# 清理所有缓存包
pkg clean -a

# 列出缓存内容
ls /var/cache/pkg

2. 锁定与解锁包

防止特定包被意外升级或删除。

# 锁定一个包
pkg lock openssl

# 列出所有被锁定的包
pkg lock -l

# 解锁一个包
pkg unlock openssl

# 锁定/解锁所有包
pkg lock -a
pkg unlock -a

3. 依赖与自动清理

# 移除不再被任何包依赖的“孤儿”包（自动包）
pkg autoremove

# 查看哪些包是手动安装的（非自动依赖）
pkg prime-list

4. 安全检查与验证

# 检查所有已安装包是否有已知安全漏洞
pkg audit -F

# 验证所有包的完整性
pkg check -saq

# 验证特定包的文件是否被修改
pkg check -s nginx

五、包仓库（Repository）配置

FreeBSD 的官方包仓库配置在 /etc/pkg/FreeBSD.conf。默认使用 quarterly 分支，更稳定。

FreeBSD: {
  url: "pkg+http://pkg.FreeBSD.org/${ABI}/quarterly",
  enabled: yes
}

切换分支：将 url 中的 quarterly 改为 latest 可获取最新的软件包（可能包含测试版）。
添加第三方仓库：在 /usr/local/etc/pkg/repos/ 目录下创建 .conf 文件。需确保 pkg.conf 中 REPO_DIRS 包含该路径。

六、命令速查与参考

任务	命令
安装	`pkg install <包名>`
卸载	`pkg delete <包名>`
搜索	`pkg search <关键词>`
列表	`pkg info`
更新仓库	`pkg update`
升级系统	`pkg upgrade`
清理缓存	`pkg clean`
自动移除孤儿包	`pkg autoremove`
安全检查	`pkg audit -F`
锁定包	`pkg lock <包名>`
获取帮助	`pkg help <子命令>`

七、重要文件与目录

路径	用途
`/usr/local/etc/pkg.conf`	`pkg` 主配置文件
`/etc/pkg/FreeBSD.conf`	官方 FreeBSD 包仓库配置
`/usr/local/etc/pkg/repos/`	自定义第三方仓库配置目录
`/var/cache/pkg/`	下载的包文件缓存目录
`/var/db/pkg/local.sqlite`	已安装包的注册数据库（切勿删除）
`/usr/local/`	通过 `pkg` 安装的软件根目录

总结：对于绝大多数 FreeBSD 系统管理任务，pkg 是管理第三方软件最有效、最推荐的工具。除非你需要特定的编译选项或软件尚未被打包，否则应优先使用 pkg 而非 Ports。

8种主要排序算法的CSharp实现

发表于 2019-11-30 更新于 2026-05-09 分类于学习笔记，排序算法

8种主要排序算法的C#实现

Excerpt
8种主要排序算法的实现及优化，包含选择排序，冒泡排序，插入排序，快速排序，归并排序，堆排序，希尔排序，基数排序。文末实际测试并比较。

新的一年到了，很多园友都辞职要去追求更好的工作环境，我也是其中一个，呵呵！

最近闲暇的时候我开始重温一些常用的算法。老早就买了《算法导论》，一直都没啃下去。

这本书确实很好，只是太难读了，总是读了几章就又读不下去了！工作上也几乎用不到。

我这段时间发现看这些排序算法比以前容易了很多，就借此机会将它们整理总结起来。

一是方便以后重温，二是可以应对笔试面试。同时也希望这篇博文可以帮助各位刚辞职和正在学习排序算法的园友。

PS：有可能实现的代码并不是最优的，如果有什么错误或者值得改进的地方，还请大家帮忙指出。

简介

排序算法是我们编程中遇到的最多的算法。目前主流的算法有8种。

平均时间复杂度从高到低依次是：

冒泡排序（o(n²)），选择排序（o(n²)），插入排序（o(n²)），堆排序（o(nlogn)），

归并排序（o(nlogn)），快速排序（o(nlogn)），希尔排序（o(n^1.25)），基数排序（o(n)）

这些平均时间复杂度是参照维基百科排序算法罗列的。

是计算的理论平均值，并不意味着你的代码实现能达到这样的程度。

例如希尔排序，时间复杂度是由选择的步长决定的。基数排序时间复杂度最小，

但我实现的基数排序的速度并不是最快的，后面的结果测试图可以看到。

本文代码实现使用的数据源类型为IList，这样可以兼容int[]和List(虽然int[]有ToList()，

List有ToArray()，哈哈！)。

选择排序

选择排序是我觉得最简单暴力的排序方式了。

以前刚接触排序算法的时候，感觉算法太多搞不清，唯独记得选择排序的做法及实现。

原理：找出参与排序的数组最大值，放到末尾（或找到最小值放到开头）维基入口

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> SelectSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count - <span>1</span>; i++<span>)
</span><span> 4</span> <span>            {
</span><span> 5</span>                 <span>int</span> min =<span> i;
</span><span> 6</span>                 <span>int</span> temp =<span> data[i];
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = i + <span>1</span>; j &lt; data.Count; j++<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &lt;<span> temp)
</span><span>10</span> <span>                    {
</span><span>11</span>                         min =<span> j;
</span><span>12</span>                         temp =<span> data[j];
</span><span>13</span> <span>                    }
</span><span>14</span> <span>                }
</span><span>15</span>                 <span>if</span> (min !=<span> i)
</span><span>16</span> <span>                    Swap(data, min, i);
</span><span>17</span> <span>            }
</span><span>18</span>         }

复制代码

过程解析：将剩余数组的最小数交换到开头。

冒泡排序

冒泡排序是笔试面试经常考的内容，虽然它是这些算法里排序速度最慢的（汗），后面有测试为证。

原理：从头开始，每一个元素和它的下一个元素比较，如果它大，就将它与比较的元素交换，否则不动。

这意味着，大的元素总是在向后慢慢移动直到遇到比它更大的元素。所以每一轮交换完成都能将最大值

冒到最后。维基入口

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 4</span> <span>            {
</span><span> 5</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; i; j++<span>)
</span><span> 6</span> <span>                {
</span><span> 7</span>                     <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span> 8</span>                         Swap(data, j, j + <span>1</span><span>);
</span><span> 9</span> <span>                }
</span><span>10</span> <span>            }
</span><span>11</span>         }

复制代码

过程解析：中需要注意的是j<i，每轮冒完泡必然会将最大值排到数组末尾，所以需要排序的数应该是在减少的。

很多网上版本每轮冒完泡后依然还是将所有的数进行第二轮冒泡即j<data.Count-1，这样会增加比较次数。

通过标识提升冒泡排序

在维基上看到，可以通过添加标识来分辨剩余的数是否已经有序来减少比较次数。感觉很有意思，可以试试。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleSortImprovedWithFlag(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>bool</span><span> flag;
</span><span> 4</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 flag = <span>true</span><span>;
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; i; j++<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span>10</span> <span>                    {
</span><span>11</span>                         Swap(data, j, j + <span>1</span><span>);
</span><span>12</span>                         flag = <span>false</span><span>;
</span><span>13</span> <span>                    }
</span><span>14</span> <span>                }
</span><span>15</span>                 <span>if</span> (flag) <span>break</span><span>;
</span><span>16</span> <span>            }
</span><span>17</span>         }

复制代码

过程解析：发现某轮冒泡没有任何数进行交换（即已经有序），就跳出排序。

我起初也以为这个方法是应该有不错效果的，可是实际测试结果并不如想的那样。和未优化耗费时间一样（对于随机数列）。

由果推因，那么应该是冒泡排序对于随机数列，当剩余数列有序的时候，也没几个数要排列了！？

不过如果已经是有序数列或者部分有序的话，这个冒泡方法将会提升很大速度。

鸡尾酒排序（来回排序）

对冒泡排序进行更大的优化

冒泡排序只是单向冒泡，而鸡尾酒来回反复双向冒泡。

原理：自左向右将大数冒到末尾，然后将剩余数列再自右向左将小数冒到开头，如此循环往复。维基入口

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BubbleCocktailSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>bool</span><span> flag;
</span><span> 4</span>             <span>int</span> m = <span>0</span>, n = <span>0</span><span>;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = data.Count - <span>1</span>; i &gt; <span>0</span>; i--<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 flag = <span>true</span><span>;
</span><span> 8</span>                 <span>if</span> (i % <span>2</span> == <span>0</span><span>)
</span><span> 9</span> <span>                {
</span><span>10</span>                     <span>for</span> (<span>int</span> j = n; j &lt; data.Count - <span>1</span> - m; j++<span>)
</span><span>11</span> <span>                    {
</span><span>12</span>                         <span>if</span> (data[j] &gt; data[j + <span>1</span><span>])
</span><span>13</span> <span>                        {
</span><span>14</span>                             Swap(data, j, j + <span>1</span><span>);
</span><span>15</span>                             flag = <span>false</span><span>;
</span><span>16</span> <span>                        }
</span><span>17</span> <span>                    }
</span><span>18</span>                     <span>if</span> (flag) <span>break</span><span>;
</span><span>19</span>                     m++<span>;
</span><span>20</span> <span>                }
</span><span>21</span>                 <span>else</span>
<span>22</span> <span>                {
</span><span>23</span>                     <span>for</span> (<span>int</span> k = data.Count - <span>1</span> - m; k &gt; n; k--<span>)
</span><span>24</span> <span>                    {
</span><span>25</span>                         <span>if</span> (data[k] &lt; data[k - <span>1</span><span>])
</span><span>26</span> <span>                        {
</span><span>27</span>                             Swap(data, k, k - <span>1</span><span>);
</span><span>28</span>                             flag = <span>false</span><span>;
</span><span>29</span> <span>                        }
</span><span>30</span> <span>                    }
</span><span>31</span>                     <span>if</span> (flag) <span>break</span><span>;
</span><span>32</span>                     n++<span>;
</span><span>33</span> <span>                }
</span><span>34</span> <span>            }
</span><span>35</span>         }

复制代码

过程解析：分析第i轮冒泡，i是偶数则将剩余数列最大值向右冒泡至末尾，是奇数则将剩余数列最小值

向左冒泡至开头。对于剩余数列，n为始，data.Count-1-m为末。

来回冒泡比单向冒泡：对于随机数列，更容易得到有序的剩余数列。因此这里使用标识将会提升的更加明显。

插入排序

插入排序是一种对于有序数列高效的排序。非常聪明的排序。只是对于随机数列，效率一般，交换的频率高。

原理：通过构建有序数列，将未排序的数从后向前比较，找到合适位置并插入。维基入口

第一个数当作有序数列。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> InsertSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 temp =<span> data[i];
</span><span> 7</span>                 <span>for</span> (<span>int</span> j = i - <span>1</span>; j &gt;= <span>0</span>; j--<span>)
</span><span> 8</span> <span>                {
</span><span> 9</span>                     <span>if</span> (data[j] &gt;<span> temp)
</span><span>10</span> <span>                    {
</span><span>11</span>                         data[j + <span>1</span>] =<span> data[j];
</span><span>12</span>                         <span>if</span> (j == <span>0</span><span>)
</span><span>13</span> <span>                        {
</span><span>14</span>                             data[<span>0</span>] =<span> temp;
</span><span>15</span>                             <span>break</span><span>;
</span><span>16</span> <span>                        }
</span><span>17</span> <span>                    }
</span><span>18</span>                     <span>else</span>
<span>19</span> <span>                    {
</span><span>20</span>                         data[j + <span>1</span>] =<span> temp;
</span><span>21</span>                         <span>break</span><span>;
</span><span>22</span> <span>                    }
</span><span>23</span> <span>                }
</span><span>24</span> <span>            }
</span><span>25</span>         }

复制代码

过程解析：将要排序的数（索引为i）存储起来，向前查找合适位置j+1，将i-1到j+1的元素依次向后

移动一位，空出j+1，然后将之前存储的值放在这个位置。

这个方法写的不如维基上的简洁清晰，由于合适位置是j+1所以多出了对j==0的判断，但实际效率影响无差别。

建议比照维基和我写的排序，自行选择。

二分查找法优化插入排序

插入排序主要工作是在有序的数列中对要排序的数查找合适的位置，而查找里面经典的二分查找法正可以适用。

原理：通过二分查找法的方式找到一个位置索引。当要排序的数插入这个位置时，大于前一个数，小于后一个数。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> InsertSortImprovedWithBinarySearch(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>int</span><span> tempIndex;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 temp =<span> data[i];
</span><span> 8</span>                 tempIndex = BinarySearchForInsertSort(data, <span>0</span><span>, i, i);
</span><span> 9</span>                 <span>for</span> (<span>int</span> j = i - <span>1</span>; j &gt;= tempIndex; j--<span>)
</span><span>10</span> <span>                {
</span><span>11</span>                     data[j + <span>1</span>] =<span> data[j];
</span><span>12</span> <span>                }
</span><span>13</span>                 data[tempIndex] =<span> temp;
</span><span>14</span> <span>            }
</span><span>15</span> <span>        }
</span><span>16</span> 
<span>17</span>         <span>public</span> <span>static</span> <span>int</span> BinarySearchForInsertSort(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span> high, <span>int</span><span> key)
</span><span>18</span> <span>        {
</span><span>19</span>             <span>if</span> (low &gt;= data.Count - <span>1</span><span>)
</span><span>20</span>                 <span>return</span> data.Count - <span>1</span><span>;
</span><span>21</span>             <span>if</span> (high &lt;= <span>0</span><span>)
</span><span>22</span>                 <span>return</span> <span>0</span><span>;
</span><span>23</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span>24</span>             <span>if</span> (mid == key) <span>return</span><span> mid;
</span><span>25</span>             <span>if</span> (data[key] &gt;<span> data[mid])
</span><span>26</span> <span>            {
</span><span>27</span>                 <span>if</span> (data[key] &lt; data[mid + <span>1</span><span>])
</span><span>28</span>                     <span>return</span> mid + <span>1</span><span>;
</span><span>29</span>                 <span>return</span> BinarySearchForInsertSort(data, mid + <span>1</span><span>, high, key);
</span><span>30</span> <span>            }
</span><span>31</span>             <span>else  <span>// data[key] &lt;= data[mid]</span></span>
<span>32</span> <span>            {
</span><span>33</span>                 <span>if</span> (mid - <span>1</span> &lt; <span>0</span>) <span>return</span> <span>0</span><span>;
</span><span>34</span>                 <span>if</span> (data[key] &gt; data[mid - <span>1</span><span>])
</span><span>35</span>                     <span>return</span><span> mid;
</span><span>36</span>                 <span>return</span> BinarySearchForInsertSort(data, low, mid - <span>1</span><span>, key);
</span><span>37</span> <span>            }
</span><span>38</span>         }

复制代码

过程解析：需要注意的是二分查找方法实现中high-low==1的时候mid==low，所以需要33行

mid-1<0即mid==0的判断，否则下行会索引越界。

快速排序

快速排序是一种有效比较较多的高效排序。它包含了“分而治之”以及“哨兵”的思想。

原理：从数列中挑选一个数作为“哨兵”，使比它小的放在它的左侧，比它大的放在它的右侧。将要排序是数列递归地分割到

最小数列，每次都让分割出的数列符合“哨兵”的规则，自然就将数列变得有序。维基入口

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortStrict(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortStrict(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp =<span> data[low];
</span><span>10</span>             <span>int</span> i = low + <span>1</span>, j =<span> high;
</span><span>11</span>             <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>            {
</span><span>13</span>                 <span>while</span> (data[j] &gt; temp) j--<span>;
</span><span>14</span>                 <span>while</span> (data[i] &lt; temp &amp;&amp; i &lt; j) i++<span>;
</span><span>15</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>16</span> <span>                Swap(data, i, j);
</span><span>17</span>                 i++; j--<span>;
</span><span>18</span> <span>            }
</span><span>19</span>             <span>if</span> (j !=<span> low)
</span><span>20</span> <span>                Swap(data, low, j);
</span><span>21</span>             QuickSortStrict(data, j + <span>1</span><span>, high);
</span><span>22</span>             QuickSortStrict(data, low, j - <span>1</span><span>);
</span><span>23</span>         }

复制代码

过程解析：取的哨兵是数列的第一个值，然后从第二个和末尾同时查找，左侧要显示的是小于哨兵的值，

所以要找到不小于的i，右侧要显示的是大于哨兵的值，所以要找到不大于的j。将找到的i和j的数交换，

这样可以减少交换次数。i>=j时，数列全部查找了一遍，而不符合条件j必然是在小的那一边，而哨兵

是第一个数，位置本应是小于自己的数。所以将哨兵与j交换，使符合“哨兵”的规则。

这个版本的缺点在于如果是有序数列排序的话，递归次数会很可怕的。

另一个版本

这是维基上的一个C#版本，我觉得很有意思。这个版本并没有严格符合“哨兵”的规则。但却将“分而治之”

以及“哨兵”思想融入其中，代码简洁。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortRelax(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelax(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp = data[(low + high) / <span>2</span><span>];
</span><span>10</span>             <span>int</span> i = low - <span>1</span>, j = high + <span>1</span><span>;
</span><span>11</span>             <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>            {
</span><span>13</span>                 <span>while</span> (data[++i] &lt;<span> temp) ;
</span><span>14</span>                 <span>while</span> (data[--j] &gt;<span> temp) ;
</span><span>15</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>16</span> <span>                Swap(data, i, j);
</span><span>17</span> <span>            }
</span><span>18</span>             QuickSortRelax(data, j + <span>1</span><span>, high);
</span><span>19</span>             QuickSortRelax(data, low, i - <span>1</span><span>);
</span><span>20</span>         }

复制代码

过程解析：取的哨兵是数列中间的数。将数列分成两波，左侧小于等于哨兵，右侧大于等于哨兵。

也就是说，哨兵不一定处于两波数的中间。虽然哨兵不在中间，但不妨碍“哨兵”的思想的实现。所以

这个实现也可以达到快速排序的效果。但却造成了每次递归完成，要排序的数列数总和没有减少（除非i==j）。

针对这个版本的缺点，我进行了优化

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             QuickSortRelaxImproved(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span> <span>        }
</span><span> 5</span> 
<span> 6</span>         <span>public</span> <span>static</span> <span>void</span> QuickSortRelaxImproved(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 7</span> <span>        {
</span><span> 8</span>             <span>if</span> (low &gt;= high) <span>return</span><span>;
</span><span> 9</span>             <span>int</span> temp = data[(low + high) / <span>2</span><span>];
</span><span>10</span>             <span>int</span> i = low - <span>1</span>, j = high + <span>1</span><span>;
</span><span>11</span>             <span>int</span> index = (low + high) / <span>2</span><span>;
</span><span>12</span>             <span>while</span> (<span>true</span><span>)
</span><span>13</span> <span>            {
</span><span>14</span>                 <span>while</span> (data[++i] &lt;<span> temp) ;
</span><span>15</span>                 <span>while</span> (data[--j] &gt;<span> temp) ;
</span><span>16</span>                 <span>if</span> (i &gt;= j) <span>break</span><span>;
</span><span>17</span> <span>                Swap(data, i, j);
</span><span>18</span>                 <span>if</span> (i == index) index =<span> j;
</span><span>19</span>                 <span>else</span> <span>if</span> (j == index) index =<span> i;
</span><span>20</span> <span>            }
</span><span>21</span>             <span>if</span> (j ==<span> i)
</span><span>22</span> <span>            {
</span><span>23</span>                 QuickSortRelaxImproved(data, j + <span>1</span><span>, high);
</span><span>24</span>                 QuickSortRelaxImproved(data, low, i - <span>1</span><span>);
</span><span>25</span> <span>            }
</span><span>26</span>             <span>else</span> <span>//</span><span>i-j==1</span>
<span>27</span> <span>            {
</span><span>28</span>                 <span>if</span> (index &gt;=<span> i)
</span><span>29</span> <span>                {
</span><span>30</span>                     <span>if</span> (index !=<span> i)
</span><span>31</span> <span>                        Swap(data, index, i);
</span><span>32</span>                     QuickSortRelaxImproved(data, i + <span>1</span><span>, high);
</span><span>33</span>                     QuickSortRelaxImproved(data, low, i - <span>1</span><span>);
</span><span>34</span> <span>                }
</span><span>35</span>                 <span>else <span>//</span><span>index &lt; i</span></span>
<span>36</span> <span>                {
</span><span>37</span>                     <span>if</span> (index !=<span> j)
</span><span>38</span> <span>                        Swap(data, index, j);
</span><span>39</span>                     QuickSortRelaxImproved(data, j + <span>1</span><span>, high);
</span><span>40</span>                     QuickSortRelaxImproved(data, low, j - <span>1</span><span>);
</span><span>41</span> <span>                }
</span><span>42</span> <span>            }
</span><span>43</span>         }

复制代码

过程解析：定义了一个变量Index，来跟踪哨兵的位置。发现哨兵最后在小于自己的那堆，

那就与j交换，否则与i交换。达到每次递归都能减少要排序的数列数总和的目的。

归并排序

归并排序也是采用“分而治之”的方式。刚发现分治法是一种算法范式，我还一直以为是一种需要意会的思想呢。

不好意思了，孤陋寡闻了，哈哈！

原理：将两个有序的数列，通过比较，合并为一个有序数列。维基入口

为方便理解，此处实现用了List的一些方法，随后有IList版本。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> List&lt;<span>int</span>&gt; MergeSortOnlyList(List&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>if</span> (low ==<span> high)
</span><span> 4</span>                 <span>return</span> <span>new</span> List&lt;<span>int</span>&gt;<span> { data[low] };
</span><span> 5</span>             List&lt;<span>int</span>&gt; mergeData = <span>new</span> List&lt;<span>int</span>&gt;<span>();
</span><span> 6</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span> 7</span>             List&lt;<span>int</span>&gt; leftData =<span> MergeSortOnlyList(data, low, mid);
</span><span> 8</span>             List&lt;<span>int</span>&gt; rightData = MergeSortOnlyList(data, mid + <span>1</span><span>, high);
</span><span> 9</span>             <span>int</span> i = <span>0</span>, j = <span>0</span><span>;
</span><span>10</span>             <span>while</span> (<span>true</span><span>)
</span><span>11</span> <span>            {
</span><span>12</span>                 <span>if</span> (leftData[i] &lt;<span> rightData[j])
</span><span>13</span> <span>                {
</span><span>14</span> <span>                    mergeData.Add(leftData[i]);
</span><span>15</span>                     <span>if</span> (++i ==<span> leftData.Count)
</span><span>16</span> <span>                    {
</span><span>17</span>                         mergeData.AddRange(rightData.GetRange(j, rightData.Count -<span> j));
</span><span>18</span>                         <span>break</span><span>;
</span><span>19</span> <span>                    }
</span><span>20</span> <span>                }
</span><span>21</span>                 <span>else</span>
<span>22</span> <span>                {
</span><span>23</span> <span>                    mergeData.Add(rightData[j]);
</span><span>24</span>                     <span>if</span> (++j ==<span> rightData.Count)
</span><span>25</span> <span>                    {
</span><span>26</span>                         mergeData.AddRange(leftData.GetRange(i, leftData.Count -<span> i));
</span><span>27</span>                         <span>break</span><span>;
</span><span>28</span> <span>                    }
</span><span>29</span> <span>                }
</span><span>30</span> <span>            }
</span><span>31</span>             <span>return</span><span> mergeData;
</span><span>32</span> <span>        }
</span><span>33</span> 
<span>34</span>         <span>public</span> <span>static</span> List&lt;<span>int</span>&gt; MergeSortOnlyList(List&lt;<span>int</span>&gt;<span> data)
</span><span>35</span> <span>        {
</span><span>36</span>             data = MergeSortOnlyList(data, <span>0</span>, data.Count - <span>1</span><span>);  <span>//不会改变外部引用 参照<a href="http://www.cnblogs.com/fatbird/p/parametersInCsharp.html" target="_blank">C#参数传递
</a></span></span><span>37</span>             <span>return</span><span> data;
</span><span>38</span>         }

复制代码

过程解析：将数列分为两部分，分别得到两部分数列的有序版本，然后逐个比较，将比较出的小数逐个放进

新的空数列中。当一个数列放完后，将另一个数列剩余数全部放进去。

IList版本

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; MergeSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             data = MergeSort(data, <span>0</span>, data.Count - <span>1</span><span>);
</span><span> 4</span>             <span>return</span><span> data;
</span><span> 5</span> <span>        }
</span><span> 6</span> 
<span> 7</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; MergeSort(IList&lt;<span>int</span>&gt; data, <span>int</span> low, <span>int</span><span> high)
</span><span> 8</span> <span>        {
</span><span> 9</span>             <span>int</span> length = high - low + <span>1</span><span>;
</span><span>10</span>             IList&lt;<span>int</span>&gt; mergeData =<span> NewInstance(data, length);
</span><span>11</span>             <span>if</span> (low ==<span> high)
</span><span>12</span> <span>            {
</span><span>13</span>                 mergeData[<span>0</span>] =<span> data[low];
</span><span>14</span>                 <span>return</span><span> mergeData;
</span><span>15</span> <span>            }
</span><span>16</span>             <span>int</span> mid = (low + high) / <span>2</span><span>;
</span><span>17</span>             IList&lt;<span>int</span>&gt; leftData =<span> MergeSort(data, low, mid);
</span><span>18</span>             IList&lt;<span>int</span>&gt; rightData = MergeSort(data, mid + <span>1</span><span>, high);
</span><span>19</span>             <span>int</span> i = <span>0</span>, j = <span>0</span><span>;
</span><span>20</span>             <span>while</span> (<span>true</span><span>)
</span><span>21</span> <span>            {
</span><span>22</span>                 <span>if</span> (leftData[i] &lt;<span> rightData[j])
</span><span>23</span> <span>                {
</span><span>24</span>                     mergeData[i + j] = leftData[i++]; <span>//</span><span>不能使用Add,Array Length不可变</span>
<span>25</span>                     <span>if</span> (i ==<span> leftData.Count)
</span><span>26</span> <span>                    {
</span><span>27</span>                         <span>int</span> rightLeft = rightData.Count -<span> j;
</span><span>28</span>                         <span>for</span> (<span>int</span> m = <span>0</span>; m &lt; rightLeft; m++<span>)
</span><span>29</span> <span>                        {
</span><span>30</span>                             mergeData[i + j] = rightData[j++<span>];
</span><span>31</span> <span>                        }
</span><span>32</span>                         <span>break</span><span>;
</span><span>33</span> <span>                    }
</span><span>34</span> <span>                }
</span><span>35</span>                 <span>else</span>
<span>36</span> <span>                {
</span><span>37</span>                     mergeData[i + j] = rightData[j++<span>];
</span><span>38</span>                     <span>if</span> (j ==<span> rightData.Count)
</span><span>39</span> <span>                    {
</span><span>40</span>                         <span>int</span> leftleft = leftData.Count -<span> i;
</span><span>41</span>                         <span>for</span> (<span>int</span> n = <span>0</span>; n &lt; leftleft; n++<span>)
</span><span>42</span> <span>                        {
</span><span>43</span>                             mergeData[i + j] = leftData[i++<span>];
</span><span>44</span> <span>                        }
</span><span>45</span>                         <span>break</span><span>;
</span><span>46</span> <span>                    }
</span><span>47</span> <span>                }
</span><span>48</span> <span>            }
</span><span>49</span>             <span>return</span><span> mergeData;
</span><span>50</span> 
<span>51</span>         }

复制代码

过程原理与上个一样，此处就不赘述了。

堆排序

堆排序是根据堆这种数据结构设计的一种算法。堆的特性：父节点的值总是小于（或大于）它的子节点。近似二叉树。

原理：将数列构建为最大堆数列（即父节点总是最大值），将最大值（即根节点）交换到数列末尾。这样要排序的数列数总和减少，

同时根节点不再是最大值，调整最大堆数列。如此重复，最后得到有序数列。维基入口有趣的演示

实现准备：如何将数列构造为堆——父节点i的左子节点为2i+1，右子节点为2i+2。节点i的父节点为floor((i-1)/2)。

实现如下（这个实现判断和临时变量使用太多，导致效率低，评论中@小城故事提出了更好的实现）：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> HeapSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span> <span>            BuildMaxHeapify(data);
</span><span> 4</span>             <span>int</span> j =<span> data.Count;
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt;<span> j; )
</span><span> 6</span> <span>            {
</span><span> 7</span>                 Swap(data, i, --<span>j);
</span><span> 8</span>                 <span>if</span> (j - <span>2</span> &lt; <span>0</span><span>)  <span>//只剩下1个数 j代表余下要排列的数的个数
</span></span><span> 9</span>                     <span>break</span><span>;
</span><span>10</span>                 <span>int</span> k = <span>0</span><span>;
</span><span>11</span>                 <span>while</span> (<span>true</span><span>)
</span><span>12</span> <span>                {
</span><span>13</span>                     <span>if</span> (k &gt; (j - <span>2</span>) / <span>2</span>) <span>break</span><span>;  <span>//即：k &gt; ((j-1)-1)/2</span> <span>超出最后一个父节点的位置  
</span></span><span>14</span>                     <span>else</span>
<span>15</span> <span>                    {
</span><span>16</span>                         <span>int</span> temp =<span> k;
</span><span>17</span>                         k = ReSortMaxBranch(data, k, <span>2</span> * k + <span>1</span>, <span>2</span> * k + <span>2</span>, j - <span>1</span><span>);
</span><span>18</span>                         <span>if</span> (temp == k) <span>break</span><span>;
</span><span>19</span> <span>                    }
</span><span>20</span> <span>                }
</span><span>21</span> <span>            }
</span><span>22</span> <span>        }
</span><span>23</span> 
<span>24</span>         <span>public</span> <span>static</span> <span>void</span> BuildMaxHeapify(IList&lt;<span>int</span>&gt;<span> data)
</span><span>25</span> <span>        {
</span><span>26</span>             <span>for</span> (<span>int</span> i = data.Count / <span>2</span> - <span>1</span>; i &gt;= <span>0</span>; i--<span>)  <span>//(data.Count-1)-1)/2为数列最大父节点索引
</span></span><span>27</span> <span>            {
</span><span>28</span>                 <span>int</span> temp =<span> i;
</span><span>29</span>                 temp = ReSortMaxBranch(data, i, <span>2</span> * i + <span>1</span>, <span>2</span> * i + <span>2</span>, data.Count - <span>1</span><span>);
</span><span>30</span>                 <span>if</span> (temp !=<span> i)
</span><span>31</span> <span>                {
</span><span>32</span>                     <span>int</span> k =<span> i;
</span><span>33</span>                     <span>while</span> (k != temp &amp;&amp; temp &lt;= data.Count / <span>2</span> - <span>1</span><span>)
</span><span>34</span> <span>                    {
</span><span>35</span>                         k =<span> temp;
</span><span>36</span>                         temp = ReSortMaxBranch(data, temp, <span>2</span> * temp + <span>1</span>, <span>2</span> * temp + <span>2</span>, data.Count - <span>1</span><span>);
</span><span>37</span> <span>                    }
</span><span>38</span> <span>                }
</span><span>39</span> <span>            }
</span><span>40</span> <span>        }
</span><span>41</span> 
<span>42</span>         <span>public</span> <span>static</span> <span>int</span> ReSortMaxBranch(IList&lt;<span>int</span>&gt; data, <span>int</span> maxIndex, <span>int</span> left, <span>int</span> right, <span>int</span><span> lastIndex)
</span><span>43</span> <span>        {
</span><span>44</span>             <span>int</span><span> temp;
</span><span>45</span>             <span>if</span> (right &gt;<span> lastIndex)  <span>//父节点只有一个子节点
</span></span><span>46</span>                 temp =<span> left;
</span><span>47</span>             <span>else</span>
<span>48</span> <span>            {
</span><span>49</span>                 <span>if</span> (data[left] &gt;<span> data[right])
</span><span>50</span>                     temp =<span> left;
</span><span>51</span>                 <span>else</span> temp =<span> right;
</span><span>52</span> <span>            }
</span><span>53</span> 
<span>54</span>             <span>if</span> (data[maxIndex] &lt;<span> data[temp])
</span><span>55</span> <span>                Swap(data, maxIndex, temp);
</span><span>56</span>             <span>else</span> temp =<span> maxIndex;
</span><span>57</span>             <span>return</span><span> temp;
</span><span>58</span>         }

复制代码

过程解析：BuildMaxHeapify为排序前构建的最大堆数列方法，主要内容为从最后一个父节点开始往前将每个三角组合

（即父节点与它的两个子节点）符合父节点值最大的规则。ReSortMaxBranch为将三角调整为父节点值最大，

并返回该值之前的索引，用来判断是否进行了交换，以及原来的父节点值交换到了什么位置。在HeapSort里首先

构建了最大堆数列，然后将根节点交换到末尾，根节点不是最大值了，在while语句中对最大堆数列进行调整。

插曲：自从看了Martin Fowler大师《重构》第三版，我发现我更不喜欢写注释了。每次都想着尽量让方法的名字更贴切，

即使会造成方法的名字很长很丑。这算不算曲解了大师的意思啊！？上面的代码注释都是写博客的时候现加的（源代码很干净的。汗!）。

希尔排序

希尔排序是插入排序的一种更高效的改进版本。

在前面介绍的插入排序，我们知道1.它对有序数列排序的效率是非常高的 2.要排序的数向前移动是一步步进行的导致插入排序效率低。

希尔排序正是利用第一点，改善第二点，达到更理想的效果。

原理：通过奇妙的步长，插入排序间隔步长的元素，随后逐渐缩短步长至1，实现数列的插入排序。维基入口

疑问：可以想象到排序间隔步长的数，会逐渐让数列变得有序，提升最后步长为1时标准插入排序的效率。在维基上看到这么

一句话“可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的”注意用词是‘可能’。我的疑问是

这是个正确的命题吗？如何证明呢？看维基上也是由果推因，说是如果不是这样，就不会排序那么快了。可这我感觉还是太牵强了，

哪位大哥发现相关资料，希望能分享出来，不胜感激。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> ShellSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> gap = data.Count / <span>2</span>; gap &gt; <span>0</span>; gap /= <span>2</span><span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>for</span> (<span>int</span> i = gap; i &lt; data.Count; i +=<span> gap)
</span><span> 7</span> <span>                {
</span><span> 8</span>                     temp =<span> data[i];
</span><span> 9</span>                     <span>for</span> (<span>int</span> j = i - gap; j &gt;= <span>0</span>; j -=<span> gap)
</span><span>10</span> <span>                    {
</span><span>11</span>                         <span>if</span> (data[j] &gt;<span> temp)
</span><span>12</span> <span>                        {
</span><span>13</span>                             data[j + gap] =<span> data[j];
</span><span>14</span>                             <span>if</span> (j == <span>0</span><span>)
</span><span>15</span> <span>                            {
</span><span>16</span>                                 data[j] =<span> temp;
</span><span>17</span>                                 <span>break</span><span>;
</span><span>18</span> <span>                            }
</span><span>19</span> <span>                        }
</span><span>20</span>                         <span>else</span>
<span>21</span> <span>                        {
</span><span>22</span>                             data[j + gap] =<span> temp;
</span><span>23</span>                             <span>break</span><span>;
</span><span>24</span> <span>                        }
</span><span>25</span> <span>                    }
</span><span>26</span> <span>                }
</span><span>27</span> <span>            }
</span><span>28</span>         }

复制代码

过程解析：采用的步长是N/2，每次取半，直至1。循环内部就是标准的插入排序。

——————

修正：修正后希尔排序才是真正牛叉的希尔啊！感谢@390218462的提出

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> ShellSortCorrect(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span><span> temp;
</span><span> 4</span>             <span>for</span> (<span>int</span> gap = data.Count / <span>2</span>; gap &gt; <span>0</span>; gap /= <span>2</span><span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>for</span> (<span>int</span> i = gap; i &lt; data.Count; <span>i++</span><span>)      // <span>i+ = gap 改为了 i++
</span></span><span> 7</span> <span>                {
</span><span> 8</span>                     temp =<span> data[i];
</span><span> 9</span>                     <span>for</span> (<span>int</span> j = i - gap; j &gt;= <span>0</span>; j -=<span> gap)
</span><span>10</span> <span>                    {
</span><span>11</span>                         <span>if</span> (data[j] &gt;<span> temp)
</span><span>12</span> <span>                        {
</span><span>13</span>                             data[j + gap] =<span> data[j];
</span><span>14</span>                             <span>if</span> (j == <span>0</span><span>)
</span><span>15</span> <span>                            {
</span><span>16</span>                                 data[j] =<span> temp;
</span><span>17</span>                                 <span>break</span><span>;
</span><span>18</span> <span>                            }
</span><span>19</span> <span>                        }
</span><span>20</span>                         <span>else</span>
<span>21</span> <span>                        {
</span><span>22</span>                             data[j + gap] =<span> temp;
</span><span>23</span>                             <span>break</span><span>;
</span><span>24</span> <span>                        }
</span><span>25</span> <span>                    }
</span><span>26</span> <span>                }
</span><span>27</span> <span>            }
</span><span>28</span>         }

复制代码

——————

这里实现的貌似是最差的希尔排序。主要源于步长的选择。维基上有各种牛叉的“凌波微步”，极限在哪里，

喜欢挑战的同学可以去学习学习。看维基排序算法里六种排序的测试，希尔最快，比快速排序还快！！我没实现啊！

只是对于神奇的步长更充满了敬畏。

基数排序

基数排序是一种非比较型整数排序。

“非比较型”是什么意思呢？因为它内部使用的是桶排序，而桶排序是非比较型排序。

这里就要说说桶排序了。一个非常有意思的排序。

桶排序

原理：取一定数量（数列中的最大值）的编好序号的桶，将数列每个数放进编号为它的桶里，然后将不是空的桶依次倒出来，

就组成有序数列了。维基入口

好吧！聪明的人一眼就看出桶排序的破绽了。假设只有两个数1,10000，岂不是要一万个桶！？这确实是个问题啊！我也

没想出解决办法。我起初也以为桶排序就是一个通过牺牲空间来换取时间的排序算法，它不需要比较，所以是非比较型算法。

但看了有趣的演示的桶排序后，发现世界之大，你没有解决，不代表别人没解决，睿智的人总是很多。

1，9999的桶排序实现：new Int[2];总共有两个数，得出最大数9999的位数4，取10的4次幂即10000作为分母，

要排序的数（1或9999）作为分子，并乘以数列总数2，即1*2/10000,9999*2/10000得到各自的位置0,1，完成排序。

如果是1,10000进行排序的话，上面的做法就需要稍微加一些处理——发现最大数是10的n次幂，就将它作为分母，并

放在数列末尾就好了。

如果是9999,10000进行排序的话，那就需要二维数组了，两个都在位置1，位置0没数。这个时候就需要在放

入每个位置时采用其它排序（比如插入排序）办法对这个位置的多个数排序了。

为基数排序做个过渡，我这里实现了一个个位数桶排序

涉及到了当重复的数出现的处理。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>void</span> BucketSortOnlyUnitDigit(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] indexCounter = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 indexCounter[data[i]]++<span>;
</span><span> 7</span> <span>            }
</span><span> 8</span>             <span>int</span>[] indexBegin = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span> 9</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; <span>10</span>; i++<span>)
</span><span>10</span> <span>            {
</span><span>11</span>                 indexBegin[i] = indexBegin[i-1]+<span> indexCounter[i-1];
</span><span>15</span> <span>            }
</span><span>16</span>             IList&lt;<span>int</span>&gt; tempList =<span> NewInstance(data, data.Count);
</span><span>17</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count; i++<span>)
</span><span>18</span> <span>            {
</span><span>19</span>                 <span>int</span> number =<span> data[i];
</span><span>20</span>                 tempList[indexBegin[number]++] =<span> data[i];
</span><span>21</span> <span>            }
</span><span>22</span>             data =<span> tempList;
</span><span>23</span>         }

复制代码

过程解析：indexCounter进行对每个数出现的频率的统计。indexBegin存储每个数的起始索引。

比如 1 1 2，indexCounter统计到0个0,2个1,1个2。indexBegin计算出0,1,2的起始索引分别为

0,0,2。当1个1已取出排序，那索引将+1,变为0,1,2。这样就通过提前给重复的数空出位置，解决了

重复的数出现的问题。当然，你也可以考虑用二维数组来解决重复。

下面继续基数排序。

基数排序原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。

取得最大数的位数，从低位开始，每个位上进行桶排序。

实现如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> IList&lt;<span>int</span>&gt; RadixSort(IList&lt;<span>int</span>&gt;<span> data)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span> max = data[<span>0</span><span>];
</span><span> 4</span>             <span>for</span> (<span>int</span> i = <span>1</span>; i &lt; data.Count; i++<span>)
</span><span> 5</span> <span>            {
</span><span> 6</span>                 <span>if</span> (data[i] &gt;<span> max)
</span><span> 7</span>                     max =<span> data[i];
</span><span> 8</span> <span>            }
</span><span> 9</span>             <span>int</span> digit = <span>1</span><span>;
</span><span>10</span>             <span>while</span> (max / <span>10</span> != <span>0</span><span>)
</span><span>11</span> <span>            {
</span><span>12</span>                 digit++<span>;
</span><span>13</span>                 max /= <span>10</span><span>;
</span><span>14</span> <span>            }
</span><span>15</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; digit; i++<span>)
</span><span>16</span> <span>            {
</span><span>17</span>                 <span>int</span>[] indexCounter = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span>18</span>                 IList&lt;<span>int</span>&gt; tempList =<span> NewInstance(data, data.Count);
</span><span>19</span>                 <span>for</span> (<span>int</span> j = <span>0</span>; j &lt; data.Count; j++<span>)
</span><span>20</span> <span>                {
</span><span>21</span>                     <span>int</span> number = (data[j] % Convert.ToInt32(Math.Pow(<span>10</span>, i + <span>1</span>))) / Convert.ToInt32(Math.Pow(<span>10</span>, i));  <span>//</span><span>得出i+1位上的数</span>
<span>22</span>                     indexCounter[number]++<span>;
</span><span>23</span> <span>                }
</span><span>24</span>                 <span>int</span>[] indexBegin = <span>new</span> <span>int</span>[<span>10</span><span>];
</span><span>25</span>                 <span>for</span> (<span>int</span> k = <span>1</span>; k &lt; <span>10</span>; k++<span>)
</span><span>26</span> <span>                {
</span><span>27</span>                     indexBegin[k] = indexBegin[k - <span>1</span>] + indexCounter[k - <span>1</span><span>];
</span><span>28</span> <span>                }
</span><span>29</span>                 <span>for</span> (<span>int</span> k = <span>0</span>; k &lt; data.Count; k++<span>)
</span><span>30</span> <span>                {
</span><span>31</span>                     <span>int</span> number = (data[k] % Convert.ToInt32(Math.Pow(<span>10</span>, i + <span>1</span>))) / Convert.ToInt32(Math.Pow(<span>10</span><span>, i));
</span><span>32</span>                     tempList[indexBegin[number]++] =<span> data[k];
</span><span>33</span> <span>                }
</span><span>34</span>                 data =<span> tempList;
</span><span>35</span> <span>            }
</span><span>36</span>             <span>return</span><span> data;
</span><span>37</span>         }

复制代码

过程解析：得出最大数的位数，从低位开始桶排序。我写的这个实现代码并不简洁，但逻辑更清晰。

后面测试的时候我们就会发现，按理来说这个实现也还行吧！但并不如想象的那么快！

循环的次数太多？（统计频率n次+9次计算+n次放到新的数组）*位数。

创建的新实例太多？(new int[10]两次+NewInstance is反射判断创建实例+new int[n])*位数

测试比较

添加随机数组，数组有序校验，微软Linq排序

代码如下：

复制代码

<span> 1</span>         <span>public</span> <span>static</span> <span>int</span>[] RandomSet(<span>int</span> length, <span>int</span><span> max)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] result = <span>new</span> <span>int</span><span>[length];
</span><span> 4</span>             Random rand = <span>new</span><span> Random();
</span><span> 5</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; result.Length; i++<span>)
</span><span> 6</span> <span>            {
</span><span> 7</span>                 result[i] =<span> rand.Next(max);
</span><span> 8</span> <span>            }
</span><span> 9</span>             <span>return</span><span> result;
</span><span>10</span> <span>        }
</span><span>11</span> 
<span>12</span>         <span>public</span> <span>static</span> <span>bool</span> IsAscOrdered(IList&lt;<span>int</span>&gt;<span> data)
</span><span>13</span> <span>        {
</span><span>14</span>             <span>bool</span> flag = <span>true</span><span>;
</span><span>15</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; data.Count - <span>1</span>; i++<span>)
</span><span>16</span> <span>            {
</span><span>17</span>                 <span>if</span> (data[i] &gt; data[i + <span>1</span><span>])
</span><span>18</span>                     flag = <span>false</span><span>;
</span><span>19</span> <span>            }
</span><span>20</span>             <span>return</span><span> flag;
</span><span>21</span> <span>        }
</span><span>22</span> 
<span>23</span>         <span>public</span> <span>static</span> <span>void</span> TestMicrosoft(IList&lt;<span>int</span>&gt;<span> data)
</span><span>24</span> <span>        {
</span><span>25</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>26</span> <span>            stopwatch.Start();
</span><span>27</span>             List&lt;<span>int</span>&gt; result = data.OrderBy(a =&gt;<span> a).ToList();
</span><span>28</span> <span>            stopwatch.Stop();
</span><span>29</span>             <span>string</span> methodName = <span>"</span><span>TestMicrosoft</span><span>"</span><span>;
</span><span>30</span>             <span>int</span> length =<span> methodName.Length;
</span><span>31</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>32</span> <span>            {
</span><span>33</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>34</span> <span>            }
</span><span>35</span>             Console.WriteLine(methodName +
<span>36</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(result) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>37</span> 
<span>38</span>         }

复制代码

测试主体如下：

复制代码

<span> 1</span>         <span>static</span> <span>void</span> Main(<span>string</span><span>[] args)
</span><span> 2</span> <span>        {
</span><span> 3</span>             <span>int</span>[] aa = RandomSet(<span>50000</span>, <span>99999</span><span>);
</span><span> 4</span>             <span>//</span><span>int[] aa = OrderedSet(5000);</span>
<span> 5</span>             Console.WriteLine(<span>"</span><span>Array Length:</span><span>"</span> +<span> aa.Length);
</span><span> 6</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)SelectSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 7</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 8</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleSortImprovedWithFlag, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span> 9</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)BubbleCocktailSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>10</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)InsertSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>11</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)InsertSortImprovedWithBinarySearch, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>12</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortStrict, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>13</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortRelax, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>14</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)QuickSortRelaxImproved, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>15</span>             RunTheMethod((Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt;)MergeSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>16</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)ShellSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>17</span>             RunTheMethod((Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt;)RadixSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>18</span>             RunTheMethod((Action&lt;IList&lt;<span>int</span>&gt;&gt;)HeapSort, aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>19</span>             TestMicrosoft(aa.Clone() <span>as</span> <span>int</span><span>[]);
</span><span>20</span> <span>            Console.Read();
</span><span>21</span> <span>        }
</span><span>22</span> 
<span>23</span>         <span>public</span> <span>static</span> <span>void</span> RunTheMethod(Func&lt;IList&lt;<span>int</span>&gt;, IList&lt;<span>int</span>&gt;&gt; method, IList&lt;<span>int</span>&gt;<span> data)
</span><span>24</span> <span>        {
</span><span>25</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>26</span> <span>            stopwatch.Start();
</span><span>27</span>             IList&lt;<span>int</span>&gt; result =<span> method(data);
</span><span>28</span> <span>            stopwatch.Stop();
</span><span>29</span>             <span>string</span> methodName =<span> method.Method.Name;
</span><span>30</span>             <span>int</span> length =<span> methodName.Length;
</span><span>31</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>32</span> <span>            {
</span><span>33</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>34</span> <span>            }
</span><span>35</span>             Console.WriteLine(methodName +
<span>36</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(result) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>37</span> <span>        }
</span><span>38</span> 
<span>39</span>         <span>public</span> <span>static</span> <span>void</span> RunTheMethod(Action&lt;IList&lt;<span>int</span>&gt;&gt; method, IList&lt;<span>int</span>&gt;<span> data)
</span><span>40</span> <span>        {
</span><span>41</span>             Stopwatch stopwatch = <span>new</span><span> Stopwatch();
</span><span>42</span> <span>            stopwatch.Start();
</span><span>43</span> <span>            method(data);
</span><span>44</span> <span>            stopwatch.Stop();
</span><span>45</span>             <span>string</span> methodName =<span> method.Method.Name;
</span><span>46</span>             <span>int</span> length =<span> methodName.Length;
</span><span>47</span>             <span>for</span> (<span>int</span> i = <span>0</span>; i &lt; <span>40</span> - length; i++<span>)
</span><span>48</span> <span>            {
</span><span>49</span>                 methodName += <span>"</span> <span>"</span><span>;
</span><span>50</span> <span>            }
</span><span>51</span>             Console.WriteLine(methodName +
<span>52</span>                 <span>"</span><span>  IsAscOrdered:</span><span>"</span> + IsAscOrdered(data) + <span>"</span><span>  Time:</span><span>"</span> +<span> stopwatch.Elapsed.TotalSeconds);
</span><span>53</span>         }

复制代码

剩余代码折叠在此处

View Code

测试设备：win8(64位)，i7-3630QM,8G内存，vs2012

测试结果：

100000,50000,10000,5000,1000,100依次是：

结果分析：可以看出在大数组的时候，微软自带排序更接近快速排序。而当数组变小时，速度却没有明显提升，甚至变得更慢，

比如1000和100。可以推断出在数组足够小的时候，比较已经不是影响这个方法主要因素。而根据它对大数组的表现。我们可以

推断出它应该用的是快速排序。反编译验证下：

在System.Linq.EnumerableSorter下。有兴趣的同学可以去看下详细实现。

维基上也有个测试。硬件没我的好。时间是我测试结果时间的几百倍。有兴趣的同学可以比较下。

在上面的测试中，我们可以看到快速最快，归并其次，冒泡最慢（维基上是希尔最快，估计使用的是某种神奇的步长）。

在我这里，以前实现的希尔还不如二分查找优化版的快，修正后希尔快了相当多，上面测试的希尔排序是以前错误的实现。

修正后的实现测试效果请点击右侧导航到希尔排序查看。希尔排序是一种神奇又有潜力的算法。步长不好会很挫！

而基数排序却是比平均时间复杂度为o(nlogn)的堆排序，归并排序，快速排序还要慢的，虽然它的平均时间复杂度为o(n)。

冒泡标识优化版对随机数列结果优化不明显，鸡尾酒版优化可以看到，但也不是很厉害。

插入排序二分查找优化版优化比较明显。我优化的快速排序QuickSortRelaxImproved优化也不明显。

以上是随机数列的测试结果，最大值为99999。

而对于有序数列，这些方法表现又会如何呢？

我这里就不演示了。本文末尾会附上demo，大家可以自行测试。

有意思的是:

我在测试有序数列的时候，QuickSortStrict方法栈溢出了（stack overflow exception）。这个异常

是让我去stackoverflow搜寻答案吗？哈哈！我确信我的方法不是无限循环。跳过一堆链接。。。我是

在测试10000个数排序的时候发生的错误。我跟踪后发现大约在9400多次递归的时候，栈溢出。找啊找

终于找见了一个类似的问题。上面说如果一个递归9000多次而没有返回值，也会报栈溢出的。而这个方法

对于10000个有序数列，确实每次减少一个数地递归，次数会超过限制。

我的算法理论不怎么好，对于时间复杂度和空间复杂度，还有稳定度，搞得也不怎么清楚，只知道个大致的

意思。各位要笔试面试的朋友可以去维基百科这个表来了解学习。

总结

我觉得使用IList更贴近数列，更能展现基本的操作。所以我的实现中都没有将它强制转化为List

或者int[]来调用微软封装的方法。这样说来，题目说C#实现倒快有点名不副实了。不过这样却也方便了其它语言

朋友。比如将我这篇博文里的实现随便改改，就可以说是另一个语言版本的8种排序算法了。哈哈！在这里，

我想说下这次学习排序对我的意义：老久不怎么动脑了，突然动起来，磨磨唧唧地得出结果，最后倒也有点成就感！

在学习过程中，经常会脑子转不过弯，想不通的，只是走在路上或者睡觉前突然灵感一现，有点小惊喜的感觉！

这大概就是进步的特征吧！哈哈！这次写demo+写博客花费了不少时间，倒也收获颇多，尤其在我将8种

排序都实现之前，没进行过一次测试，全部实现完成后，测试时各种索引越界+无限循环+各种问题，没几个

能跑通的，到后来的几乎都没有问题，也算是锻炼了思维，找出错原因的能力。本篇是自我学习的一个总结，

要学习及锻炼的园友，还望一定自己实现一下，可以和我的比较一下，解除疑惑或者提出改进。

Demo源码

PS:我打算三月份去广州发展，主要会Asp.net mvc+jquery（不介意学习新的技术[除了webform]及语言[除了java]）。

CSharp排序算法小结

发表于 2019-11-30 更新于 2026-05-09 分类于学习笔记，排序算法

前言

算法这个东西其实在开发中很少用到，特别是web开发中，但是算法也很重要，因为任何的程序，任何的软件，都是由很多的算法和数据结构组成的。但是这不意味着算法对于每个软件设计人员的实际工作都是很重要的。每个项目特点和需求特殊也导致算法运用场景上不同。但是个人觉得算法运用的好的话会给自己在程序设计的时候提供比较好的思路。下面就对一些排序算法小结一下，就当做自己的一个笔记吧。

插入排序

1.简介

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

2.算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到该位置后
6.重复步骤2~5
如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

3.使用插入排序为一列数字进行排序的过程

最差时间复杂度 $O(n^{2})$

最优时间复杂度 $O(n)$

平均时间复杂度 $O(n^{2})$

4.C#实现

复制代码

    /// <summary>
    /// 插入排序 /// </summary>
    public class InsertionSorter
    { public void Sort(int\[\] list)
        { for (int i = 1; i < list.Length; ++i)
            { int t = list\[i\]; int j = i; while ((j > 0) && (list\[j - 1\] > t))
                {
                    list\[j\] \= list\[j - 1\]; \--j;
                }
                list\[j\] \= t;
            }

        }
    }

复制代码

数组

int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };

希尔排序

1.简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

2.算法实现

原始的算法实现在最坏的情况下需要进行O(n2)的比较和交换。V. Pratt的书[1] 对算法进行了少量修改，可以使得性能提升至O(n log2 n)。这比最好的比较算法的O(n log n)要差一些。
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序（冒泡排序或插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。

3.排序过程

最差时间复杂度根据步长串行的不同而不同。 $O(n\log^2 n)$

最优时间复杂度 O(n)

平均时间复杂度根据步长串行的不同而不同。

4.C#实现

复制代码

    /// <summary>
    /// 希尔排序 /// </summary>
    public class ShellSorter
    { public void Sort(int\[\] list)
        { int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 \* inc + 1) ; for (; inc > 0; inc /= 3)
            { for (int i = inc + 1; i <= list.Length; i += inc)
                { int t = list\[i - 1\]; int j = i; while ((j > inc) && (list\[j - inc - 1\] > t))
                    {
                        list\[j \- 1\] = list\[j - inc - 1\];
                        j \-= inc;
                    }
                    list\[j \- 1\] = t;
                }
            }
        }
    }

复制代码

选择排序

1.简介

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

2.实现过程

最差时间复杂度 О(n²)

最优时间复杂度 О(n²)

平均时间复杂度 О(n²)

3.C#实现

复制代码

    /// <summary>
    /// 选择排序 /// </summary>
    public class SelectionSorter
    { // public enum comp {COMP\_LESS,COMP\_EQUAL,COMP\_GRTR};
        private int min; // private int m=0;
        public void Sort(int\[\] list)
        { for (int i = 0; i < list.Length - 1; ++i)
            {
                min \= i; for (int j = i + 1; j < list.Length; ++j)
                { if (list\[j\] < list\[min\])
                        min \= j;
                } int t = list\[min\];
                list\[min\] \= list\[i\];
                list\[i\] \= t; // Console.WriteLine("{0}",list\[i\]);

}

        }
    }

复制代码

冒泡排序

1.简介

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n^{2})的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n^{2})次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（O(n^{2})），而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。

2.算法实现
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.实现过程

最差时间复杂度 $O(n^{2})$

最优时间复杂度 $O(n)$

平均时间复杂度 $O(n^{2})$

4.C#实现

复制代码

   /// <summary>
    /// 冒泡排序 /// </summary>
    public class bubblesort
    { public void BubbleSort(int\[\] R)
        { int i, j, temp; //交换标志 
            bool exchange; for (i = 0; i < R.Length; i++) //最多做R.Length-1趟排序

{
exchange = false; //本趟排序开始前，交换标志应为假
for (j = R.Length - 2; j >= i; j–)
{ if (R[j + 1] < R[j])　//交换条件
{
temp = R[j + 1];
R[j + 1] = R[j];
R[j] = temp;
exchange = true; //发生了交换，故将交换标志置为真
}
} if (!exchange) //本趟排序未发生交换，提前终止算法
{ break;
}
}
}
}

复制代码

设计模式总结

发表于 2019-11-25 更新于 2026-05-09

设计模式是软件开发中经过总结和验证的、解决特定场景下常见问题的最佳实践，它能提升代码的可复用性、可维护性、可读性和扩展性。根据目的和应用场景，设计模式主要分为创建型模式、结构型模式、行为型模式三大类，以下是各类模式的核心总结及对应UML图：

一、创建型模式

创建型模式聚焦于对象的创建过程，封装对象创建的细节，降低创建逻辑与业务逻辑的耦合，让程序在创建对象时更灵活。

1. 单例模式（Singleton）

核心意图：保证一个类仅有一个实例，并提供一个全局访问点。
适用场景：配置管理、日志记录器、数据库连接池等需唯一实例的场景。
实现要点：私有化构造方法，通过静态方法/属性返回唯一实例；需考虑线程安全（如懒汉式加锁、饿汉式提前初始化）、序列化/反序列化破坏单例的问题。
优缺点：优点是节省资源、全局统一访问；缺点是违背单一职责，扩展困难，可能引发并发问题（未妥善处理时）。

UML类图：

2. 工厂方法模式（Factory Method）

核心意图：定义创建对象的接口，让子类决定实例化哪个类，将对象创建延迟到子类。
适用场景：产品种类可扩展，创建逻辑需隔离的场景（如日志框架支持不同日志输出类型）。
实现要点：抽象工厂类定义创建方法，具体工厂类实现该方法创建对应产品。
优缺点：优点是符合开闭原则，解耦产品创建与使用；缺点是新增产品需新增工厂类，类数量增多。

UML类图：

3. 抽象工厂模式（Abstract Factory）

核心意图：提供一个创建一系列相关或相互依赖对象的接口，无需指定具体类。
适用场景：需创建一套“产品族”（如操作系统+UI组件组合、数据库+驱动组合）的场景。
实现要点：抽象工厂定义多个产品创建方法，具体工厂实现所有方法，产出对应产品族。
优缺点：优点是保证产品族一致性，隔离具体产品；缺点是新增产品族需修改抽象工厂，违背开闭原则。

UML类图：

4. 建造者模式（Builder）

核心意图：将复杂对象的构建与表示分离，使得同样的构建过程可以创建不同的表示。
适用场景：对象属性多、构造逻辑复杂（如建造汽车、生成复杂文档）。
实现要点：建造者类封装构建步骤，指挥者类控制构建流程，产品类表示最终对象。
优缺点：优点是解耦构建与表示，灵活控制构建过程；缺点是产品属性固定时冗余，类数量增加。

UML类图：

5. 原型模式（Prototype）

核心意图：通过复制现有实例（原型）创建新对象，避免重复初始化开销。
适用场景：对象创建成本高（如数据库查询后的数据对象）、需批量创建相似对象的场景。
实现要点：实现克隆接口（浅克隆/深克隆），通过原型对象复制生成新对象。
优缺点：优点是简化创建过程，提升性能；缺点是深克隆需处理复杂引用关系。

UML类图：

二、结构型模式

结构型模式关注类和对象的组合方式，通过合理的结构设计，提升代码的灵活性和复用性，解决类/对象间的耦合与扩展问题。

1. 适配器模式（Adapter）

核心意图：将一个类的接口转换成客户希望的另一个接口，让不兼容的类可以协同工作。
适用场景：集成第三方库、复用现有类但接口不匹配、新旧系统对接。
实现要点：类适配器（继承适配者）、对象适配器（组合适配者）、接口适配器（默认空实现）。
优缺点：优点是复用现有代码，解耦接口与实现；缺点是增加额外类，复杂场景可能导致适配链过长。

UML类图（对象适配器）：

2. 装饰器模式（Decorator）

核心意图：动态地给一个对象添加一些额外的职责，比继承更灵活。
适用场景：需扩展对象功能，且功能可组合（如IO流、日志增强、权限叠加）。
实现要点：装饰器类与被装饰类实现同一接口，持有被装饰对象引用，重写方法并增强逻辑。
优缺点：优点是灵活扩展，符合开闭原则；缺点是多层装饰会增加代码复杂度。

UML类图：

3. 代理模式（Proxy）

核心意图：为其他对象提供一种代理以控制对这个对象的访问。
适用场景：远程代理（RPC）、虚拟代理（懒加载）、保护代理（权限控制）、日志代理（监控）。
实现要点：静态代理（手动编写代理类）、动态代理（JDK动态代理、CGLIB），代理类与目标类实现同一接口/继承目标类。
优缺点：优点是隔离目标对象，增强访问控制；缺点是增加代理层，可能降低性能。

UML类图（静态代理）：

4. 外观模式（Facade）

核心意图：为子系统中的一组接口提供一个一致的入口，简化子系统的使用。
适用场景：复杂系统（如电商下单：库存、支付、物流子系统）、对外提供统一API。
实现要点：外观类封装子系统交互逻辑，对外暴露简单接口。
优缺点：优点是降低使用复杂度，解耦客户端与子系统；缺点是外观类可能成为“上帝类”，耦合过多逻辑。

UML类图：

5. 桥接模式（Bridge）

核心意图：将抽象部分与它的实现部分分离，使它们都可以独立地变化。
适用场景：多维度变化的场景（如“形状+颜色”、“操作系统+文件系统”）。
实现要点：抽象类持有实现类引用，抽象与实现分层，各自独立扩展。
优缺点：优点是解耦抽象与实现，符合开闭原则；缺点是增加代码复杂度，理解成本高。

UML类图：

6. 组合模式（Composite）

核心意图：将对象组合成树形结构以表示“部分-整体”的层次结构，统一对待单个对象和组合对象。
适用场景：树形结构场景（如菜单、文件目录、组织架构）。
实现要点：抽象组件类定义公共方法，叶子节点类表示单个对象，组合节点类包含子组件集合。
优缺点：优点是统一访问单个/组合对象，简化客户端逻辑；缺点是设计复杂，限制类型时需额外判断。

UML类图：

7. 享元模式（Flyweight）

核心意图：运用共享技术有效地支持大量细粒度的对象，减少内存占用。
适用场景：大量相似对象（如池化资源、字符常量池、游戏角色）。
实现要点：区分内部状态（共享）和外部状态（不共享），享元工厂管理共享对象池。
优缺点：优点是减少内存消耗，提升性能；缺点是增加系统复杂度，需处理外部状态。

UML类图：

三、行为型模式

行为型模式关注对象间的交互和职责分配，优化对象的通信方式和行为逻辑，提升代码的协作性和可扩展性。

1. 观察者模式（Observer）

核心意图：定义对象间的一对多依赖，当一个对象状态改变时，所有依赖它的对象都得到通知并自动更新。
适用场景：事件驱动、发布-订阅（如GUI事件、消息通知、数据监听）。
实现要点：主题（被观察者）维护观察者列表，提供注册/移除/通知方法；观察者实现更新方法。
优缺点：优点是解耦主题与观察者，支持广播通知；缺点是观察者过多时通知效率低，可能引发循环依赖。

UML类图：

2. 策略模式（Strategy）

核心意图：定义一系列算法，将每个算法封装起来，使它们可以互相替换，且算法的变化不影响使用算法的客户。
适用场景：多种算法可选（如排序算法、支付方式、优惠计算）。
实现要点：策略接口定义算法方法，具体策略类实现算法，上下文类持有策略引用并调用。
优缺点：优点是算法可灵活切换，符合开闭原则；缺点是客户端需了解所有策略，策略过多时类数量增加。

UML类图：

3. 模板方法模式（Template Method）

核心意图：定义一个操作中的算法骨架，将一些步骤延迟到子类中，子类不改变算法结构即可重定义某些步骤。
适用场景：流程固定但步骤实现可变（如框架初始化、报表生成、测试流程）。
实现要点：抽象父类定义模板方法（固定流程）和抽象方法（可变步骤），子类实现抽象方法。
优缺点：优点是复用流程代码，控制扩展点；缺点是模板方法过多时父类复杂，子类受限。

UML类图：

4. 迭代器模式（Iterator）

核心意图：提供一种方法顺序访问一个聚合对象中的各个元素，而不暴露其内部表示。
适用场景：遍历集合（如列表、集合、树），统一遍历接口。
实现要点：迭代器接口定义遍历方法（next、hasNext），聚合类提供获取迭代器的方法。
优缺点：优点是统一遍历接口，解耦聚合与遍历；缺点是简单遍历场景下增加冗余类。

UML类图：

5. 命令模式（Command）

核心意图：将请求封装成对象，以便使用不同的请求、队列或日志来参数化其他对象，支持撤销/重做操作。
适用场景：请求解耦（如GUI按钮、事务操作、任务队列）。
实现要点：命令接口定义执行方法，具体命令类封装接收者和动作，调用者触发命令执行。
优缺点：优点是解耦请求者与接收者，支持命令组合、撤销；缺点是类数量增加，简单场景冗余。

UML类图：

6. 责任链模式（Chain of Responsibility）

核心意图：为请求创建一个接收者对象的链，使多个对象都有机会处理请求，避免请求发送者与接收者耦合。
适用场景：请求需多节点处理（如权限审批、日志分级、异常处理链）。
实现要点：处理者接口定义处理方法，每个处理者持有下一个处理者引用，自行处理或转发请求。
优缺点：优点是解耦请求与处理，动态调整责任链；缺点是请求可能无人处理，调试复杂。

UML类图：

7. 状态模式（State）

核心意图：允许对象在其内部状态改变时改变它的行为，对象看起来似乎修改了它的类。
适用场景：对象行为依赖状态（如订单状态、电梯状态、游戏角色状态）。
实现要点：状态接口定义行为方法，具体状态类实现对应行为，上下文类持有当前状态并委托状态处理。
优缺点：优点是状态逻辑集中管理，避免大量if-else；缺点是状态多时有大量状态类。

UML类图：

8. 备忘录模式（Memento）

核心意图：在不破坏封装的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，以便后续恢复。
适用场景：撤销操作（如编辑器、游戏存档、事务回滚）。
实现要点：备忘录类存储状态，原发器创建/恢复备忘录，管理者管理备忘录。
优缺点：优点是支持状态回滚，封装状态；缺点是消耗内存（大量备忘录）。

UML类图：

9. 中介者模式（Mediator）

核心意图：用一个中介对象来封装一系列的对象交互，使各对象不需要显式地相互引用，降低耦合。
适用场景：多对象复杂交互（如聊天室、GUI组件交互、分布式系统协调）。
实现要点：中介者接口定义交互方法，具体中介者封装对象间交互，同事类通过中介者通信。
优缺点：优点是解耦对象间交互，简化维护；缺点是中介者可能成为“上帝类”，复杂度高。

UML类图：

10. 解释器模式（Interpreter）

核心意图：给定一个语言，定义它的文法的一种表示，并定义一个解释器，该解释器使用该表示来解释语言中的句子。
适用场景：简单语法解析（如表达式计算、配置解析、自定义脚本）。
实现要点：抽象表达式定义解释方法，终结符/非终结符表达式实现具体逻辑，环境类存储上下文。
优缺点：优点是灵活扩展语法；缺点是语法复杂时类数量爆炸，效率低。

UML类图：

四、设计模式核心原则

所有设计模式均围绕SOLID原则展开，是设计模式的底层逻辑：

单一职责原则（SRP）：一个类只负责一个职责，降低耦合。
开闭原则（OCP）：对扩展开放，对修改关闭，通过抽象/接口实现。
里氏替换原则（LSP）：子类可替换父类且不影响程序正确性。
接口隔离原则（ISP）：拆分臃肿接口，提供最小化专用接口。
依赖倒置原则（DIP）：依赖抽象而非具体实现，降低耦合。

五、设计模式使用建议

不要过度设计：仅在问题重复出现、需复用/扩展时使用，避免为了用模式而用模式。
优先复用现有框架：多数框架已内置设计模式（如Spring的单例、代理，MyBatis的工厂、装饰器），无需重复实现。
结合场景选择：如创建对象选创建型，扩展功能选装饰器/策略，解耦交互选观察者/中介者。
理解本质而非形式：模式的核心是解决问题的思路，而非固定代码结构。

设计模式是经验的沉淀，掌握其思想能让代码更贴合“高内聚、低耦合”的软件设计目标，提升系统的可维护性和扩展性。

解释器模式

发表于 2019-11-24 更新于 2026-05-09 分类于学习笔记，设计模式

解释器模式（Interpreter Pattern）是行为型设计模式的重要分支，其核心设计思想是定义特定语言的文法规则，并构建对应的解释器，将复杂的语法解析拆解为多个简单的解释器节点，通过组合这些节点完成整体语法的解释与执行。该模式专注于“语法解析与逻辑执行”的解耦，适用于处理固定语法规则的场景，如表达式计算、自定义配置解析、简单脚本解释、领域特定语言（DSL）实现等。本文将从核心结构拆解、多语言落地实现、优缺点深度剖析、适用场景梳理及实战总结等维度，系统解读解释器模式的设计思想与工程实践，为开发者提供可直接复用的技术方案。

一、解释器模式核心结构

解释器模式的核心价值在于“拆分复杂语法、实现模块化解析”，通过五大核心角色的协同工作，完成语法树的构建与解释执行，各角色职责边界清晰、耦合度低，具体定义与交互逻辑如下：

1.1 抽象表达式（Abstract Expression）

抽象表达式是所有具体表达式的基类或接口，核心职责是定义统一的解释操作接口（通常命名为Interpret方法）。该接口是所有表达式节点的通用入口，确保终结符与非终结符表达式能以统一的方式被调用，为多态解析提供基础。

1.2 终结符表达式（Terminal Expression）

终结符表达式是语法树的叶子节点，对应文法中的终结符（即语法规则中不可再拆分的最小单元），如算术表达式中的数字、常量，配置语法中的键值对等。其核心职责是实现终结符的具体解释逻辑，无需依赖其他表达式，直接返回解析结果。

1.3 非终结符表达式（Nonterminal Expression）

非终结符表达式对应文法中的非终结符（可拆分为多个子表达式的语法单元），如算术表达式中的加减乘除运算符、逻辑表达式中的与或非逻辑等。其核心职责是组合多个子表达式（终结符或非终结符），通过递归调用子表达式的解释方法，完成复杂语法的解析与执行。

1.4 环境（Context）

环境类用于存储解释器的全局上下文信息，供所有表达式共享使用，如变量映射关系、语法解析的中间状态、计算结果缓存等。环境类的存在的可以减少表达式之间的直接依赖，同时为后续扩展（如变量替换）提供灵活支撑。

1.5 客户端（Client）

客户端负责两个核心操作：一是根据预设的文法规则，构建由终结符表达式和非终结符表达式组成的语法树；二是调用语法树根节点的解释方法，触发整个语法树的逐层解析与执行，最终获取解析结果。

核心交互流程：客户端定义文法规则 → 构建语法树（组合终结符与非终结符表达式） → 初始化环境上下文 → 调用根节点Interpret方法 → 子表达式逐层递归解析 → 返回最终执行结果。

二、多语言实现解释器模式

以“简单算术表达式解析（支持整数加减运算）”为统一实战场景，设计核心逻辑：通过解释器模式解析表达式“1 + 2 - 3”，拆解为“加法表达式”与“减法表达式”的组合，最终计算出结果。以下提供C#、Python、Golang、C++及纯C的可运行实现，贴合各语言原生特性，补充规范注释、边界校验与资源释放逻辑，兼顾实用性与严谨性，清晰呈现模式在不同语言中的适配思路。

2.1 C# 实现（面向对象规范实现）

C#作为强类型面向对象语言，通过接口定义抽象表达式，依托类实现终结符与非终结符逻辑，借助多态特性实现统一解析。代码结构清晰、可维护性高，适用于企业级应用中的简单表达式解析、配置语法解析等场景。

using System;

/// <summary>
/// 环境类：存储解释器全局上下文（此处简化为无状态，可扩展添加变量映射等）
/// </summary>
public class Context { }

/// <summary>
/// 抽象表达式接口：定义统一的解释操作
/// </summary>
public interface IExpression
{
    /// <summary>
    /// 解释方法：执行当前表达式的解析逻辑
    /// </summary>
    /// <param name="context">全局上下文</param>
    /// <returns>解析执行结果</returns>
    int Interpret(Context context);
}

/// <summary>
/// 终结符表达式：数字表达式，解析算术表达式中的数字
/// </summary>
public class NumberExpression : IExpression
{
    /// <summary>
    /// 存储的数字值
    /// </summary>
    private readonly int _number;

    /// <summary>
    /// 构造函数：初始化数字表达式
    /// </summary>
    /// <param name="number">数字值</param>
    public NumberExpression(int number)
    {
        _number = number;
    }

    /// <summary>
    /// 解释逻辑：直接返回数字本身
    /// </summary>
    public int Interpret(Context context)
    {
        return _number;
    }
}

/// <summary>
/// 非终结符表达式：加法表达式，解析“+”运算
/// </summary>
public class AddExpression : IExpression
{
    /// <summary>
    /// 左表达式（加法左侧的子表达式）
    /// </summary>
    private readonly IExpression _leftExpression;

    /// <summary>
    /// 右表达式（加法右侧的子表达式）
    /// </summary>
    private readonly IExpression _rightExpression;

    /// <summary>
    /// 构造函数：组合两个子表达式
    /// </summary>
    /// <param name="left">左子表达式</param>
    /// <param name="right">右子表达式</param>
    public AddExpression(IExpression left, IExpression right)
    {
        _leftExpression = left ?? throw new ArgumentNullException(nameof(left), "左表达式不可为null");
        _rightExpression = right ?? throw new ArgumentNullException(nameof(right), "右表达式不可为null");
    }

    /// <summary>
    /// 解释逻辑：递归解析左右子表达式，返回加法结果
    /// </summary>
    public int Interpret(Context context)
    {
        return _leftExpression.Interpret(context) + _rightExpression.Interpret(context);
    }
}

/// <summary>
/// 非终结符表达式：减法表达式，解析“-”运算
/// </summary>
public class SubtractExpression : IExpression
{
    /// <summary>
    /// 左表达式（减法左侧的子表达式）
    /// </summary>
    private readonly IExpression _leftExpression;

    /// <summary>
    /// 右表达式（减法右侧的子表达式）
    /// </summary>
    private readonly IExpression _rightExpression;

    /// <summary>
    /// 构造函数：组合两个子表达式
    /// </summary>
    /// <param name="left">左子表达式</param>
    /// <param name="right">右子表达式</param>
    public SubtractExpression(IExpression left, IExpression right)
    {
        _leftExpression = left ?? throw new ArgumentNullException(nameof(left), "左表达式不可为null");
        _rightExpression = right ?? throw new ArgumentNullException(nameof(right), "右表达式不可为null");
    }

    /// <summary>
    /// 解释逻辑：递归解析左右子表达式，返回减法结果
    /// </summary>
    public int Interpret(Context context)
    {
        return _leftExpression.Interpret(context) - _rightExpression.Interpret(context);
    }
}

// 客户端：构建语法树并执行解析
class Program
{
    static void Main(string[] args)
    {
        try
        {
            // 1. 初始化上下文
            Context context = new Context();

            // 2. 构建语法树：解析表达式 “1 + 2 - 3”
            // 结构：减法表达式（左：加法表达式，右：数字表达式3）
            // 加法表达式（左：数字表达式1，右：数字表达式2）
            IExpression expression = new SubtractExpression(
                new AddExpression(
                    new NumberExpression(1),
                    new NumberExpression(2)
                ),
                new NumberExpression(3)
            );

            // 3. 执行解析并输出结果
            int result = expression.Interpret(context);
            Console.WriteLine($"C# 解析表达式「1 + 2 - 3」，执行结果：{result}"); // 输出 0
        }
        catch (Exception ex)
        {
            Console.WriteLine($"解析异常：{ex.Message}");
        }
    }
}

2.2 Python 实现（动态语言简洁实现）

Python遵循“鸭子类型”，无需显式定义接口，通过基类+子类继承实现抽象表达式逻辑，语法简洁、无冗余类型声明。依托动态特性，可灵活扩展表达式类型，无需修改核心解析逻辑，适用于快速开发、轻量级解析场景（如简单配置解析、小型计算器）。

class Context:
    """环境类：存储解释器全局上下文，可扩展添加变量映射等功能"""
    pass

class Expression:
    """抽象表达式基类：定义统一的解释接口"""
    def interpret(self, context):
        """
        解释方法：子类必须实现该方法，执行具体解析逻辑
        :param context: 全局上下文对象
        :return: 解析执行结果
        """
        raise NotImplementedError("子类必须实现interpret方法，完成具体解析逻辑")

class NumberExpression(Expression):
    """终结符表达式：数字表达式，解析算术表达式中的数字"""
    def __init__(self, number):
        """
        初始化数字表达式
        :param number: 数字值（整数）
        """
        if not isinstance(number, int):
            raise TypeError("数字表达式仅支持整数类型")
        self.number = number

    def interpret(self, context):
        """解释逻辑：直接返回数字本身"""
        return self.number

class AddExpression(Expression):
    """非终结符表达式：加法表达式，解析“+”运算"""
    def __init__(self, left, right):
        """
        初始化加法表达式，组合两个子表达式
        :param left: 左子表达式（Expression子类实例）
        :param right: 右子表达式（Expression子类实例）
        """
        if not isinstance(left, Expression) or not isinstance(right, Expression):
            raise TypeError("加法表达式的左右子表达式必须是Expression子类实例")
        self.left = left
        self.right = right

    def interpret(self, context):
        """解释逻辑：递归解析左右子表达式，返回加法结果"""
        return self.left.interpret(context) + self.right.interpret(context)

class SubtractExpression(Expression):
    """非终结符表达式：减法表达式，解析“-”运算"""
    def __init__(self, left, right):
        """
        初始化减法表达式，组合两个子表达式
        :param left: 左子表达式（Expression子类实例）
        :param right: 右子表达式（Expression子类实例）
        """
        if not isinstance(left, Expression) or not isinstance(right, Expression):
            raise TypeError("减法表达式的左右子表达式必须是Expression子类实例")
        self.left = left
        self.right = right

    def interpret(self, context):
        """解释逻辑：递归解析左右子表达式，返回减法结果"""
        return self.left.interpret(context) - self.right.interpret(context)

# 客户端：构建语法树并执行解析
if __name__ == "__main__":
    try:
        # 1. 初始化上下文
        context = Context()

        # 2. 构建语法树：解析表达式 “1 + 2 - 3”
        expression = SubtractExpression(
            AddExpression(
                NumberExpression(1),
                NumberExpression(2)
            ),
            NumberExpression(3)
        )

        # 3. 执行解析并输出结果
        result = expression.interpret(context)
        print(f"Python 解析表达式「1 + 2 - 3」，执行结果：{result}")  # 输出 0
    except Exception as e:
        print(f"解析异常：{str(e)}")

2.3 Golang 实现（接口至上轻量实现）

Go语言无类和继承，遵循“组合优于继承”原则，通过接口定义抽象表达式，结构体实现接口方法，依托接口多态实现统一解析。代码极简高效、无冗余，贴合Go语言“简洁、高效”的设计理念，适配高并发后端场景（如服务端配置解析、简单规则引擎）。

package main

import (
 "fmt"
)

// Context 环境类：存储解释器全局上下文（可扩展变量映射等）
type Context struct{}

// Expression 抽象表达式接口：定义统一的解释方法
type Expression interface {
  nterpret(context *Context) int
}

// NumberExpression 终结符表达式：数字表达式
type NumberExpression struct {
        num // 存储的数字值
}

// NewNumberExpression 初始化数字表达式，添加参数校验
func NewNumberExpression(number int) *NumberExpression {
        reumberExpression{number: number}
}

// Interpret 解释方法：直接返回数字本身
func (n *NumberExpression) Interpret(context *Context) int {
        retumber
}

// AddExpression 非终结符表达式：加法表达式
type AddExpression struct {
    t  Expression // 左子表达式
        rpression // 右子表达式
}

// NewAddExpression 初始化加法表达式，组合两个子表达式并校验
func NewAddExpression(left, right Expression) (*AddExpression, error) {
    left == nil || right == nil {
   eturn nil, fmt.Errorf("加法表达式的左右子表达式不可为nil")
    return &AddExpression{left: left, right: right}, nil
}

// Interpret 解释方法：递归解析左右子表达式，返回加法结果
func (a *AddExpression) Interpret(context *Context) int {
        r.left.Interpret(context) + a.right.Interpret(context)
}

// SubtractExpression 非终结符表达式：减法表达式
type SubtractExpression struct {
       Expression // 左子表达式
        right Expression // 右子表达式
}

// NewSubtractExpression 初始化减法表达式，组合两个子表达式并校验
func NewSubtractExpression(left, right Expression) (*SubtractExpression, error) {
        if left == nil || right == nil {
                return nil, fmt.Errorf("减法表达式的左右子表达式不可为nil")
        }
        return &SubtractExpression{left: left, right: right}, nil
}

// Interpret 解释方法：递归解析左右子表达式，返回减法结果
func (s *SubtractExpression) Interpret(context *Context) int {
        return s.left.Interpret(context) - s.right.Interpret(context)
}

// 客户端：构建语法树并执行解析
func main() {
        // 1. 初始化上下文
        context := &Context{}

        // 2. 构建语法树：解析表达式 “1 + 2 - 3”
        // 先创建加法表达式
        addExpr, err := NewAddExpression(NewNumberExpression(1), NewNumberExpression(2))
        if err != nil {
                fmt.Printf("创建加法表达式失败：%v\n", err)
                return
        }
        // 再创建减法表达式（组合加法表达式与数字表达式）
        subExpr, err := NewSubtractExpression(addExpr, NewNumberExpression(3))
        if err != nil {
                fmt.Printf("创建减法表达式失败：%v\n", err)
                return
        }

        // 3. 执行解析并输出结果
        result := subExpr.Interpret(context)
        fmt.Printf("Golang 解析表达式「1 + 2 - 3」，执行结果：%d\n", result) // 输出 0
}
        left eturn a    }
                     r    if ight Ex    lefurn n.nturn &Nber int      I

2.4 C++ 实现（抽象类+虚函数经典实现）

C++通过抽象类（纯虚函数）定义抽象表达式，子类继承并实现具体解释逻辑，依托虚函数实现多态解析。同时通过手动内存管理，避免内存泄漏，兼顾灵活性与高性能，适用于底层开发、高频调用场景（如编译器简化版表达式解析、嵌入式设备规则解析）。

#include <iostream>
#include <stdexcept>
using namespace std;

/// <summary>
/// 环境类：存储解释器全局上下文（可扩展变量映射等）
/// </summary>
class Context {};

/// <summary>
/// 抽象表达式（抽象类）：定义统一的解释接口（纯虚函数）
/// </summary>
class Expression {
public:
    /// <summary>
    /// 纯虚函数：解释方法，子类必须实现
    /// </summary>
    virtual int interpret(Context* context) = 0;
    
    /// <summary>
    /// 虚析构函数：确保子类对象正确释放
    /// </summary>
    virtual ~Expression() = default;
};

/// <summary>
/// 终结符表达式：数字表达式
/// </summary>
class NumberExpression : public Expression {
private:
    int number; // 存储的数字值
public:
    /// <summary>
    /// 构造函数：初始化数字表达式
    /// </summary>
    NumberExpression(int num) : number(num) {}

    /// <summary>
    /// 解释方法：直接返回数字本身
    /// </summary>
    int interpret(Context* context) override {
        return number;
    }
};

/// <summary>
/// 非终结符表达式：加法表达式
/// </summary>
class AddExpression : public Expression {
private:
    Expression* left;  // 左子表达式
    Expression* right; // 右子表达式
public:
    /// <summary>
    /// 构造函数：组合两个子表达式，添加参数校验
    /// </summary>
    AddExpression(Expression* l, Expression* r) {
        if (l == nullptr || r == nullptr) {
            throw invalid_argument("加法表达式的左右子表达式不可为nullptr");
        }
        left = l;
        right = r;
    }

    /// <summary>
    /// 解释方法：递归解析左右子表达式，返回加法结果
    /// </summary>
    int interpret(Context* context) override {
        return left->interpret(context) + right->interpret(context);
    }

    /// <summary>
    /// 析构函数：释放子表达式内存，避免泄漏
    /// </summary>
    ~AddExpression() override {
        delete left;
        delete right;
    }
};

/// <summary>
/// 非终结符表达式：减法表达式
/// </summary>
class SubtractExpression : public Expression {
private:
    Expression* left;  // 左子表达式
    Expression* right; // 右子表达式
public:
    /// <summary>
    /// 构造函数：组合两个子表达式，添加参数校验
    /// </summary>
    SubtractExpression(Expression* l, Expression* r) {
        if (l == nullptr || r == nullptr) {
            throw invalid_argument("减法表达式的左右子表达式不可为nullptr");
        }
        left = l;
        right = r;
    }

    /// <summary>
    /// 解释方法：递归解析左右子表达式，返回减法结果
    /// </summary>
    int interpret(Context* context) override {
        return left->interpret(context) - right->interpret(context);
    }

    /// <summary>
    /// 析构函数：释放子表达式内存，避免泄漏
    /// </summary>
    ~SubtractExpression() override {
        delete left;
        delete right;
    }
};

// 客户端：构建语法树并执行解析
int main() {
    try {
        // 1. 初始化上下文
        Context* context = new Context();

        // 2. 构建语法树：解析表达式 “1 + 2 - 3”
        Expression* expression = new SubtractExpression(
            new AddExpression(
                new NumberExpression(1),
                new NumberExpression(2)
            ),
            new NumberExpression(3)
        );

        // 3. 执行解析并输出结果
        int result = expression->interpret(context);
        cout << "C++ 解析表达式「1 + 2 - 3」，执行结果：" << result << endl; // 输出 0

        // 4. 释放内存，避免泄漏
        delete expression;
        delete context;
    } catch (const exception& e) {
        cout << "解析异常：" << e.what() << endl;
        return -1;
    }
    return 0;
}

2.5 纯C语言实现（结构体+函数指针模拟实现）

纯C无面向对象特性，通过“结构体封装数据+函数指针封装行为”模拟解释器模式的核心逻辑，依托函数指针实现统一的解释接口，通过命名约定区分终结符与非终结符表达式。底层可控性强、无额外依赖，适用于嵌入式、底层开发等资源受限场景，完整还原模式“拆分语法、组合解析”的核心思想。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 前向声明：解决结构体与函数指针的交叉引用
typedef struct Context Context;
typedef struct Expression Expression;

/// <summary>
/// 环境类（结构体）：存储解释器全局上下文
/// </summary>
typedef struct Context {
    // 可扩展添加变量映射、中间结果缓存等
} Context;

/// <summary>
/// 解释函数指针：模拟抽象表达式的Interpret方法
/// </summary>
typedef int (*InterpretFunc)(Expression*, Context*);

/// <summary>
/// 表达式结构体（模拟抽象表达式）
/// </summary>
typedef struct Expression {
    InterpretFunc interpret; // 函数指针：解释方法
    void* data;              // 存储具体数据（数字/子表达式）
} Expression;

/// <summary>
/// 终结符：数字表达式的数据结构
/// </summary>
typedef struct {
    int number; // 存储的数字值
} NumberData;

/// <summary>
/// 非终结符：加减表达式的数据结构（二元表达式通用）
/// </summary>
typedef struct {
    Expression* left;  // 左子表达式
    Expression* right; // 右子表达式
} BinaryData;

// -------------------------- 表达式解释逻辑实现 --------------------------
/// <summary>
/// 终结符：数字表达式的解释逻辑
/// </summary>
int number_interpret(Expression* expr, Context* ctx) {
    if (expr == NULL || ctx == NULL) {
        printf("警告：数字表达式或上下文为空，返回0\n");
        return 0;
    }
    NumberData* data = (NumberData*)expr->data;
    return data->number;
}

/// <summary>
/// 非终结符：加法表达式的解释逻辑
/// </summary>
int add_interpret(Expression* expr, Context* ctx) {
    if (expr == NULL || ctx == NULL) {
        printf("警告：加法表达式或上下文为空，返回0\n");
        return 0;
    }
    BinaryData* data = (BinaryData*)expr->data;
    // 递归调用左右子表达式的解释方法
    return data->left->interpret(data->left, ctx) + data->right->interpret(data->right, ctx);
}

/// <summary>
/// 非终结符：减法表达式的解释逻辑
/// </summary>
int subtract_interpret(Expression* expr, Context* ctx) {
    if (expr == NULL || ctx == NULL) {
        printf("警告：减法表达式或上下文为空，返回0\n");
        return 0;
    }
    BinaryData* data = (BinaryData*)expr->data;
    // 递归调用左右子表达式的解释方法
    return data->left->interpret(data->left, ctx) - data->right->interpret(data->right, ctx);
}

// -------------------------- 表达式创建与释放 --------------------------
/// <summary>
/// 创建数字表达式（终结符）
/// </summary>
Expression* new_number_expr(int number) {
    // 分配表达式结构体内存
    Expression* expr = (Expression*)malloc(sizeof(Expression));
    if (expr == NULL) {
        printf("内存分配失败：创建数字表达式\n");
        return NULL;
    }
    // 分配数字数据内存
    NumberData* data = (NumberData*)malloc(sizeof(NumberData));
    if (data == NULL) {
        printf("内存分配失败：创建数字表达式数据\n");
        free(expr);
        return NULL;
    }
    data->number = number;
    expr->interpret = number_interpret;
    expr->data = data;
    return expr;
}

/// <summary>
/// 创建加法表达式（非终结符）
/// </summary>
Expression* new_add_expr(Expression* left, Expression* right) {
    if (left == NULL || right == NULL) {
        printf("警告：加法表达式的左右子表达式不可为null\n");
        return NULL;
    }
    // 分配表达式结构体内存
    Expression* expr = (Expression*)malloc(sizeof(Expression));
    if (expr == NULL) {
        printf("内存分配失败：创建加法表达式\n");
        return NULL;
    }
    // 分配二元表达式数据内存
    BinaryData* data = (BinaryData*)malloc(sizeof(BinaryData));
    if (data == NULL) {
        printf("内存分配失败：创建加法表达式数据\n");
        free(expr);
        return NULL;
    }
    data->left = left;
    data->right = right;
    expr->interpret = add_interpret;
    expr->data = data;
    return expr;
}

/// <summary>
/// 创建减法表达式（非终结符）
/// </summary>
Expression* new_subtract_expr(Expression* left, Expression* right) {
    if (left == NULL || right == NULL) {
        printf("警告：减法表达式的左右子表达式不可为null\n");
        return NULL;
    }
    // 分配表达式结构体内存
    Expression* expr = (Expression*)malloc(sizeof(Expression));
    if (expr == NULL) {
        printf("内存分配失败：创建减法表达式\n");
        return NULL;
    }
    // 分配二元表达式数据内存
    BinaryData* data = (BinaryData*)malloc(sizeof(BinaryData));
    if (data == NULL) {
        printf("内存分配失败：创建减法表达式数据\n");
        free(expr);
        return NULL;
    }
    data->left = left;
    data->right = right;
    expr->interpret = subtract_interpret;
    expr->data = data;
    return expr;
}

/// <summary>
/// 递归释放表达式内存（避免内存泄漏）
/// </summary>
void free_expr(Expression* expr) {
    if (expr == NULL) return;
    // 判断表达式类型，针对性释放数据
    if (expr->interpret == number_interpret) {
        // 终结符：直接释放数据
        free(expr->data);
    } else {
        // 非终结符：递归释放左右子表达式
        BinaryData* data = (BinaryData*)expr->data;
        free_expr(data->left);
        free_expr(data->right);
        free(data);
    }
    free(expr);
}

// 客户端：构建语法树并执行解析
int main() {
    // 1. 初始化上下文
    Context* ctx = (Context*)malloc(sizeof(Context));
    if (ctx == NULL) {
        printf("内存分配失败：创建上下文\n");
        return -1;
    }

    // 2. 构建语法树：解析表达式 “1 + 2 - 3”
    Expression* addExpr = new_add_expr(new_number_expr(1), new_number_expr(2));
    Expression* subExpr = new_subtract_expr(addExpr, new_number_expr(3));
    if (subExpr == NULL) {
        printf("创建语法树失败\n");
        free_expr(addExpr);
        free(ctx);
        return -1;
    }

    // 3. 执行解析并输出结果
    int result = subExpr->interpret(subExpr, ctx);
    printf("纯C 解析表达式「1 + 2 - 3」，执行结果：%d\n", result); // 输出 0

    // 4. 释放所有资源
    free_expr(subExpr);
    free(ctx);
    return 0;
}

三、解释器模式的优缺点

解释器模式的核心优势是“高扩展性、语法模块化”，但同时存在性能损耗与维护成本的权衡。实际开发中需结合业务场景，判断是否适用该模式，避免过度设计或滥用。

3.1 核心优点

扩展性极强：新增文法规则时，只需新增对应的终结符或非终结符表达式，无需修改现有解析逻辑，完全符合“开闭原则”。例如，在现有加减表达式基础上，新增乘法表达式，仅需实现MultiplyExpression类，无需改动其他代码。
语法解析模块化：将复杂语法拆解为多个简单的表达式节点，每个节点职责单一，代码可读性高、易于理解和维护。例如，算术表达式拆分为数字、加法、减法等节点，每个节点仅处理自身的解析逻辑。
代码复用性高：相同的表达式节点可在不同的语法树中复用，例如数字表达式可同时用于加减乘除等多种运算表达式中，减少代码冗余。
易于实现简单语法：对于固定且简单的文法规则，无需依赖复杂的解析工具，通过解释器模式可快速实现解析逻辑，开发成本低。

3.2 主要缺点

性能损耗较大：语法树的解析依赖递归调用，嵌套层级越深，递归次数越多，性能损耗越明显；同时，每个表达式节点都是独立对象（或结构体），大量节点会占用较多内存，尤其在高频解析场景中，性能瓶颈突出。
维护成本高：若文法规则复杂（如支持乘除、括号、优先级、变量替换等），需定义大量的表达式类/结构体，代码量会急剧增加，后续维护和扩展的成本大幅上升。
适用场景有限：仅适用于固定且简单的文法规则，无法应对动态、复杂的语法解析场景（如完整的编程语言解释器、复杂SQL解析），此类场景更适合使用专业的解析器生成工具（如ANTLR、Yacc）。
调试难度高：语法解析过程是递归执行的，当解析出现异常时，难以定位问题所在，调试成本较高。

四、解释器模式的使用场景

解释器模式的适用场景具有明确的核心前提：文法规则固定且简单，需要自定义语法解析，且对解析性能要求不高。以下结合具体业务场景与实战案例，帮助开发者精准判断适用性，避免滥用。

4.1 核心适用场景

简单表达式计算：如计算器中的加减乘除、逻辑表达式（&&、||、!）解析，自定义公式计算（如业务系统中的折扣计算、积分计算）。
自定义配置解析：解析自定义格式的配置文件，如自定义键值对规则、简单条件配置（如“if 条件A then 执行B”），适用于轻量级配置场景。
领域特定语言（DSL）实现：实现简化版的领域特定语言，如数据库查询语言（简化版SQL）、脚本语言（如Lua子集）、规则引擎中的规则语法（如风控规则、权限规则）。
格式转换与解析：如日期格式解析（如“yyyy-MM-dd”转换为日期对象）、数据格式解析（如自定义协议数据解析）、简单模板解析（如静态模板中的变量替换）。
简单规则执行：业务规则简单且固定的场景，如工作流中的节点跳转规则、消息推送的条件规则，通过解释器模式解析规则并执行。

4.2 不适用场景

复杂语法解析场景（如完整的编程语言解释器、复杂SQL解析）：此类场景文法规则复杂，使用解释器模式会导致代码量激增、维护困难，应使用专业的解析器生成工具。
高频解析、高性能要求场景（如实时数据解析、高并发接口中的表达式计算）：解释器模式的递归解析会导致性能损耗，应使用编译期优化、逆波兰表达式等更高效的方案。
文法规则频繁变更的场景：每次规则变更都需新增或修改表达式节点，维护成本过高，不适合使用解释器模式。

五、总结

解释器模式通过“拆分语法、组合解析”的思路，将复杂的语法解释逻辑拆解为可复用的简单节点，核心价值是简化固定语法的解析逻辑并提供良好的扩展性，其本质是“语法的模块化与多态解析”。该模式让客户端无需关注具体的解析细节，只需构建语法树并调用解释方法，即可完成语法解析与执行。

从多语言实现来看，不同语言的实现风格虽有显著差异，但核心逻辑高度一致：

面向对象语言（C#、Python、C++、Golang）可直接通过接口/抽象类+多态实现，代码结构贴合解释器模式的经典定义，开发高效、可读性强；
纯C语言则通过结构体+函数指针模拟面向对象特性，虽实现过程稍繁琐，但能在资源受限的底层场景中还原模式核心价值，兼顾底层可控性。

在实际开发中，使用解释器模式需重点权衡两个核心点：一是扩展性与维护成本，若文法规则简单且稳定，解释器模式是优雅的选择；若规则复杂，需优先考虑专业解析工具；二是性能与场景适配，高频解析场景需避免使用，优先选择更高效的解析方案。

总之，解释器模式是“简单语法解析”场景下的高效解决方案，掌握其核心结构与多语言实现，能帮助开发者在实际项目中优雅处理自定义语法解析、规则执行等需求，平衡代码设计与工程落地成本，提升系统的可扩展性与可维护性。

备忘录模式

发表于 2019-11-23 更新于 2026-05-09 分类于学习笔记，设计模式

备忘录模式（Memento Pattern）是行为型设计模式的重要分支，其核心设计目标是在不破坏对象封装性的前提下，捕获对象的内部状态并将其持久化到外部容器，以便在需要时快速将对象恢复至指定历史状态。该模式完美解决了“状态保存与恢复”的核心痛点，广泛应用于撤销操作、数据回滚、快照备份等场景。本文将从核心结构拆解、多语言落地实现、优缺点深度剖析、适用场景梳理及实战总结等维度，系统解读备忘录模式的设计思想与工程实践，为开发者提供可直接复用的技术方案。

一、备忘录模式核心结构

备忘录模式的核心价值在于“封装状态、解耦管理”，通过三大核心角色的协同工作，实现状态的安全保存与灵活恢复，各角色职责边界清晰，无冗余依赖，具体定义与交互逻辑如下：

1.1 原发器（Originator）

原发器是需要进行状态管理的核心业务对象，负责两个核心操作：一是创建备忘录，即捕获自身当前的内部状态，并将状态写入备忘录对象；二是恢复状态，即从备忘录中读取历史状态，将自身恢复至该状态。原发器是唯一有权限访问备忘录内部状态的角色，确保状态的封装性。

1.2 备忘录（Memento）

备忘录是状态的“容器”，专门用于存储原发器的内部状态，其设计核心是“封装隔离”。为保证状态安全，备忘录仅暴露供原发器读写状态的接口（或仅允许原发器访问其私有状态），其他角色（如管理者）仅能持有备忘录对象，无法修改或直接访问其内部状态，避免破坏原发器的封装性。

1.3 管理者（Caretaker）

管理者是备忘录的“管家”，负责备忘录对象的生命周期管理，包括存储、获取、清理等操作，但不参与状态的读写。管理者的核心作用是解耦原发器与备忘录的直接依赖，通过统一的接口管理多个备忘录，支持多状态快照的存储与切换（如多步撤销）。

核心交互流程：原发器捕获当前状态 → 创建备忘录并写入状态 → 管理者存储备忘录 → 需恢复状态时，管理者取出指定备忘录 → 原发器从备忘录读取状态并完成恢复。

二、多语言实现备忘录模式

以“文本编辑器撤销功能”为统一实战场景，设计核心逻辑：原发器（编辑器）负责存储当前文本内容，备忘录存储文本快照，管理者管理快照列表，支持多步保存与撤销。以下提供C#、Python、Golang、C++及纯C的可运行实现，贴合各语言原生特性，补充规范注释、边界校验与资源释放逻辑，兼顾实用性与严谨性，清晰呈现模式的适配思路。

2.1 C# 实现（面向对象规范实现）

C#作为强类型面向对象语言，通过类封装备忘录状态，依托访问修饰符（private）保证备忘录的封装性，借助泛型与集合优化管理者的备忘录管理逻辑，代码结构清晰、可维护性高，适用于企业级应用的撤销/回滚场景（如办公软件、业务系统配置管理）。

using System;
using System.Collections.Generic;

/// <summary>
/// 备忘录：存储原发器（文本编辑器）的状态，仅允许原发器访问
/// </summary>
public class Memento
{
    /// <summary>
    /// 存储的文本状态（私有字段，仅通过属性供原发器访问）
    /// </summary>
    public string TextState { get; private set; }

    /// <summary>
    /// 构造函数：仅允许原发器创建备忘录（通过访问修饰符控制）
    /// </summary>
    /// <param name="textState">文本编辑器当前状态</param>
    internal Memento(string textState)
    {
        TextState = textState ?? string.Empty; // 避免空值，提升健壮性
    }
}

/// <summary>
/// 原发器：文本编辑器，负责创建/恢复备忘录，管理自身文本状态
/// </summary>
public class Originator
{
    /// <summary>
    /// 编辑器当前文本状态
    /// </summary>
    private string _currentText = string.Empty;

    /// <summary>
    /// 设置编辑器文本状态
    /// </summary>
    /// <param name="text">新文本内容</param>
    public void SetText(string text)
    {
        _currentText = text ?? string.Empty;
        Console.WriteLine($"编辑器更新状态：{_currentText}");
    }

    /// <summary>
    /// 获取当前文本状态
    /// </summary>
    /// <returns>当前文本内容</returns>
    public string GetText() => _currentText;

    /// <summary>
    /// 创建备忘录：捕获当前文本状态，生成快照
    /// </summary>
    /// <returns>包含当前状态的备忘录</returns>
    public Memento CreateMemento()
    {
        return new Memento(_currentText);
    }

    /// <summary>
    /// 从备忘录恢复状态：将编辑器恢复至备忘录存储的历史状态
    /// </summary>
    /// <param name="memento">待恢复的备忘录</param>
    public void RestoreMemento(Memento memento)
    {
        if (memento == null)
        {
            Console.WriteLine("警告：备忘录不可为null，无法恢复状态");
            return;
        }
        _currentText = memento.TextState;
        Console.WriteLine($"编辑器恢复状态：{_currentText}");
    }
}

/// <summary>
/// 管理者：管理备忘录列表，支持多快照存储与获取
/// </summary>
public class Caretaker
{
    /// <summary>
    /// 存储备忘录的队列（FIFO，适配多步撤销场景）
    /// </summary>
    private readonly Queue<Memento> _mementos = new Queue<Memento>();

    /// <summary>
    /// 最大快照数量（避免内存溢出）
    /// </summary>
    private readonly int _maxCount = 10;

    /// <summary>
    /// 添加备忘录快照
    /// </summary>
    /// <param name="memento">待存储的备忘录</param>
    public void AddMemento(Memento memento)
    {
        if (memento == null)
        {
            Console.WriteLine("警告：无法添加空备忘录");
            return;
        }
        // 超过最大快照数量，移除最旧的快照
        if (_mementos.Count >= _maxCount)
        {
            _mementos.Dequeue();
            Console.WriteLine("提示：快照数量已达上限，移除最旧快照");
        }
        _mementos.Enqueue(memento);
        Console.WriteLine($"快照添加成功，当前快照数量：{_mementos.Count}");
    }

    /// <summary>
    /// 获取最新的备忘录快照（适配一步撤销）
    /// </summary>
    /// <returns>最新的备忘录，无快照时返回null</returns>
    public Memento GetLatestMemento()
    {
        if (_mementos.Count == 0)
        {
            Console.WriteLine("警告：无历史快照可获取");
            return null;
        }
        // 队列尾部为最新快照，此处采用ToArray获取最后一个元素（不改变队列结构）
        var mementoArray = _mementos.ToArray();
        return mementoArray[^1];
    }

    /// <summary>
    /// 根据索引获取指定备忘录快照（适配多步撤销）
    /// </summary>
    /// <param name="index">快照索引</param>
    /// <returns>指定索引的备忘录，索引无效时返回null</returns>
    public Memento GetMemento(int index)
    {
        if (index < 0 || index >= _mementos.Count)
        {
            Console.WriteLine("警告：快照索引无效");
            return null;
        }
        return _mementos.ToArray()[index];
    }
}

// 客户端：测试文本编辑器的撤销功能
class Program
{
    static void Main()
    {
        try
        {
            // 1. 初始化组件
            Originator editor = new Originator();
            Caretaker caretaker = new Caretaker();

            // 2. 输入文本并保存快照
            editor.SetText("第1步：编写备忘录模式核心概念");
            caretaker.AddMemento(editor.CreateMemento());

            // 3. 继续输入并保存快照
            editor.SetText("第2步：梳理多语言实现思路");
            caretaker.AddMemento(editor.CreateMemento());

            // 4. 继续输入并保存快照
            editor.SetText("第3步：分析优缺点与使用场景");
            caretaker.AddMemento(editor.CreateMemento());

            // 5. 撤销一步（恢复到第2步状态）
            Console.WriteLine("\n=== 执行一步撤销 ===");
            editor.RestoreMemento(caretaker.GetLatestMemento());

            // 6. 再撤销一步（恢复到第1步状态）
            Console.WriteLine("\n=== 执行第二步撤销 ===");
            editor.RestoreMemento(caretaker.GetMemento(0));
        }
        catch (Exception ex)
        {
            Console.WriteLine($"执行异常：{ex.Message}");
        }
    }
}

2.2 Python 实现（动态语言简洁实现）

Python遵循“鸭子类型”，无需显式定义接口，通过类封装与属性装饰器（@property）保证备忘录的封装性，语法简洁、无冗余类型声明。依托动态特性，可灵活扩展备忘录的状态字段，无需修改核心逻辑，适用于快速开发、轻量级项目（如小型编辑器、配置工具）。

class Memento:
    """备忘录：存储文本编辑器的状态，仅允许原发器访问内部状态"""
    def __init__(self, text_state):
        # 私有字段，通过属性供原发器访问，外部无法直接修改
        self._text_state = text_state or ""

    @property
    def text_state(self):
        """供原发器读取状态的接口"""
        return self._text_state

class Originator:
    """原发器：文本编辑器，负责创建/恢复备忘录，管理自身状态"""
    def __init__(self):
        self._current_text = ""  # 编辑器当前文本状态

    def set_text(self, text):
        """设置编辑器文本状态，处理空值，提升健壮性"""
        self._current_text = text or ""
        print(f"编辑器更新状态：{self._current_text}")

    def get_text(self):
        """获取当前文本状态"""
        return self._current_text

    def create_memento(self):
        """创建备忘录，捕获当前文本状态"""
        return Memento(self._current_text)

    def restore_memento(self, memento):
        """从备忘录恢复状态，校验备忘录合法性"""
        if not isinstance(memento, Memento):
            print("警告：无效的备忘录对象，无法恢复状态")
            return
        self._current_text = memento.text_state
        print(f"编辑器恢复状态：{self._current_text}")

class Caretaker:
    """管理者：管理备忘录列表，支持多快照存储与多步撤销"""
    def __init__(self, max_count=10):
        self._mementos = []  # 存储备忘录的列表
        self._max_count = max_count  # 最大快照数量，避免内存溢出

    def add_memento(self, memento):
        """添加备忘录快照，处理空值与数量上限"""
        if not isinstance(memento, Memento):
            print("警告：无法添加无效的备忘录")
            return
        # 超过最大数量，移除最旧的快照
        if len(self._mementos) >= self._max_count:
            self._mementos.pop(0)
            print("提示：快照数量已达上限，移除最旧快照")
        self._mementos.append(memento)
        print(f"快照添加成功，当前快照数量：{len(self._mementos)}")

    def get_latest_memento(self):
        """获取最新的备忘录快照（一步撤销）"""
        if not self._mementos:
            print("警告：无历史快照可获取")
            return None
        return self._mementos[-1]

    def get_memento(self, index):
        """根据索引获取指定备忘录快照（多步撤销）"""
        if index < 0 or index >= len(self._mementos):
            print("警告：快照索引无效")
            return None
        return self._mementos[index]

# 客户端测试：模拟文本编辑器的撤销流程
if __name__ == "__main__":
    try:
        # 1. 初始化组件
        editor = Originator()
        caretaker = Caretaker(max_count=5)

        # 2. 输入文本并保存快照
        editor.set_text("第1步：编写备忘录模式核心概念")
        caretaker.add_memento(editor.create_memento())

        # 3. 继续输入并保存快照
        editor.set_text("第2步：梳理多语言实现思路")
        caretaker.add_memento(editor.create_memento())

        # 4. 继续输入并保存快照
        editor.set_text("第3步：分析优缺点与使用场景")
        caretaker.add_memento(editor.create_memento())

        # 5. 撤销一步（恢复到第2步状态）
        print("\n=== 执行一步撤销 ===")
        editor.restore_memento(caretaker.get_latest_memento())

        # 6. 再撤销一步（恢复到第1步状态）
        print("\n=== 执行第二步撤销 ===")
        editor.restore_memento(caretaker.get_memento(0))
    except Exception as e:
        print(f"执行异常：{str(e)}")

2.3 Golang 实现（接口至上轻量实现）

Go语言无类和继承，遵循“组合优于继承”原则，通过结构体封装备忘录与原发器状态，依托“小写字段”实现封装（包内可见、包外不可访问），无需额外访问修饰符。代码极简高效，贴合Go语言设计理念，适配高并发后端场景（如分布式系统配置回滚、服务状态快照）。

package main

import (
	"fmt"
)

// memento 备忘录：小写字段保证包内访问（封装），仅允许原发器访问状态
type memento struct {
	textState string // 存储的文本状态
}

// Originator 原发器：文本编辑器，负责创建/恢复备忘录
type Originator struct {
	currentText string // 编辑器当前文本状态
}

// SetText 设置编辑器文本状态，处理空值
func (o *Originator) SetText(text string) {
	if text == "" {
		o.currentText = ""
	} else {
		o.currentText = text
	}
	fmt.Printf("编辑器更新状态：%s\n", o.currentText)
}

// GetText 获取当前文本状态
func (o *Originator) GetText() string {
	return o.currentText
}

// CreateMemento 创建备忘录，捕获当前状态
func (o *Originator) CreateMemento() *memento {
	return &memento{textState: o.currentText}
}

// RestoreMemento 从备忘录恢复状态，校验备忘录合法性
func (o *Originator) RestoreMemento(m *memento) {
	if m == nil {
		fmt.Println("警告：备忘录不可为nil，无法恢复状态")
		return
	}
	o.currentText = m.textState
	fmt.Printf("编辑器恢复状态：%s\n", o.currentText)
}

// Caretaker 管理者：管理备忘录列表，支持多快照存储与撤销
type Caretaker struct {
	mementos []*memento // 存储备忘录的切片
	maxCount int        // 最大快照数量
}

// NewCaretaker 初始化管理者，指定最大快照数量
func NewCaretaker(maxCount int) *Caretaker {
	if maxCount <= 0 {
		maxCount = 10 // 默认最大快照数量
	}
	return &Caretaker{
		mementos: make([]*memento, 0, maxCount),
		maxCount: maxCount,
	}
}

// AddMemento 添加备忘录快照，处理数量上限
func (c *Caretaker) AddMemento(m *memento) {
	if m == nil {
		fmt.Println("警告：无法添加空备忘录")
		return
	}
	// 超过最大数量，移除最旧的快照
	if len(c.mementos) >= c.maxCount {
		c.mementos = c.mementos[1:]
		fmt.Println("提示：快照数量已达上限，移除最旧快照")
	}
	c.mementos = append(c.mementos, m)
	fmt.Printf("快照添加成功，当前快照数量：%d\n", len(c.mementos))
}

// GetLatestMemento 获取最新的备忘录快照（一步撤销）
func (c *Caretaker) GetLatestMemento() *memento {
	if len(c.mementos) == 0 {
		fmt.Println("警告：无历史快照可获取")
		return nil
	}
	return c.mementos[len(c.mementos)-1]
}

// GetMemento 根据索引获取指定备忘录快照（多步撤销）
func (c *Caretaker) GetMemento(index int) *memento {
	if index < 0 || index >= len(c.mementos) {
		fmt.Println("警告：快照索引无效")
		return nil
	}
	return c.mementos[index]
}

// 客户端测试：模拟文本编辑器撤销流程
func main() {
	// 1. 初始化组件
	editor := &Originator{}
	caretaker := NewCaretaker(5)

	// 2. 输入文本并保存快照
	editor.SetText("第1步：编写备忘录模式核心概念")
	caretaker.AddMemento(editor.CreateMemento())

	// 3. 继续输入并保存快照
	editor.SetText("第2步：梳理多语言实现思路")
	caretaker.AddMemento(editor.CreateMemento())

	// 4. 继续输入并保存快照
	editor.SetText("第3步：分析优缺点与使用场景")
	caretaker.AddMemento(editor.CreateMemento())

	// 5. 撤销一步（恢复到第2步状态）
	fmt.Println("\n=== 执行一步撤销 ===")
	editor.RestoreMemento(caretaker.GetLatestMemento())

	// 6. 再撤销一步（恢复到第1步状态）
	fmt.Println("\n=== 执行第二步撤销 ===")
	editor.RestoreMemento(caretaker.GetMemento(0))
}

2.4 C++ 实现（抽象类+友元经典实现）

C++通过类与友元机制实现备忘录的封装性，将原发器声明为备忘录的友元，确保只有原发器能访问备忘录的私有状态；同时通过虚析构函数与手动内存管理，避免内存泄漏。该实现兼顾灵活性与高性能，适用于底层开发、高频调用场景（如编译器撤销功能、嵌入式设备配置回滚）。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 前向声明：让管理者识别备忘录
class Memento;

/// <summary>
/// 原发器：文本编辑器，负责创建/恢复备忘录
/// 声明为Memento的友元，有权访问其私有状态
/// </summary>
class Originator {
private:
    string currentText; // 编辑器当前文本状态
public:
    Originator() : currentText("") {}

    /// <summary>
    /// 设置编辑器文本状态
    /// </summary>
    void setText(const string& text) {
        currentText = text.empty() ? "" : text;
        cout << "编辑器更新状态：" << currentText << endl;
    }

    /// <summary>
    /// 获取当前文本状态
    /// </summary>
    string getText() const {
        return currentText;
    }

    /// <summary>
    /// 创建备忘录，捕获当前状态
    /// </summary>
    Memento* createMemento();

    /// <summary>
    /// 从备忘录恢复状态
    /// </summary>
    void restoreMemento(Memento* m);
};

/// <summary>
/// 备忘录：存储文本状态，仅允许原发器访问私有成员
/// </summary>
class Memento {
private:
    string textState; // 存储的文本状态
    // 友元声明：仅Originator可访问私有成员
    friend class Originator;

    /// <summary>
    /// 私有构造函数：仅允许原发器创建备忘录
    /// </summary>
    Memento(const string& state) : textState(state) {}

    /// <summary>
    /// 私有接口：供原发器读取状态
    /// </summary>
    string getTextState() const {
        return textState;
    }
};

// 实现原发器的备忘录方法
Memento* Originator::createMemento() {
    return new Memento(currentText);
}

void Originator::restoreMemento(Memento* m) {
    if (m == nullptr) {
        cout << "警告：备忘录不可为nullptr，无法恢复状态" << endl;
        return;
    }
    currentText = m->getTextState();
    cout << "编辑器恢复状态：" << currentText << endl;
}

/// <summary>
/// 管理者：管理备忘录列表，负责内存释放
/// </summary>
class Caretaker {
private:
    vector<Memento*> mementos; // 存储备忘录指针的容器
    int maxCount; // 最大快照数量
public:
    Caretaker(int maxCount = 10) : maxCount(maxCount) {}

    /// <summary>
    /// 析构函数：释放所有备忘录内存，避免泄漏
    /// </summary>
    ~Caretaker() {
        for (auto m : mementos) {
            delete m;
            m = nullptr;
        }
        mementos.clear();
    }

    /// <summary>
    /// 添加备忘录快照
    /// </summary>
    void addMemento(Memento* m) {
        if (m == nullptr) {
            cout << "警告：无法添加空备忘录" << endl;
            return;
        }
        // 超过最大数量，移除最旧的快照并释放内存
        if (mementos.size() >= maxCount) {
            delete mementos[0];
            mementos[0] = nullptr;
            mementos.erase(mementos.begin());
            cout << "提示：快照数量已达上限，移除最旧快照" << endl;
        }
        mementos.push_back(m);
        cout << "快照添加成功，当前快照数量：" << mementos.size() << endl;
    }

    /// <summary>
    /// 获取最新的备忘录快照
    /// </summary>
    Memento* getLatestMemento() {
        if (mementos.empty()) {
            cout << "警告：无历史快照可获取" << endl;
            return nullptr;
        }
        return mementos.back();
    }

    /// <summary>
    /// 根据索引获取指定备忘录快照
    /// </summary>
    Memento* getMemento(int index) {
        if (index < 0 || index >= (int)mementos.size()) {
            cout << "警告：快照索引无效" << endl;
            return nullptr;
        }
        return mementos[index];
    }
};

// 客户端测试：模拟文本编辑器撤销流程
int main() {
    try {
        // 1. 初始化组件
        Originator* editor = new Originator();
        Caretaker* caretaker = new Caretaker(5);

        // 2. 输入文本并保存快照
        editor->setText("第1步：编写备忘录模式核心概念");
        caretaker->addMemento(editor->createMemento());

        // 3. 继续输入并保存快照
        editor->setText("第2步：梳理多语言实现思路");
        caretaker->addMemento(editor->createMemento());

        // 4. 继续输入并保存快照
        editor->setText("第3步：分析优缺点与使用场景");
        caretaker->addMemento(editor->createMemento());

        // 5. 撤销一步（恢复到第2步状态）
        cout << "\n=== 执行一步撤销 ===" << endl;
        editor->restoreMemento(caretaker->getLatestMemento());

        // 6. 再撤销一步（恢复到第1步状态）
        cout << "\n=== 执行第二步撤销 ===" << endl;
        editor->restoreMemento(caretaker->getMemento(0));

        // 释放资源
        delete editor;
        delete caretaker;
        editor = nullptr;
        caretaker = nullptr;
    } catch (const exception& e) {
        cout << "执行异常：" << e.what() << endl;
    }
    return 0;
}

2.5 纯C语言实现（结构体+函数指针模拟实现）

纯C无面向对象特性，通过“结构体封装数据+函数指针封装行为”模拟备忘录模式的核心逻辑，依托命名约定（前缀下划线）模拟私有字段，通过函数接口控制状态的读写权限，底层可控性强、无额外依赖。适用于嵌入式、底层开发等资源受限场景，完整还原模式“封装状态、解耦管理”的核心思想。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 前向声明：解决结构体与函数指针的交叉引用
typedef struct Memento Memento;
typedef struct Originator Originator;
typedef struct Caretaker Caretaker;

/// <summary>
/// 备忘录结构体：模拟私有字段（下划线前缀），仅通过接口供原发器访问
/// </summary>
typedef struct Memento {
    char* _text_state; // 存储的文本状态（模拟私有字段）
} Memento;

/// <summary>
/// 原发器结构体：文本编辑器，封装状态与方法指针
/// </summary>
typedef struct Originator {
    char* current_text; // 当前文本状态
    // 方法指针：模拟类的成员方法
    Memento* (*create_memento)(Originator*);    // 创建备忘录
    void (*restore_memento)(Originator*, Memento*); // 恢复状态
} Originator;

/// <summary>
/// 管理者结构体：管理备忘录列表
/// </summary>
typedef struct Caretaker {
    Memento** mementos; // 存储备忘录指针的数组
    int count;          // 当前快照数量
    int capacity;       // 数组容量
    int max_count;      // 最大快照数量
} Caretaker;

// -------------------------- 备忘录工具函数 --------------------------
/// <summary>
/// 创建备忘录，初始化状态
/// </summary>
Memento* memento_create(const char* text_state) {
    Memento* m = (Memento*)malloc(sizeof(Memento));
    if (m == NULL) return NULL;
    // 处理空值，避免野指针
    int len = text_state ? strlen(text_state) : 0;
    m->_text_state = (char*)malloc(len + 1);
    if (m->_text_state == NULL) {
        free(m);
        return NULL;
    }
    strcpy(m->_text_state, text_state ? text_state : "");
    return m;
}

/// <summary>
/// 销毁备忘录，释放内存
/// </summary>
void memento_destroy(Memento* m) {
    if (m == NULL) return;
    free(m->_text_state);
    free(m);
}

/// <summary>
/// 供原发器读取备忘录状态的接口（模拟私有字段访问）
/// </summary>
const char* memento_get_text_state(Memento* m) {
    if (m == NULL) return "";
    return m->_text_state;
}

// -------------------------- 原发器方法实现 --------------------------
/// <summary>
/// 原发器：创建备忘录，捕获当前状态
/// </summary>
Memento* originator_create_memento(Originator* o) {
    if (o == NULL) return NULL;
    return memento_create(o->current_text);
}

/// <summary>
/// 原发器：从备忘录恢复状态
/// </summary>
void originator_restore_memento(Originator* o, Memento* m) {
    if (o == NULL || m == NULL) {
        printf("警告：原发器或备忘录为空，无法恢复状态\n");
        return;
    }
    // 释放原有状态内存，避免泄漏
    if (o->current_text != NULL) {
        free(o->current_text);
    }
    // 复制备忘录中的状态
    const char* state = memento_get_text_state(m);
    int len = strlen(state);
    o->current_text = (char*)malloc(len + 1);
    strcpy(o->current_text, state);
    printf("编辑器恢复状态：%s\n", o->current_text);
}

/// <summary>
/// 原发器：设置文本状态
/// </summary>
void originator_set_text(Originator* o, const char* text) {
    if (o == NULL) return;
    // 释放原有状态内存
    if (o->current_text != NULL) {
        free(o->current_text);
    }
    // 处理空值
    int len = text ? strlen(text) : 0;
    o->current_text = (char*)malloc(len + 1);
    strcpy(o->current_text, text ? text : "");
    printf("编辑器更新状态：%s\n", o->current_text);
}

/// <summary>
/// 初始化原发器
/// </summary>
Originator* originator_init() {
    Originator* o = (Originator*)malloc(sizeof(Originator));
    if (o == NULL) return NULL;
    o->current_text = NULL;
    o->create_memento = originator_create_memento;
    o->restore_memento = originator_restore_memento;
    // 初始化状态为空字符串
    originator_set_text(o, "");
    return o;
}

// -------------------------- 管理者方法实现 --------------------------
/// <summary>
/// 初始化管理者
/// </summary>
Caretaker* caretaker_init(int max_count) {
    Caretaker* c = (Caretaker*)malloc(sizeof(Caretaker));
    if (c == NULL) return NULL;
    // 默认最大快照数量为10
    c->max_count = max_count <= 0 ? 10 : max_count;
    c->capacity = c->max_count;
    c->count = 0;
    c->mementos = (Memento**)malloc(sizeof(Memento*) * c->capacity);
    if (c->mementos == NULL) {
        free(c);
        return NULL;
    }
    return c;
}

/// <summary>
/// 管理者：添加备忘录快照
/// </summary>
void caretaker_add_memento(Caretaker* c, Memento* m) {
    if (c == NULL || m == NULL) {
        printf("警告：管理者或备忘录为空，无法添加快照\n");
        return;
    }
    // 超过最大数量，移除最旧快照并释放内存
    if (c->count >= c->max_count) {
        memento_destroy(c->mementos[0]);
        // 移动数组，移除第一个元素
        for (int i = 0; i < c->count - 1; i++) {
            c->mementos[i] = c->mementos[i + 1];
        }
        c->count--;
        printf("提示：快照数量已达上限，移除最旧快照\n");
    }
    c->mementos[c->count++] = m;
    printf("快照添加成功，当前快照数量：%d\n", c->count);
}

/// <summary>
/// 管理者：获取最新的备忘录快照
/// </summary>
Memento* caretaker_get_latest_memento(Caretaker* c) {
    if (c == NULL || c->count == 0) {
        printf("警告：无历史快照可获取\n");
        return NULL;
    }
    return c->mementos[c->count - 1];
}

/// <summary>
/// 管理者：根据索引获取指定备忘录快照
/// </summary>
Memento* caretaker_get_memento(Caretaker* c, int index) {
    if (c == NULL || index < 0 || index >= c->count) {
        printf("警告：快照索引无效\n");
        return NULL;
    }
    return c->mementos[index];
}

/// <summary>
/// 释放所有资源
/// </summary>
void cleanup(Originator* o, Caretaker* c) {
    // 释放原发器资源
    if (o != NULL) {
        if (o->current_text != NULL) {
            free(o->current_text);
        }
        free(o);
    }
    // 释放管理者与备忘录资源
    if (c != NULL) {
        for (int i = 0; i < c->count; i++) {
            memento_destroy(c->mementos[i]);
        }
        free(c->mementos);
        free(c);
    }
}

// 客户端测试：模拟文本编辑器撤销流程
int main() {
    // 1. 初始化组件
    Originator* editor = originator_init();
    Caretaker* caretaker = caretaker_init(5);
    if (editor == NULL || caretaker == NULL) {
        printf("初始化失败，退出程序\n");
        cleanup(editor, caretaker);
        return -1;
    }

    // 2. 输入文本并保存快照
    originator_set_text(editor, "第1步：编写备忘录模式核心概念");
    caretaker_add_memento(caretaker, editor->create_memento(editor));

    // 3. 继续输入并保存快照
    originator_set_text(editor, "第2步：梳理多语言实现思路");
    caretaker_add_memento(caretaker, editor->create_memento(editor));

    // 4. 继续输入并保存快照
    originator_set_text(editor, "第3步：分析优缺点与使用场景");
    caretaker_add_memento(caretaker, editor->create_memento(editor));

    // 5. 撤销一步（恢复到第2步状态）
    printf("\n=== 执行一步撤销 ===\n");
    editor->restore_memento(editor, caretaker_get_latest_memento(caretaker));

    // 6. 再撤销一步（恢复到第1步状态）
    printf("\n=== 执行第二步撤销 ===\n");
    editor->restore_memento(editor, caretaker_get_memento(caretaker, 0));

    // 7. 释放所有资源
    cleanup(editor, caretaker);
    return 0;
}

三、备忘录模式的优缺点

备忘录模式的核心优势的是“封装状态、灵活回滚”，但同时存在资源消耗与维护成本的权衡。实际开发中需结合业务场景，平衡设计优雅与工程落地成本，避免过度设计或滥用。

3.1 核心优点

封装性极佳：备忘录仅允许原发器访问内部状态，外部角色（如管理者）无法直接修改或访问，完美遵循“封装原则”，保证状态数据的安全性。
状态回滚灵活：支持多步快照的保存与恢复，可轻松实现撤销、回滚、快照备份等功能，无需修改原发器核心逻辑，适配多场景状态管理需求。
职责划分清晰：原发器负责状态管理，备忘录负责状态存储，管理者负责备忘录生命周期管理，三者各司其职、解耦关联，符合“单一职责原则”，提升代码可维护性。
扩展性良好：新增状态字段或扩展快照功能时，仅需修改原发器与备忘录，无需改动管理者，对现有业务逻辑侵入性低。

3.2 主要缺点

资源消耗较大：若原发器状态字段多、快照保存频繁，会产生大量备忘录对象，占用内存资源；尤其在高频保存场景（如实时编辑器），可能引发性能瓶颈。
维护成本较高：若原发器的状态结构发生变更（如新增/删除字段），备忘录需同步修改，管理者的存储逻辑也可能需要调整，增加维护成本。
并发安全风险：多线程环境下，多个线程同时读写备忘录或原发器状态，可能引发线程安全问题，需额外添加锁机制，增加代码复杂度。
序列化成本高：若需持久化备忘录（如存储到文件、数据库），需实现序列化/反序列化逻辑，尤其对于复杂状态，序列化成本较高。

四、备忘录模式的使用场景

备忘录模式的适用场景具有明确的核心前提：需要保存对象历史状态，且需支持状态回滚，同时要求不破坏对象封装性。以下结合具体业务场景与实战案例，帮助开发者精准判断适用性，避免滥用。

4.1 核心适用场景

撤销/回滚操作场景：最典型的场景是文本编辑器、表格软件的撤销功能，每输入一步保存一个快照，支持多步撤销；此外，数据库事务回滚、代码版本回滚也属于此类场景。
状态快照备份场景：如游戏存档（保存角色等级、装备、进度等状态）、虚拟机快照（保存虚拟机运行状态）、系统配置快照（保存系统当前配置），支持后续恢复至指定状态。
业务流程回溯场景：如审批流程中，保存每个节点的状态，支持回溯到任意节点重新处理；订单流程中，保存订单的状态变更记录，便于异常时回滚至正常状态。
测试场景：自动化测试中，保存测试用例的初始状态，执行测试后恢复至初始状态，避免测试用例之间的相互影响。

4.2 不适用场景

对象状态简单、无需回滚的场景，使用备忘录模式会增加代码复杂度，直接通过变量存储状态更高效。
状态频繁变更且状态量极大的场景（如实时日志、高频数据采集），大量备忘录会占用过多内存，导致性能下降。
对象封装性要求极低，允许外部直接访问状态的场景，无需通过备忘录间接管理状态。

五、总结

备忘录模式通过“原发器-备忘录-管理者”的三元结构，优雅地解决了“状态保存与恢复”的核心痛点，其核心设计思想是在不破坏对象封装性的前提下，实现状态的安全存储与灵活回滚。该模式的本质是“状态的隔离与管理”，让原发器专注于核心业务逻辑，将状态的存储与恢复交给备忘录和管理者，提升代码的可维护性与扩展性。

不同语言对备忘录模式的实现风格虽有显著差异，但核心逻辑高度一致：面向对象语言（C#、Python、Golang、C++）依托类、接口、友元等特性，轻松实现状态封装与访问控制，代码结构清晰；纯C语言则通过结构体+函数指针模拟面向对象特性，虽实现繁琐，但能在资源受限场景中还原模式核心价值，兼顾底层可控性。

使用备忘录模式时，需重点权衡两个核心点：一是资源消耗，对于高频保存、状态量大的场景，可优化为增量快照（仅保存状态变化部分）或定期清理过期快照，避免内存溢出；二是维护成本，若原发器状态频繁变更，需谨慎使用，避免因状态结构调整导致的大量代码修改。

总之，备忘录模式是“状态管理与回滚”场景下的最优解决方案之一，掌握其核心结构与多语言实现，能帮助开发者在实际项目中优雅处理撤销、快照、回滚等需求，平衡代码设计与工程落地成本，提升系统的健壮性与可扩展性。

一、 概述与目标

二、 核心对接步骤

1. 配置后端 API 基础地址

2. 修改登录认证逻辑

3. 处理用户信息

三、 页面与路由调整

1. 创建个人中心页面

2. 添加个人中心路由

3. 修改导航栏下拉菜单 (src/layout/components/Navbar.vue)

四、 测试与验证

五、 关键注意事项

六、 参考资源

一、submodule

1.引入子库

git submodule add 子库地址 保存目录

2.同步子库变化

方法一

方法二

3.复制父版本库

分步操作

合并操作

4.删除子版本库

二、subtree

1.简介

2.创建子库

3.建立关联

4.同步子库变化

5.参数--squash

6.修改子库

存在的问题

解决方案

7.抽离子库

git subtree split

什么是时间戳

Unix时间戳相互转换

C# DateTime转换为Unix时间戳

.NET 4.6新方法

通用的老方法

Unix时间戳转换为C# DateTime

.NET 4.6新方法

通用的老方法

备注

DateTimeOffset使用Now还是UtcNow

DateTime转换为DateTimeOffset

DateTime的时区信息(Kind属性)

测试代码

DateTimeOffset.Parse的默认时区

参考

一、核心概念：什么是内核模块？

二、模块管理工具对比

三、使用 modprobe（推荐方法）

3.1 准备工作：生成模块依赖关系

3.2 加载模块

3.3 卸载模块

3.4 常用 modprobe 参数详解

3.5 实用示例

四、使用 insmod 与 rmmod（基础方法）

4.1 加载模块 (insmod)

4.2 卸载模块 (rmmod)

4.3 insmod 常用参数

五、模块状态查看与系统集成

5.1 查看已加载模块

5.2 模块配置文件

5.3 开机自动加载模块

六、故障排除与最佳实践

6.1 常见错误与解决

6.2 依赖关系解析示例

6.3 最佳实践总结

七、总结对比

一、 核心概念：Ports 与 Packages

二、 安装与初始配置

1. 安装 pkg 工具

2. 配置文件 (/usr/local/etc/pkg.conf)

三、 日常包管理操作

1. 搜索软件包

2. 安装与卸载

3. 查询已安装的包

4. 更新与升级

四、 高级管理与维护

1. 包缓存管理

一、概述与目标

二、核心对接步骤

三、页面与路由调整

3. 修改导航栏下拉菜单 (`src/layout/components/Navbar.vue`)

四、测试与验证

五、关键注意事项

六、参考资源

一、`submodule`

`git submodule add 子库地址保存目录`

二、`subtree`

5.参数`--squash`

`git subtree split`

三、使用 `modprobe`（推荐方法）

3.4 常用 `modprobe` 参数详解

四、使用 `insmod` 与 `rmmod`（基础方法）

4.1 加载模块 (`insmod`)

4.2 卸载模块 (`rmmod`)

4.3 `insmod` 常用参数

一、核心概念：Ports 与 Packages

二、安装与初始配置

1. 安装 `pkg` 工具

2. 配置文件 (`/usr/local/etc/pkg.conf`)

三、日常包管理操作

四、高级管理与维护

五、包仓库（Repository）配置

六、命令速查与参考

七、重要文件与目录