排序

要解决的问题

回想一下课堂上我们见过的几种排序算法：选择排序、冒泡排序和归并排序。

  • 选择排序 遍历列表的未排序部分，每次选择最小的元素并将其移到正确的位置。
  • 冒泡排序 每次比较一对相邻的值，如果顺序不正确则交换它们。这持续进行直到列表排序完毕。
  • 归并排序 递归地将列表反复分成两部分，然后将较小的列表按正确顺序合并回较大的列表。

在这个问题中，你将分析三个（已编译好的！）排序程序，以判断它们使用了哪种算法。在名为 sort 的文件夹中的 answers.txt 文件中，通过填写标记为 TODO 的空白来记录你的答案以及每个程序的解释。

分发代码

对于这个问题，你将需要一些”分发代码”——即由 CS50 工作人员编写的代码。提供给你的是三个已编译好的 C 程序 sort1, sort2和 sort3，以及几个用于输入的 .txt 文件和一个用于填写答案的文件 answers.txt。sort1、sort2 和 sort3 分别实现了不同的排序算法：选择排序、冒泡排序或归并排序（但不一定按此顺序！）。你的任务是判断每个文件使用的是哪种排序算法。首先下载这些文件。

下载分发文件

打开 cs50.dev.

首先点击你的终端窗口内部, 然后执行 cd 本身. 你应该发现它的”提示符”类似于下面所示。

$

点击该终端窗口内部，然后执行

wget https://cdn.cs50.net/2026/x/psets/3/sort.zip

然后按 Enter，以便将一个名为 sort.zip 的 ZIP 文件下载到你的代码空间中。注意不要遗漏 wget 和后续 URL 之间的空格，或其他任何字符！

现在执行

unzip sort.zip

来创建一个名为 sort 的文件夹。你不再需要这个 ZIP 文件，所以可以执行

rm sort.zip

然后在提示符下输入 “y” 并按 Enter 来删除你下载的 ZIP 文件。

提示

探索 .txt 文件
  • 提供了多个 .txt 文件给你。这些文件包含 n 行值，它们是逆序、随机或已排序的。
    • 例如，reversed10000.txt 包含从 10000 逆序排列的 10,000 行数字，而 random50000.txt 包含随机顺序的 50,000 行数字。
  • 不同类型的 .txt 文件可能帮助你判断哪个排序是哪个。考虑每种算法在已排序列表上的表现如何。对逆序列表呢？或随机列表呢？手动处理每种类型的一个较小列表并逐步完成每个排序过程可能会有所帮助。
用不同输入对每次排序计时
  • 要对文本文件运行排序，在终端中运行 ./[program_name] [text_file.txt]。确保你已经使用 cd 进入 sort 目录！
    • 例如，要用 sort1 对 reversed10000.txt 排序，运行 ./sort1 reversed10000.txt。
  • 你可能会发现对你的排序进行计时很有帮助。为此，运行 time ./[sort_file] [text_file.txt]。
    • 例如，你可以运行 time ./sort1 reversed10000.txt 来对 10,000 个逆序数字运行 sort1。在你的终端输出的末尾，你可以查看 real 时间来了解运行程序实际经过了多少时间。

讲解视频

不确定如何解决？

如何测试

正确性

check50 cs50/problems/2026/x/sort

如何提交

在终端中执行以下命令提交你的作业，并按提示完成操作。

submit50 cs50/problems/2026/x/sort