# 练习33：链表算法

## 冒泡排序和归并排序

• 阅读描述，并且观察任何可视化的图表。
• 使用方框和线条在纸上画出算法，或者使用一些带有数字的卡片（比如扑克牌），尝试手动执行算法。这会向你形象地展示算法的执行过程。
• `list_algos.c`文案总创建函数的主干，并且创建`list_algos.h`文件，之后创建测试代码。
• 编写第一个测试并且编译所有东西。
• 回到维基百科页面，复制粘贴伪代码到你创建的函数中（不是C代码）。
• 将伪代码翻译成良好的C代码，就像我教你的那样，使用你的单元测试来保证它有效。
• 为边界情况补充一些测试，例如空链表，排序号的链表，以及其它。
• 对下一个算法重复这些过程并测试。

## 单元测试

``````#include "minunit.h"
#include <lcthw/list_algos.h>
#include <assert.h>
#include <string.h>

char *values[] = {"XXXX", "1234", "abcd", "xjvef", "NDSS"};
#define NUM_VALUES 5

List *create_words()
{
int i = 0;
List *words = List_create();

for(i = 0; i < NUM_VALUES; i++) {
List_push(words, values[i]);
}

return words;
}

int is_sorted(List *words)
{
LIST_FOREACH(words, first, next, cur) {
if(cur->next && strcmp(cur->value, cur->next->value) > 0) {
debug("%s %s", (char *)cur->value, (char *)cur->next->value);
return 0;
}
}

return 1;
}

char *test_bubble_sort()
{
List *words = create_words();

// should work on a list that needs sorting
int rc = List_bubble_sort(words, (List_compare)strcmp);
mu_assert(rc == 0, "Bubble sort failed.");
mu_assert(is_sorted(words), "Words are not sorted after bubble sort.");

// should work on an already sorted list
rc = List_bubble_sort(words, (List_compare)strcmp);
mu_assert(rc == 0, "Bubble sort of already sorted failed.");
mu_assert(is_sorted(words), "Words should be sort if already bubble sorted.");

List_destroy(words);

// should work on an empty list
words = List_create(words);
rc = List_bubble_sort(words, (List_compare)strcmp);
mu_assert(rc == 0, "Bubble sort failed on empty list.");
mu_assert(is_sorted(words), "Words should be sorted if empty.");

List_destroy(words);

return NULL;
}

char *test_merge_sort()
{
List *words = create_words();

// should work on a list that needs sorting
List *res = List_merge_sort(words, (List_compare)strcmp);
mu_assert(is_sorted(res), "Words are not sorted after merge sort.");

List *res2 = List_merge_sort(res, (List_compare)strcmp);
mu_assert(is_sorted(res), "Should still be sorted after merge sort.");
List_destroy(res2);
List_destroy(res);

List_destroy(words);
return NULL;
}

char *all_tests()
{
mu_suite_start();

mu_run_test(test_bubble_sort);
mu_run_test(test_merge_sort);

return NULL;
}

RUN_TESTS(all_tests);
``````

## 实现

``````#ifndef lcthw_List_algos_h
#define lcthw_List_algos_h

#include <lcthw/list.h>

typedef int (*List_compare)(const void *a, const void *b);

int List_bubble_sort(List *list, List_compare cmp);

List *List_merge_sort(List *list, List_compare cmp);

#endif
``````
``````#include <lcthw/list_algos.h>
#include <lcthw/dbg.h>

inline void ListNode_swap(ListNode *a, ListNode *b)
{
void *temp = a->value;
a->value = b->value;
b->value = temp;
}

int List_bubble_sort(List *list, List_compare cmp)
{
int sorted = 1;

if(List_count(list) <= 1) {
}

do {
sorted = 1;
LIST_FOREACH(list, first, next, cur) {
if(cur->next) {
if(cmp(cur->value, cur->next->value) > 0) {
ListNode_swap(cur, cur->next);
sorted = 0;
}
}
}
} while(!sorted);

return 0;
}

inline List *List_merge(List *left, List *right, List_compare cmp)
{
List *result = List_create();
void *val = NULL;

while(List_count(left) > 0 || List_count(right) > 0) {
if(List_count(left) > 0 && List_count(right) > 0) {
if(cmp(List_first(left), List_first(right)) <= 0) {
val = List_shift(left);
} else {
val = List_shift(right);
}

List_push(result, val);
} else if(List_count(left) > 0) {
val = List_shift(left);
List_push(result, val);
} else if(List_count(right) > 0) {
val = List_shift(right);
List_push(result, val);
}
}

return result;
}

List *List_merge_sort(List *list, List_compare cmp)
{
if(List_count(list) <= 1) {
return list;
}

List *left = List_create();
List *right = List_create();
int middle = List_count(list) / 2;

LIST_FOREACH(list, first, next, cur) {
if(middle > 0) {
List_push(left, cur->value);
} else {
List_push(right, cur->value);
}

middle--;
}

List *sort_left = List_merge_sort(left, cmp);
List *sort_right = List_merge_sort(right, cmp);

if(sort_left != left) List_destroy(left);
if(sort_right != right) List_destroy(right);

return List_merge(sort_left, sort_right, cmp);
}
``````

## 你会看到什么

``````\$ make clean all
rm -rf build src/lcthw/list.o src/lcthw/list_algos.o tests/list_algos_tests tests/list_tests
rm -f tests/tests.log
find . -name "*.gc*" -exec rm {} \;
rm -rf `find . -name "*.dSYM" -print`
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list.o src/lcthw/list.c
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  -fPIC   -c -o src/lcthw/list_algos.o src/lcthw/list_algos.c
ar rcs build/liblcthw.a src/lcthw/list.o src/lcthw/list_algos.o
ranlib build/liblcthw.a
cc -shared -o build/liblcthw.so src/lcthw/list.o src/lcthw/list_algos.o
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list_algos_tests.c   -o tests/list_algos_tests
cc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG  build/liblcthw.a    tests/list_tests.c   -o tests/list_tests
sh ./tests/runtests.sh
Running unit tests:
----
RUNNING: ./tests/list_algos_tests
ALL TESTS PASSED
Tests run: 2
tests/list_algos_tests PASS
----
RUNNING: ./tests/list_tests
ALL TESTS PASSED
Tests run: 6
tests/list_tests PASS
\$
``````

## 如何改进

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

## 附加题

• 创建单元测试来比较这两个算法的性能。你需要`man 3 time`来查询基本的时间函数，并且需要运行足够的迭代次数，至少以几秒钟作为样本。
• 改变需要排序的链表中的数据总量，看看耗时如何变化。
• 寻找方法来创建不同长度的随机链表，并且测量需要多少时间，之后将它可视化并与算法的描述对比。
• 尝试解释为什么对链表排序十分麻烦。
• 实现`List_insert_sorted`（有序链表），它使用`List_compare`，接收一个值，将其插入到正确的位置，使链表有序。它与创建链表后再进行排序相比怎么样？
• 尝试实现维基百科上“自底向上”的归并排序。上面的代码已经是C写的了，所以很容易重新创建，但是要试着理解它的工作原理，并与这里的低效版本对比。