C语言标准库 qsort bsearch 源码实现

C语言是简洁的强大的，当然也有很多坑。C语言也是有点业界良心的，至少它实现了2个最最常用的算法：快速排序和二分查找。

我们知道，对于C语言标准库 qsort和 bsearch：

a. 它是“泛型”的，可以对任何类型进行排序或二分。

b. 我们使用时必须自定义一个比较函数当作函数指针传入。

c语言要实现泛型，基本上就只有 void指针提供的弱爆了的泛型机制，容易出错。

这篇文章中，我实现了标准库qsort和bsearch函数，最基本的正确性和泛型当然要保证了。

在这里，不涉及优化(写标准库实现的那帮人恨不得用汇编实现)，只展现算法的运行原理和泛型的实现机制。

1.C语言标准库qsort源码实现。我先呈上完整实现，然后具体剖析。

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

#include <string.h>

void swap(const void* a, const void* b, int size)

{

    assert(a != NULL && b != NULL);

    char tmp = ;

    int i = ;

    while (size > ) {

        tmp = *((char*)a + i);

        *((char*)a + i) = *((char*)b + i);

        *((char*)b + i) = tmp;

        ++i;

        --size;

    }

}

void Qsort(void* base, int left, int right, int size, int (*cmp)(const void* a, const void* b))

{

    assert(base != NULL && size >=  && cmp != NULL);    /* left may be < 0 because of the last - 1 */

    if (left >= right) return;

    char* pleft = (char*)base + left * size;

    char* pkey = (char*)base + (left + (right - left) / ) * size;

    swap(pleft, pkey, size);

    int last = left;

    char* plast = (char*)base + last * size;

    for (int i = left + ; i <= right; ++i) {

        char* pi = (char*)base + i * size;

        if (cmp(pi, pleft) < ) {

            ++last;

            plast = (char*)base + last * size;

            swap(pi, plast, size);

        }

    }

    swap(pleft, plast, size);

    Qsort(base, left, last - , size, cmp);

    Qsort(base, last + , right, size, cmp);

}

int cmp_string(const void* a, const void* b)

{

    assert(a != NULL && b != NULL);

    const char** lhs = (const char**)a;

    const char** rhs = (const char**)b;

    return strcmp(*lhs, *rhs);

}

int cmp_int(const void* a, const void* b)

{

    assert(a != NULL && b != NULL);

    const int* lhs = (const int*)a;

    const int* rhs = (const int*)b;

    if (*lhs < *rhs) {

        return -;

    } else if (*lhs == *rhs) {

        return ;

    } else {

        return ;

    }

}

int main(int argc, char* argv[])

{

    int a[] = {-, , , , , , , , , };

    int len1 = sizeof(a) / sizeof(a[]);

    fprintf(stdout, "before sort:\n");

    for (int i = ; i < len1; ++i) {

        fprintf(stdout, "%d ", a[i]);

    }

    fprintf(stdout, "\n");

    Qsort(a, , len1 - , sizeof(a[]), cmp_int);

    fprintf(stdout, "after sort:\n");

    for (int i = ; i < len1; ++i) {

        fprintf(stdout, "%d ", a[i]);

    }

    fprintf(stdout, "\n");

    const char* b[] = {"what", "chenwei", "skyline", "wel", "dmr"};

    int len2 = sizeof(b) / sizeof(b[]);

    fprintf(stdout, "before sort:\n");

    for (int i = ; i < len2; ++i) {

        fprintf(stdout, "%s-->", b[i]);

    }

    fprintf(stdout, "\n");

    Qsort(b, , len2 - , sizeof(b[]), cmp_string);

    fprintf(stdout, "after sort:\n");

    for (int i = ; i < len2; ++i) {

        fprintf(stdout, "%s-->", b[i]);

    }

    fprintf(stdout, "\n");

}

qsort基本实现在K&R里有非常详细的描述，我这里重点解释的是 swap函数，这个函数是实现泛型的基石。

首先对qsort函数原型说明几点：

a.Qsort函数原型里面没有标准库qsort的 len, 而是使用 left 和 right 来指明每次待排序的区间，用两个值来表示一个区间非常直观且优雅。

b.对于数据类型大小，我没有使用 size_t 无符号类型。

C语言中无符号类型虽然可以对数组提供负向越界保证和2倍空间，但是由于坑爹的类型提升规则滋生了N多的bug，我是尽量少用这个。

然后就是 swap函数.

首先我们知道数据元素都是以比特位形式暂存在内存中的，后简化为以字节形式暂存在内存中。

我们平常的一个 swap 函数，如果交换的数据是 int 型，我们就是:

void swap(int* a , int* b) {

     int tmp = *a;

     *a = *b;

     *b = tmp;

}

现在我们不知道元素是什么类型，那我们怎么做到泛型呢？首先传入的两个指针肯定是 void 指针，如何确定 void所指元素类型呢？其实我们这里是不需要知道元素类型的。

我们这里的目的是什么？我们就是要 交换两个元素的字节序列，我们每次交换一个字节，直到交换完为止，这样就达到目的了，这时我们就需要第三个参数：待排元素的所占字节数。

我们知道C语言中结构体是可以直接复制的，比如：

struct test {

    int a;

    char b;

};

struct test a, b;

a = b;

C语言是怎样支持这种直接复制呢？其实最终就是两个元素的字节序列的复制。注意到，如果struct里面有指针，那么这个结构体是引用语义的，两个元素的指针成员指向同一内存。

我们这里的swap函数其实就是手工模拟了类似结构体复制的整个过程。我们每次交换一个字节，总共交换的次数就是元素的sizeof大小。

注意两点：

a. 数据的字节序列是有大端小端之分的，我的这个实现是不能跨大端小端的。如果排序过程都始终都在同一机器中，那么无需担心。

b. 数据的字节序列可能是有内存对齐的，主要是在结构体之中。所以我的这个实现受机器内存对齐规则的影响，但是排序发生在同一机器中的话，这个是不会影响正确性的。

总而言之，代码实现受机器底层数据大小端表示和内存对齐策略的影响。但是实际上一个排序过程是不可能一部分进行在这台机，另一部分在另外一台机器上进行的(仅考虑单机)，所以我的这个实现是可以很好工作的。

Qsort的快排思想就很简单了，我们最需要注意的就是每次对交换元素的首字节地址进行更新，我们都是经由char*转换，因为char*所指元素正好1字节，正好模拟每次一字节的swap.

2.C语言标准库bsearch源码实现

void* Bsearch(void* base, int len, int size, const void* key, int (*cmp)(const void* a, const void* b))

{

    assert(base != NULL && len >=  && size >=  && cmp != NULL);

    int low = ;

    int high = len - ;

    while (low <= high) {

        int mid = low + (high - low) / ;

        char* pmid = (char*)base + mid * size;

        if (cmp(pmid, key) < ) {

            low = mid + ;

        } else if (cmp(pmid, key) > ) {

            high = mid - ;

        } else {

            return pmid;

        }

    }

    return NULL;

}

int cmp_int(const void* a, const void* b)

{

    assert(a != NULL && b != NULL);

    const int* lhs = (const int*)a;

    const int* rhs = (const int*)b;

    if (*lhs < *rhs) {

        return -;

    } else if (*lhs == *rhs) {

        return ;

    } else {

        return ;

    }

}

int cmp_string(const void* a, const void* b)

{

    assert(a != NULL && b != NULL);

    const char** lhs = (const char**)a;

    const char** rhs = (const char**)b;

    return strcmp(*lhs, *rhs);

}

int main(int argc, char* argv[])

{

    int a[] = {-, , , , , , , , , };

    int len1 = sizeof(a) / sizeof(a[]);

    int tmp = ;

    int* res1 = (int*)Bsearch(a, len1, sizeof(a[]), &tmp, cmp_int);

    if (res1 != NULL) {

        fprintf(stdout, "found it\n");

    } else {

        fprintf(stdout, "Not found\n");

    }

    const char* str[] = {"chenwei", "dmr", "skyline", "wel", "what"};

    int len2 = sizeof(str) / sizeof(str[]);

    const char* p = "chenwei";

    char* res2 = (char*)Bsearch(str, len2, sizeof(str[]), &p, cmp_string);

    if (res2 != NULL) {

        fprintf(stdout, "found it\n");

    } else {

        fprintf(stdout, "Not found\n");

    }

    return ;

}

欢迎大家批评指正，共同学习。转载请注明出处，谢谢。

巴特西

C语言标准库 qsort bsearch 源码实现

最新文章

热门文章