1.前言
上文我们讲述了c语言中qsort的简洁和使用,今天我们从qsort的代码编写出发,重新打造一个属于自己的qsort,希望能对大家的学习有所帮助,
2.思路引导
我们知道qsort是一个库函数,底层实现使用了快排的算法,这里我们为了简化就使用冒泡排序来代替,本文注重思路引导.
2.1 函数实现
首先我们需要思考代码的参数,我们需要将一组数据进行排序,但是不知道具体传入何种数据,这里我们就只能使用 void* 类型的指针来接收 ,然后我们需要知道待排序的一组数据一共有多少个元素,每个元素所占空间大小的是怎样的,最后是一个函数指针,我们需要通过这个函数来将数据排成想要的顺序,这样我们就得到了函数的外形,返回值是void.
my_qsort(void* base,size_t num,size_t size,int(*cmp)(const void* e1,const void* e2)) { }
这里我们是在冒泡排序上用来改进,我们不妨借此回顾一下冒泡排序.
2.2 冒泡排序
bubble_sort(int arr[],size_t num) { int i = 0; for (i = 0; i < num - 1; i++) { //一趟冒泡排序 int j = 0; for (j = 0; j < num - 1 - i; j++) { //要求升序排列 if(arr[j] > arr[j+1]) { int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } }
我们在此阶段上进行改进,我们发现冒泡排序在这种情况下只能排序整形的数据,这并不满足我们的需求,我们想要排序结构体的数据,我们甚至想要排序其他各种不同的数据,就像qsort一样能力强大,于是我们继续进行改造.
2.3 主函数的实现
void my_qsort(void* base, size_t num,size_t size, 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 * size,(char*)base + (j+1) * size)>0) /*if (arr[j] > arr[j + 1])*/ { //交换 swap((char*)base + j * size, (char*)base + (j + 1) * size,size); //一个字节一个字节交换 } } } }
这里我们不改变冒泡排序的核心,我们将它判断两个数据大小的if语句换成了一个比较函数,而比较的方式或者是依据则由用户自定义,这样也解决了冒泡排序只能排序整形数据的痛点.除此之外,我们又遇到了新的问题,我们我们如何将数据进行交换呢,于是我们想到了,将原有数据地址转换成char*类型的数据,再将数据进行逐字节的交换,根据参数提供的每个数据的大小,我们也能轻松的将这一问题解决.
2.4 交换函数
void swap(char* buf1, char* buf2, size_t size) { int i = 0; for (i = 0; i < size; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } }
3.函数测试
3.1 对整形测试
至此,一个简单的my_qsort就实现了,下面我们进行测试,首先排序一下整形数据,看看改动后是否能完成之前的功能.
int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } void test1() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; //排序成升序 int sz = sizeof(arr) / sizeof(arr[0]); print_arr(arr,sz); my_qsort(arr, sz, sizeof(arr[0]), cmp_int); print_arr(arr,sz); }
运行结果如下
3.2 对结构体测试
typedef struct Stu { char name[20]; int age; }ST; int cmp_ST_by_age(const void* e1, const void* e2) { return ((ST*)e1)->age - ((ST*)e2)->age; } int cmp_ST_by_name(const void* e1, const void* e2) { return strcmp(((ST*)e1)->name, ((ST*)e2)->name); } void test2() { ST arr[] = { {"张三",20},{"李四",30},{"王五",15} }; int sz = sizeof(arr) / sizeof(arr[0]); my_qsort(arr, sz, sizeof(arr[0]), cmp_ST_by_age); }
