算法库

C 里面能称为算法库一部分的，只有 <stdlib.h> 里面的两个函数：二分查找和排序。

排序函数 qsort()

不要被名称误导

虽然叫 qsort，名字中带 quick 的首字母 q，但它未必使用快速排序算法实现。它甚至不保证时间复杂度（快速排序平均时间复杂度是 $O(n\lg n)$）。

函数原型

void qsort(void *ptr, size_t count, size_t size, int (*compare)(const void *, const void *));

其中：

• ptr 是指向要排序的数组的指针；
• count 是数组中元素的个数；
• size 是数组中每个元素的大小；
• compare 是一个比较函数，用于确定数组中元素的顺序。

比较函数

compare 函数的原型如下：

int compare(const void *a, const void *b);

如果 a 应该排在 b 之前，则返回负值；如果两者相等，则返回零；如果 a 应该排在 b 之后，则返回正值。也就是说：如果 a 小于 b 时返回正值，则从大到小排序；如果 a 大于 b 时返回负值，则从小到大排序。

注意类型转换

在比较函数中，需要将 const void * 类型的参数转换为实际数据类型，以便进行比较。比如，如果要比较 int 类型的数组：

int compare(const void *a, const void *b) {
    int n1 = *(const int *)a;
    int n2 = *(const int *)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;

    // 可以如此缩写
    // return (n1 > n2) - (n1 < n2);

    // 以下写法不合适：如果整数溢出，会引发未定义行为。
    // return *(const int *)a - *(const int *)b;
}

示例代码

1. 整数数组排序

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

int compare_ints(const void* a, const void* b)
{
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;

    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}

int main(void)
{
    int ints[] = {-2, 99, 0, -743, 2, INT_MIN, 4};
    size_t size = sizeof ints / sizeof ints[0];

    qsort(ints, size, sizeof(int), compare_ints);

    for (size_t i = 0; i < size; i++)
        printf("%d ", ints[i]);

    printf("\n");
}

可能的输出：

-2147483648 -743 -2 0 2 4 99

2. 字符串数组排序

#include <stdio.h>
#include <stdlib.h>

int compare_strings(const void* a, const void* b)
{
    // 注意 a 和 b 应该被转换为指向 char * 的指针
    char *arg1 = *(char **)a;
    char *arg2 = *(char **)b;

    return strcmp(arg1, arg2);
}

int main(void)
{
    char *names[] = {"John", "Paul", "George", "Ringo"};
    size_t size = sizeof names / sizeof names[0];

    qsort(names, size, sizeof(char *), compare_strings);

    for (size_t i = 0; i < size; i++)
        printf("%s ", names[i]);

    printf("\n");
}

可能的输出：

George John Paul Ringo

3. 结构体数组排序

由大到小排序

这个示例代码把分数从大到小排序。 比较函数中返回值是 (a < b) - (a > b)，当 a < b 时返回 1，当 a > b 时返回 -1。

#include <stdio.h>
#include <stdlib.h>
struct frac {
    int n, d;
};

struct frac arr[6] = {{1, 3}, {3, 4}, {2, 5}, {4, 3}, {2, 7}, {-2, 3}};

int compare_fracs(const void* p1, const void* p2)
{
    struct frac f1 = *(const struct frac*)p1;
    struct frac f2 = *(const struct frac*)p2;
    double a = (double)f1.n / f1.d;
    double b = (double)f2.n / f2.d;
    return (a < b) - (a > b);
}

int main(void)
{
    size_t size = sizeof arr / sizeof arr[0];

    qsort(arr, size, sizeof arr[0], compare_fracs);

    for (size_t i = 0; i < size; ++i) {
        printf("%d/%d ", arr[i].n, arr[i].d);
    }
    return 0;
}

可能的输出：

4/3 3/4 2/5 1/3 2/7 -2/3

二分查找函数 bsearch()

原型

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compare)(const void *, const void *));

其中：

• key 是指向要搜索的键值的指针；
• base 是指向要搜索的数组的指针；
• nmemb 是数组中元素的个数；
• size 是数组中每个元素的大小；
• compare 是一个比较函数，用于确定元素的顺序。这个函数的原型与 qsort() 中的比较函数的原型相同。

如果找到匹配的元素，则返回指向该元素的指针；否则返回空指针。

示例

#include <stdio.h>
#include <stdlib.h>

int compare_ints(const void* a, const void* b)
{
    int arg1 = *(const int*)a;
    int arg2 = *(const int*)b;
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    return 0;
}
int main(void)
{
    int ints[] = {-2, 99, 0, -743, 2, INT_MIN, 4};
    size_t size = sizeof ints / sizeof ints[0];
    qsort(ints, size, sizeof(int), compare_ints);
    int key = 2;
    int* result = bsearch(&key, ints, size, sizeof(int), compare_ints);
    if (result)
        printf("Found %d\n", *result);
    else
        printf("Not found\n");
}

#include <stdio.h>
#include <stdlib.h>
int compare_strings(const void* a, const void* b)
{
    // 注意 a 和 b 应该被转换为指向 char * 的指针
    char *arg1 = *(char **)a;
    char *arg2 = *(char **)b;
    return strcmp(arg1, arg2);
}
int main(void)
{
    char *names[] = {"John", "Paul", "George", "Ringo"};
    size_t size = sizeof names / sizeof names[0];
    qsort(names, size, sizeof(char *), compare_strings);
    char key[] = "George";
    char** result = bsearch(&key, names, size, sizeof(char *), compare_strings);
    if (result)
        printf("Found %s\n", *result);
    else
        printf("Not found\n");
}

#include <stdio.h>
#include <stdlib.h>
struct frac {
    int n, d;
};
struct frac arr[6] = {{1, 3}, {3, 4}, {2, 5}, {4, 3}, {2, 7}, {-2, 3}};
int compare_fracs(const void* p1, const void* p2)
{
    struct frac f1 = *(const struct frac*)p1;
    struct frac f2 = *(const struct frac*)p2;
    double a = (double)f1.n / f1.d;
    double b = (double)f2.n / f2.d;
    return (a < b) - (a > b);
}
int main(void)
{
    size_t size = sizeof arr / sizeof arr[0];
    qsort(arr, size, sizeof arr[0], compare_fracs);
    struct frac key = {4, 3};
    struct frac* result = bsearch(&key, arr, size, sizeof arr[0], compare_fracs);
    if (result)
        printf("Found %d/%d\n", result->n, result->d);
    else
        printf("Not found\n");
}