C语⾔标准库qsortbsearch源码实现
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) {
return0;
} else {
return1;
}
}
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. 数据的字节序列可能是有内存对齐的，主要是在结构体之中。所以我的这个实现受机器内存对齐规则的影响，但是排序发⽣在同⼀机器中的话，这个是不会影响正确性的。
总⽽⾔之，代码实现受机器底层数据⼤⼩端表⽰和内存对齐策略的影响。但是实际上⼀个排序过程是不可能⼀部分进⾏在这台机，另⼀部分在另外⼀台机器上进⾏的(仅考虑单机)，所以我的这个实现是可以很好⼯作的。
sizeof结构体大小
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) {
return0;
} else {
return1;
}
}
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");
}
return0;
}
欢迎⼤家批评指正，共同学习。转载请注明出处，谢谢。