如何开展网站建设,创建网站有什么用,网站中微信公众号链接怎么做,官网建站系统什么是qsort
qsort是一个库函数#xff0c;是用来排序的库函数#xff0c;使用的是快速排序的方法(quicksort)。 qsort的好处在于#xff1a; 1#xff0c;现成的 2#xff0c;可以排序任意类型的数据。
在之前我们已经学过一种排序方法#xff1a;冒泡排序。排序的原理…什么是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.hint 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(快排)的全部内容了如有出入欢迎指正。
