C语言--模拟实现库函数qsort

什么是qsort

qsort是一个库函数，是用来排序的库函数，使用的是快速排序的方法(quicksort)。
qsort的好处在于：
1，现成的
2，可以排序任意类型的数据。

在之前我们已经学过一种排序方法：冒泡排序。排序的原理是两两相邻的元素进行比较。但是冒泡排序的缺陷就在于只能两两整型进行比较，可现实生活中很多东西的比较并不只是仅仅局限于数字的比较，比如名字的排序等等。
但是qsort就可以排序任意类型的数据
1，比较两个整数的大小(< > =)
2，比较两个字符串(strcmp)
3，比较两个结构体数据(学生：张三，李四，王五)

qsort的声明与参数

我们先来看C标准库里对qsort函数的描述

头文件

qsort需引用的头文件为 <stdlib.h>

#include <stdio.h>

声明

qsort函数的声明如下

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
{
}

参数

qsort函数的参数如下

base -- 指向了待排序数组的第一个元素
num -- 待排序的元素个数
size -- 每个元素的大小，单位是字节
cmp -- 指向一个函数，这个函数可以比较两个元素的大小

书写格式

我们以给一个数组按升序排序为例，看下面这段代码：

#include <stdio.h>
#include <stdlib.h>int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void print(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d", arr[i]);}}
void test1()
{int arr[] = { 9,8,6,7,5,4,2,3,1 };int sz = sizeof(arr) / sizeof(arr[0]);qsort(arr, sz, sizeof(arr[0]), cmp_int);print(arr, sz);
}
int main()
{test1();return 0;
}

值得注意的是，其中的cmp_int函数是系统已经封装好了的一个函数，但是因为编译者在编译这个函数的时候，并不知道后来的人们使用这个qsort去排序什么类型的元素，所以用了void* 这样一个通用类型的指针。
这就意味着void*这个指针可以存放任意数据类型的指针。

int main()
{int a = 0;int* p = &a;//通常写法char* p = &a;//编译器会报错，char*类型与a类型不匹配void* p = &a;//通用指针*p;//报错*(int*)p;//正确return 0;
}

为什么用void*指针来存放地址直接解引用会报错呢？这是因为系统在解引用操作时并不知道要访问几个字节，必须要强制类型转换才能正常解引用。

测试qsort排序结构体

学习完了qsort函数的基本格式，我们现在来尝试运用一下它，以实现对结构体的排序为例：

以年龄升序排序

struct Stu
{char name[20];int age;
};
int cmp_stu_by_age(const void* p1, const void* p2)
{return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;
}
void test2()
{struct Stu s[] = { {"zhangsan",20},{"lisi",25},{"wangwu",15} };int sz = sizeof(s) / sizeof(s[0]);//按年龄来比较qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
}
int main()
{test2();return 0;
}

我们用监视的方法来看一下排序的结果

以姓名升序排序

如果我们要以姓名排序，要注意的是，姓名是一个字符串，而字符串是不能直接相减的，所以我们要使用另一个库函数—strcmp来进行比较，但是返回值类型仍然为整型，因为strcmp这个库函数的返回值类型就是整型，代码书写如下

struct Stu
{char name[20];int age;
};
int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name,((struct Stu*)p2)->name);
}
void test2()
{struct Stu s[] = { {"zhangsan",20},{"lisi",25},{"wangwu",15} };int sz = sizeof(s) / sizeof(s[0]);//按姓氏来比较qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
}
int main()
{//test1();test2();return 0;
}

我们同样用监视的方法来看一下结果

结果也是成功以姓名升序排列。

用冒泡排序来模拟实现

因为我们还没有学习快速排序的底层逻辑，所以本章我们先用冒泡排序的思想来实现一个类似于qsort这个函数功能的冒泡排序函数bubble_sort，效果是一样的。
在之前的文章里有专门的对于冒泡排序实现过程的讲解，这里不再过多赘述，直接上代码

void bubble_sort(int arr[], int sz)
{int i = 0;//冒泡排序的趟数for (i = 0; i < sz - 1; i++){//一趟冒泡排序的过程int j = 0;for (j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
int main()
{int arr[] = { 3,1,5,9,2,4,7,6,8,0 };//排序 - 升序//冒泡排序int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr,sz);//arr是数组首元素的地址int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

我们先来看以冒泡排序为原理实现的快排源码再逐一分析：

int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}void Swap(char* buf1, char* buf2,int width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *buf1;*buf1 = *buf2;*buf2 = tmp;buf1++;buf2++;}
}
void bubble_sort(void* base, size_t num,size_t width, int(*cmp)(const void* p1, const void* p2))
{int i = 0;for (i = 0; i < num - 1; i++){int j = 0;for (j = 0; j < num - 1 - i; j++){//俩相邻元素比较//假设以升序排列if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}}
}
void test3()
{int arr[] = { 3,2,1,4,5,7,8,9,6 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print(arr, sz);
}
int main()
{test3();return 0;
}

图解

我们来通过图文结合·进一步了解各部分的作用：

通过图解应该能对该算法有更深一步的理解。

以上就是关于模拟实现库函数qsort(快排)的全部内容了，如有出入，欢迎指正。