练习33：链表算法

我将想你介绍涉及到排序的两个算法，你可以用它们操作链表。我首先要警告你，如果你打算对数据排序，不要使用链表，它们对于排序十分麻烦，并且有更好的数据结构作为替代。我向你介绍这两种算法只是因为它们难以在链表上完成，并且让你思考如何高效操作它们。

为了编写这本书，我打算将算法放在两个不同的文件中，和list_algos.c，之后在list_algos_test.c中编写测试。现在你要按照我的结构，因为它足以把事情做好，但是如果你使用其它的库要记住这并不是通用的结构。

这个练习中我打算给你一些额外的挑战，并且希望你不要作弊。我打算先给你单元测试，并且让你打下来。之后让你基于它们在维基百科中的描述，尝试实现这个两个算法，之后看看你的代码是否和我的类似。

• 阅读描述，并且观察任何可视化的图表。
• 在list_algos.c文案总创建函数的主干，并且创建文件，之后创建测试代码。
• 编写第一个测试并且编译所有东西。
• 回到维基百科页面，复制粘贴伪代码到你创建的函数中（不是C代码）。
• 将伪代码翻译成良好的C代码，就像我教你的那样，使用你的单元测试来保证它有效。
• 为边界情况补充一些测试，例如空链表，排序号的链表，以及其它。
• 对下一个算法重复这些过程并测试。

我只是告诉你理解大多数算法的秘密，直到你碰到一些更加麻烦的算法。这里你只是按照维基百科来实现冒泡排序和归并排序，它们是一个好的起始。

单元测试

下面是你应该通过的单元测试：

建议你从冒泡排序开始，使它正确，之后再测试归并。我所做的就是编写函数原型和主干，让这三个文件能够编译，但不能通过测试。之后你将实现填充进入之后才能够工作。

你作弊了吗？之后的练习中，我只会给你单元测试，并且让自己实现它。对于你来说，不看这段代码知道你自己实现它是一种很好的练习。下面是list_algos.c和list_algos.h的代码：

归并排序有另一种“自底向上”的实现方式，但是它太难了，我就没有选择它。就像我刚才说的那样，在链表上编写排序算法没有什么意思。你可以把时间都花在使它更快，它比起其他可排序的数据结构会相当版。链表的本质决定了如果你需要对数据进行排序，你就不要使用它们（尤其是单向的）。

你会看到什么

如果一切都正常工作，你会看到这些：

这个练习之后我就不会向你展示这样的输出了，除非有必要向你展示它的工作原理。你应该能知道我运行了测试，并且通过了所有测试。

退回去查看算法描述，有一些方法可用于改进这些实现，其中一些是很显然的：

• 归并排序做了大量的链表复制和创建操作，寻找减少它们的办法。
• 你能使用List_split和（如果你实现了的话）来改进归并排序嘛？
• 浏览所有防御性编程原则，检查并提升这一实现的健壮性，避免NULL指针，并且创建一个可选的调试级别的不变量，在排序后实现is_sorted的功能。

附加题

• 创建单元测试来比较这两个算法的性能。你需要man 3 time来查询基本的时间函数，并且需要运行足够的迭代次数，至少以几秒钟作为样本。
• 改变需要排序的链表中的数据总量，看看耗时如何变化。
• 寻找方法来创建不同长度的随机链表，并且测量需要多少时间，之后将它可视化并与算法的描述对比。
• 尝试解释为什么对链表排序十分麻烦。
• 实现（有序链表），它使用List_compare，接收一个值，将其插入到正确的位置，使链表有序。它与创建链表后再进行排序相比怎么样？