前言 lab13 实现了 counting sort 和 radix sort。 counting sort 目标：寻求一种使得 counting sort 能够处理负数的方法 [9, -1, 3, 5, -1, -2, 1] 思路：创建两个counts数组，一个统计正数的出现次数，记为countPos；一个统计负数的出现次数，记为countNe。然后根据这两个count数组，再创建两个starts数组，一个存储正数的位置，一个存储负数的位置。之后根据两个starts数组填充sorted数组即可。 一些注意事项： startsPos 存储正数位置时要加上一个等于负数个数的偏移量 注意处理负数时要加绝对值 下方是示例代码： public static int[] betterCountingSort(int[] arr) { // TODO make counting sort work with arrays containing negative numbers. // find max int max = Integer.MIN_VALUE; for (int i : arr) { max = max > i ? max : i; } // find min int min = Integer.MAX_VALUE; for (int i : arr) { min = min < i ? min : i; } int neNum = 0; int[] countPos = new int[max + 1]; int[] countNe = new int[Math.abs(min) + 1]; for (int i : arr) { if (i >= 0) { countPos[i]++; } else { countNe[Math.abs(i)]++; neNum++; } } int[] startsPos = new int[max + 1]; int[] startsNe = new int[Math.abs(min) + 1]; int pos = 0; for (int i = 0; i < startsPos.length; i += 1) { startsPos[i] = pos + neNum; pos += countPos[i]; } pos = 0; for (int i = startsNe.length - 1; i >= 0; i -= 1) { startsNe[i] = pos; pos += countNe[i]; } int size = arr.length; int[] sorted = new int[size]; for (int i = 0; i < size; i += 1) { int item = arr[i]; int place; if (item >= 0) { place = startsPos[item]; startsPos[item] += 1; } else { int absItem = Math.abs(item); place = startsNe[absItem]; startsNe[absItem] += 1; } sorted[place] = item; } return sorted; } radix sort 目标：基于 LSD radix sort 算法按照字典序排序一个 ASCII 字符串数组，注意排序数字和字符串的区别（字符串长度不同时右边填充占位符） ...

这是一个测试

课后习题 问：对下面的三个序列对，对每一对序列，判断第二个序列是否会出现在第一个序列的排序过程中。 答：考察插入排序、归并排序、快速排序、堆排序。我觉得这道题的难点在于要在20分钟之内解决。（试卷11道题只给了110分钟，本题占据最高的3分） 问：为什么Java的Arrays.sort对int、long、char这样的基本数据类型数组采用快排，但对对象类型数组却采用归并排序呢？ 答：经过一番查阅，这个问题的答案应该是稳定性。快排是不稳定的（61B的讲义提到稳不稳定取决于分区策略，我有点迷茫了），而归并排序是稳定的。我们希望排序对象类型数组时它是稳定的，所以才采用归并排序。比如讲义中提到的将学生根据名称排序，如果名称相同则再根据学分排序。在这里如果排序算法不稳定，那么学分排序之后名称相同的学生的相对顺序就会被破坏。

前言 本节课程讲述的内容如下： 快速排序（quicksort）算法的起源 快速排序算法描述 快速排序算法性能 起源 快速排序算法（以下简称快排）是一个名为 Tony Hoare 的人提出的。他当时在开发一个将英文翻译为俄文的程序，具体的实现思路是在遇见一个英文单词时利用二分查找算法在字典中查找该英文单词对应的俄文单词并进行相应的替换。 在理想的情况下，如果字典的长度是D，那么执行一次二分查找的时间复杂度是$\Theta(logD)$，所以将N个英文单词翻译为对应俄文单词的时间复杂度就为$\Theta(NlogD)$（执行N次二分查找）。然而现实并没有这么理想，因为字典信息存储在磁带上，所以从后面的单词跳到前面的单词就需要移动磁带，这会花费一定的时间，所以执行二分查找的时间复杂度并不是$O(logD)$。解决这个问题的办法就是让磁带不会来回移动而是一直往后走，实现该目标的措施就是事先排序英文句子，所以Tone Hoare就需要找到一个能够排序英文句子的算法，这就引出了快排。 算法描述 快排的核心是一个称为分区（partition）的操作，分区指的是选中数组的某个元素（这个被选中的元素成为pivot），经过一些步骤使得pivot左边的元素都小于等于pivot，而pivot右边的元素都大于等于pivot（这个过程中pivot在数组中的位置可能会也可能不会改变）。 课后习题 问：找到快排一个最坏情况下的输入（假设总选择最左边的元素作为pivot） 答：最坏情况出现在pivot分区后总落在数组的第一个位置，这种情况对应的输入可以是 [1, 2, 3, 4, 5] 问：快排在最好、最坏、平均情况下的递归深度是多少？ 答：分区的次数和递归深度相等，假设总选择最左边的元素作为pivot，那么： 最好情况：最好情况下会进行$O(log^n)$次分区，所以最好情况下的递归深度是$O(log^n)$ 最坏情况：最坏情况下会进行N次分区，所以最坏情况下的递归深度是$O(n)$ 平均情况：$O(log^n)$ 问：假设采用的分区策略是将元素分为3类： 小于pivot 等于pivot 大于pivot 假设该分区策略的运行时间是$\Theta(N)$，证明一个快排对一个长为N但仅有7个不同元素的数组的运行时间是$\Theta(N)$。（比如[0, 1, 0, 0, 6, 6, 5, 5, 4, 2, 2, 0, 3, 0, 1, …, 2, 6]） 由于每次分区至少都会排除一个键的所有元素，所以最多会进行7次分区。 问：找到一个使得Arrays.sort 崩溃（crash）的整型数组。Arrays.sort(int[])使用的排序算法是快排。更多细节参阅 A Killer Adversary for Quicksort。 答：一个使得Arrays.sort崩溃的输入必然是由于快排的性能过差导致的，根据讲义可以知道，快排性能退化的原因是分区后pivot落在了导致左右两个子数组长度极不均衡的位置，这会导致分区次数的增加从而对性能产生影响。所以现在要找到一个使得分区落点不平衡的输入，关键的问题是如何找到？ 之前的问题可以知道快排对近乎有序的数组性能很差，但在构造一个很大的有序数组并传给Arrays.sort后程序并没有崩溃，猜测内部做了一些优化。看起来必须依照论文给出的方法构造输入。

前言 汇总我的计算机学习资源 Web 开发 Web 开发跟随 MDN 的脚步即可，学习完毕之后上手 React 或者 Vue 的官方教程应该就没什么问题了。 HTML CSS 教程 JavaScript 编程语言 Python 官方教程 python 之禅 学完以上两个，或能写出地道的 python 代码。 Python 语言基础 50 课：讲的挺好的，适合入门。 FastAPI 官方教程-中文版 他人总结的 FastAPI 最佳实践 Git Pro git-中文版：2014 年的书籍了，稍微有些过时。此外中文版的翻译不是很好。 Learn Git Branching 重命名分支 配置代理 Tmux（终端复用器） Tmux 使用教程-阮一峰 Tmux 使用手册 软件工程 MIT 6.031 软件构造 6.031 中文翻译-工大李秋豪 数据库 w3School-sql SQL样式指南：描述SQL语句的编写规范等，有一款名为 Prettier SQL VSCode 的插件支持这种格式。 Go 官方教程 Go 指南中文版 Effective Go 中文版 Go 入门指南 Gin 框架文档-中文版

前言 本篇文章描述了如何基于Hugo和Github Page搭建一个私人博客。 Hugo配置 从此处下载Hugo的exe文件然后解压到某个文件夹中，之后配置相应的环境变量。 Github Page 配置 根据官方文档的描述，需要利用github的workflow完成hugo网页的部署。 这里一定要注意博客目录本身要和远程仓库关联起来。 引用 如果遇到了一些问题，可以参看此处的文章。