练习35：排序和搜索

    这个练习中我打算涉及到四个排序算法和一个搜索算法。排序算法是快速排序、堆排序、归并排序和基数排序。之后在你完成基数排序之后，我打算想你展示二分搜索。

    然而，我是一个懒人，大多数C标准库都实现了堆排序、快速排序和归并排序算法，你可以直接使用它们：

    这就是文件的整个实现，它在大多数现代Unix系统上都能运行。它们的每一个都使用DArray_compare对contents中储存的无类型指针进行排序。我也要向你展示这个头文件：

    1. #ifndef darray_algos_h
    2. #define darray_algos_h
    4. #include <lcthw/darray.h>
    6. typedef int (*DArray_compare)(const void *a, const void *b);
    8. int DArray_qsort(DArray *array, DArray_compare cmp);
    10. int DArray_heapsort(DArray *array, DArray_compare cmp);
    12. int DArray_mergesort(DArray *array, DArray_compare cmp);
    14. #endif

    大小几乎一样，你也应该能预料到。接下来你可以了解单元测试中这三个函数如何使用：

    你需要注意的事情是第四行testcmp的定义，它困扰了我一整天。你必须使用char **而不是char *，因为qsort会向你提供指向content数组中指针的指针。原因是qsort会打扫数组，使用你的比较函数来处理数组中每个元素的指针。因为我在contents中存储指针，所以你需要使用指针的指针。

    有了这些之后，你只需要实现三个困难的搜索算法，每个大约20行。你应该在这里停下来，不过这本书的一部分就是学习这些算法的原理，附加题会涉及到实现这些算法。

    既然你打算自己实现快速排序、堆排序和归并排序，我打算向你展示一个流行的算法叫做基数排序。它的实用性很小，只能用于整数数组，并且看上去像魔法一样。这里我打算常见一个特殊的数据结构，叫做RadixMap，用于将一个整数映射为另一个。

    下面是为新算法创建的头文件，其中也含有数据结构：

    1. #ifndef _radixmap_h
    2. #include <stdint.h>
    4. typedef union RMElement {
    5.     uint64_t raw;
    6.     struct {
    7.         uint32_t key;
    8.         uint32_t value;
    9.     } data;
    10. } RMElement;
    12. typedef struct RadixMap {
    13.     size_t max;
    14.     size_t end;
    15.     uint32_t counter;
    16.     RMElement *contents;
    17.     RMElement *temp;
    18. } RadixMap;
    21. RadixMap *RadixMap_create(size_t max);
    23. void RadixMap_destroy(RadixMap *map);
    25. void RadixMap_sort(RadixMap *map);
    27. RMElement *RadixMap_find(RadixMap *map, uint32_t key);
    29. int RadixMap_add(RadixMap *map, uint32_t key, uint32_t value);
    31. int RadixMap_delete(RadixMap *map, RMElement *el);
    33. #endif

    你看到了其中有许多和Dynamic Array或List数据结构相同的操作，不同就在于我只处理固定32位大小的uint32_t正忽视。我也会想你介绍C语言的一个新概念，叫做union。

    C联合体

    联合体是使用不同方式引用内存中同一块区域的方法。它们的工作方式，就像你把它定义为sturct，然而，每个元素共享同一片内存区域。你可以认为，联合体是内存中的一幅画，所有颜色不同的元素都重叠在它上面。

    它可以用于节约内存，或在不同格式之间转换内存块。它的第一个用途就是实现“可变类型”，你可以创建一个带有类型“标签”的结构体，之后在其中创建含有多种类型的联合体。用于在内存的不同格式之间转换时，只需要定义两个结构体，访问正确的那个类型。

    首先让我向你展示如何使用C联合体构造可变类型：

    你可以在许多动态语言实现中发现它。对于为语言中所有基本类型，代码中首先定义了一些带有变迁的可变类型，之后通常给你所创建的类型打上object标签。这样的好处就是Variant通常只需要VariantType type标签的空间，加上联合体最大成员的空间，因为C将Variant.data的每个元素堆起来，它们是重叠的，只保证有足够的空间放下最大的元素。

    接下来是实际的RadixMap对于这些操作的实现：

    1. /*
    2. * Based on code by Andre Reinald then heavily modified by Zed A. Shaw.
    3. */
    5. #include <stdio.h>
    6. #include <stdlib.h>
    7. #include <assert.h>
    8. #include <lcthw/radixmap.h>
    9. #include <lcthw/dbg.h>
    11. RadixMap *RadixMap_create(size_t max)
    12. {
    13.     RadixMap *map = calloc(sizeof(RadixMap), 1);
    15.     map->contents = calloc(sizeof(RMElement), max + 1);
    16.     check_mem(map->contents);
    18.     map->temp = calloc(sizeof(RMElement), max + 1);
    19.     check_mem(map->temp);
    21.     map->max = max;
    22.     map->end = 0;
    24.     return map;
    25. error:
    26.     return NULL;
    27. }
    29. void RadixMap_destroy(RadixMap *map)
    30. {
    31.     if(map) {
    32.         free(map->contents);
    33.         free(map->temp);
    34.         free(map);
    35.     }
    36. }
    39. #define ByteOf(x,y) (((uint8_t *)x)[(y)])
    41. static inline void radix_sort(short offset, uint64_t max, uint64_t *source, uint64_t *dest)
    42. {
    43.     uint64_t count[256] = {0};
    44.     uint64_t *cp = NULL;
    45.     uint64_t *sp = NULL;
    46.     uint64_t *end = NULL;
    47.     uint64_t s = 0;
    48.     uint64_t c = 0;
    50.     // count occurences of every byte value
    51.     for (sp = source, end = source + max; sp < end; sp++) {
    52.         count[ByteOf(sp, offset)]++;
    53.     }
    55.     // transform count into index by summing elements and storing into same array
    56.     for (s = 0, cp = count, end = count + 256; cp < end; cp++) {
    57.         c = *cp;
    58.         *cp = s;
    59.         s += c;
    60.     }
    62.     // fill dest with the right values in the right place
    63.     for (sp = source, end = source + max; sp < end; sp++) {
    64.         cp = count + ByteOf(sp, offset);
    65.         dest[*cp] = *sp;
    66.         ++(*cp);
    67.     }
    68. }
    70. void RadixMap_sort(RadixMap *map)
    71. {
    72.     uint64_t *source = &map->contents[0].raw;
    73.     uint64_t *temp = &map->temp[0].raw;
    75.     radix_sort(0, map->end, source, temp);
    76.     radix_sort(1, map->end, temp, source);
    77.     radix_sort(2, map->end, source, temp);
    78.     radix_sort(3, map->end, temp, source);
    79. }
    81. RMElement *RadixMap_find(RadixMap *map, uint32_t to_find)
    82. {
    83.     int high = map->end - 1;
    84.     RMElement *data = map->contents;
    86.     while (low <= high) {
    87.         int middle = low + (high - low)/2;
    88.         uint32_t key = data[middle].data.key;
    90.         if (to_find < key) {
    91.             high = middle - 1;
    92.         } else if (to_find > key) {
    93.             low = middle + 1;
    94.         } else {
    95.             return &data[middle];
    96.         }
    97.     }
    100. }
    102. int RadixMap_add(RadixMap *map, uint32_t key, uint32_t value)
    103. {
    104.     check(key < UINT32_MAX, "Key can't be equal to UINT32_MAX.");
    106.     RMElement element = {.data = {.key = key, .value = value}};
    107.     check(map->end + 1 < map->max, "RadixMap is full.");
    109.     map->contents[map->end++] = element;
    111.     RadixMap_sort(map);
    113.     return 0;
    115. error:
    116.     return -1;
    117. }
    119. int RadixMap_delete(RadixMap *map, RMElement *el)
    120. {
    121.     check(map->end > 0, "There is nothing to delete.");
    122.     check(el != NULL, "Can't delete a NULL element.");
    124.     el->data.key = UINT32_MAX;
    126.     if(map->end > 1) {
    127.         // don't bother resorting a map of 1 length
    128.         RadixMap_sort(map);
    129.     }
    131.     map->end--;
    133.     return 0;
    134. error:
    135.     return -1;
    136. }

    像往常一样键入它并使它通过单元测试，之后我会解释它。尤其要注意radix_sort函数，我实现它的方法非常特别。

    我不应该向你解释关于测试的过多东西，它只是模拟将随机正是放入RadixMap，确保你可以可靠地将其取出。也不是非常有趣。

    在radixmap.c中的大多数操作都易于理解，如果你阅读代码的话。下面是每个基本函数作用及其工作原理的描述：

    RadixMap_create

    像往常一样，我分配了结构体所需的内存，结构体在radixmap.h中定义。当后面涉及到radix_sort时我会使用temp和contents。

    RadixMap_destroy

    同样，销毁我所创建的东西。

    radix_sort

    这个数据结构的灵魂，我会在下一节中解释其作用。

    RadixMap_sort

    它使用了radix_sort函数来实际对contents进行排序。

    RadixMap_find

    使用二分搜索算法来寻找提供的key，我之后会解释它的原理。

    使用RadixMap_sort函数，它会在末尾添加key和value，然后简单地重新排序使一切元素都有序。一旦排序完，RadixMap_find会正确工作，因为它是二分搜索。

    RadixMap_delete

    工作方式类似RadixMap_add，除了“删除”结构中的元素，通过将它们的值设为无符号的32为整数的最大值，也就是UINT32_MAX。这意味着你不能使用这个值作为合法的键，但是它是元素删除变得容易。简单设置它之后排序，它会被移动到末尾，这就算删除了。

    学习我所描述的代码，接下来还剩RadixMap_sort，radix_sort和RadixMap_find需要了解。

    RadixMap_find 和二分搜索

    我首先以二分搜索如何实现开始。二分搜索是一种简单算法，大多数人都可以直观地理解。实际上，你可以取一叠游戏卡片（或带有数字的卡片）来手动操作。下面是该函数的工作方式，也是二分搜索的原理：

    • 基于数组大小设置上界和下界。
    • 获取上下界之间的中间元素。
    • 如果键小于这个元素的值，就一定在它前面，所以上界设置为中间元素。
    • 如果键大于这个元素的值，就一定在它后面，所以下界设置为中间元素。
    • 继续循环直到上界和下界越过了彼此。如果退出了循环则没有找到。

    你实际上所做的事情是，通过挑选中间的值来比较，猜出key可能的位置。由于数据是有序的，你知道key一定会在它前面或者后面，这样就能把搜索区域分成两半。之后你继续搜索知道找到他，或者越过了边界并穷尽了搜索空间。

    如果你事先手动模拟基数排序，它就很易于理解。这个算法利用了一个现象，数字都以十进制字符的序列来表示，按照“不重要”到“重要”的顺序排列。之后它通过十进制字符来选取数字并且将它们储存在桶中，当它处理完所有字符时，数字就排好序了。一开始它看上去像是魔法，浏览代码也的确如此，但是你要尝试手动执行它。

    为了解释这个算法，需要先写下一组三位的十进制数，以随机的顺序，假设就是223、912、275、100、633、120 和 380。

    • 按照它们的个位，将数字放入桶中：[380, 100, 120], [912], [633, 223], [275]。
    • 现在遍历每个桶中的数字，接着按十位排序：[100], [912], [120, 223], [633], [275], [380]。
    • 现在每个桶都包含了按照个位和十位排序后的数字。接着我需要按照这个顺序遍历，并把它们放入最后百位的桶中：[100, 120], [223, 275], [380], [633], [912]。
    • 到现在为止，每个数字都按照百位、十位和个位排序，并且如果我按照顺序遍历每个桶，我会得到最终排序的结果：100, 120, 223, 275, 380, 633, 912。

    确保你多次重复了这个过程，便于你理解它如何工作。这实在是一种机智的算法，并且最重要的是它对于任何大小的数字都有效。所以你可以用它来排序比较大的数字，因为你一次只是处理一位。

    在我的环境下，“字符”是独立的8位字节，所以我需要256个桶来储存这些数字按照字节的分布结果。我需要一种方法来储存它，并且不需要花费太多的空间。如果你查看radix_sort，首先我会构建count直方图，便于我了解对于给定的offset，每个字节的频率。

    一旦我知道了每一种字节的数量（共有256种），我就可以将目标数组用于存储这些值的分布。比如，如果0x00的数量为10个，我就可以将它们放在目标数组的前10个位置中。这可以让我索引到它们在目标数组中的位置，这就是radix_sort中的第二个for循环。

    最后，当我知道它们在目标数组中储存在哪里，我只是遍历source数组对于当前offset的所有字节，并且将数值按顺序放入它们的位置中。ByteOf宏的使用有助于保持代码整洁，因为它需要一些指针的黑魔法，但是最后当for循环结束之后，所有整数都会按照它们的字节放入桶中。

    我在RadixMap_sort中对这些64位的整数按照它们的前32位进行排序，这非常有意思。还记得我是如何将键和值放入RMElement类型的联合体了吗？这意味着如果要按照键来对这个数组排序，我只需要对每个整数前4个字节（32位/8位每字节）进行排序。

    如果你观察RadixMap_sort，你会看到我获取了contents和temp的便利指针，用于源数组和目标数组，之后我四次调用radix_sort。每次调用我将源数组和目标数组替换为下一字节的情况。当我完成时，radix_sort就完成了任务，并且contents中也有了最后的结果。

    如何改进

    有两个方法可以用于改进这个实现：

    • 使用二分搜索来寻找新元素的最小位置，只对这个位置到微末之间进行排序。你需要找到它，将新元素放到末尾，之后对它们之间进行排序。大多数情况下这会显著地缩减排序范围。
    • 跟踪当前所使用的最大的键，之后只对足够的位数进行排序，来处理这个键。你也可以跟踪最小的数值，之后只对范围中必要的字节进行排序。为了这样做，你需要关心CPU的整数存储顺序（大小端序）。
    • 实现快速排序、堆排序和归并排序，并且提供一个#define让其他人在二者（标准库和你的实现）当中进行选择，或者创建另一套不同名称的函数。使用我教给你的技巧，阅读维基百科的算法页面，之后参照伪代码来实现它。
    • 对比你的实现和标准库实现的性能。
    • 使用这些排序函数创建DArray_sort_add，它可以向DArray添加元素，但是随后对数组排序。