C语言标准库qsortbsearch源码实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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 = 0;
    int i = 0;
    while (size > 0) {
        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 >= 1 && 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) / 2) * size;
    swap(pleft, pkey, size);
    int last = left;
    char* plast = (char*)base + last * size;
    for (int i = left + 1; i <= right; ++i) {
        char* pi = (char*)base + i * size;
        if (cmp(pi, pleft) < 0) {
            ++last;
            plast = (char*)base + last * size;
            swap(pi, plast, size);
        }
    }
    swap(pleft, plast, size);
    Qsort(base, left, last - 1, size, cmp);
    Qsort(base, last + 1, 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 -1;
    } else if (*lhs == *rhs) {
        return 0;
    } else {
        return 1;
    }
}

int main(int argc, char* argv[])
{
    int a[] = {-2, 0, 5, 1, 10, 8, 5, 4, 3, 9};
    int len1 = sizeof(a) / sizeof(a[0]);
    fprintf(stdout, "before sort:\n");
    for (int i = 0; i < len1; ++i) {
        fprintf(stdout, "%d ", a[i]);
    }
    fprintf(stdout, "\n");

    Qsort(a, 0, len1 - 1, sizeof(a[0]), cmp_int);
    fprintf(stdout, "after sort:\n");
    for (int i = 0; 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[0]);
    fprintf(stdout, "before sort:\n");
    for (int i = 0; i < len2; ++i) {
        fprintf(stdout, "%s-->", b[i]);
    }
    fprintf(stdout, "\n");

    Qsort(b, 0, len2 - 1, sizeof(b[0]), cmp_string);
    fprintf(stdout, "after sort:\n");
    for (int i = 0; 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 >= 0 && size >= 1 && cmp != NULL);
    int low = 0;
    int high = len - 1; 
    while (low <= high) {
        int mid = low + (high - low) / 2;
        char* pmid = (char*)base + mid * size;
        if (cmp(pmid, key) < 0) {
            low = mid + 1;
        } else if (cmp(pmid, key) > 0) {
            high = mid - 1;
        } 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 -1;
    } else if (*lhs == *rhs) {
        return 0;
    } else {
        return 1;
    }
}

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[] = {-2, 0, 1, 3, 4, 5, 5, 8, 9, 10};
    int len1 = sizeof(a) / sizeof(a[0]);

    int tmp = 5;
    int* res1 = (int*)Bsearch(a, len1, sizeof(a[0]), &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[0]);
    const char* p = "chenwei";
    char* res2 = (char*)Bsearch(str, len2, sizeof(str[0]), &p, cmp_string);
    if (res2 != NULL) {
        fprintf(stdout, "found it\n");
    } else {
        fprintf(stdout, "Not found\n");
    }
    return 0;
}