文章目录
- 一、概述
- 二、qsort函数参数介绍
- 三、qsort实现排序
- 3.1 qsort实现整型数组排序
- 3.2 qsort实现结构体数组排序
- 四、模拟实现qsort函数
一、概述
对数组的元素进行排序
对数组中由 指向的元素进行排序,每个元素字节长,使用该函数确定顺序。
此函数使用的排序算法通过调用指定的函数来比较元素对,并将指向它们的指针作为参数。
官方解释:
声明:
void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));
qsort函数的参数
void* base
size_t num
size_t size
int( * compar )( const void * ,const void *)
二、qsort函数参数介绍
void qsort(void* base, //待排序数据的起始位置size_t num, //待排序数据的元素个数size_t size,//待排序数据的每个元素的大小int (*compar)(const void*p1, const void*p2));//函数指针 - 指针指向的函数是用来比较待排序数据中两个元素大小关系的
关于void * 的介绍:
void * 是一个无具体指向的指针类型
任何类型的指针变量都i可以存放在void中
void * 不能解引用
其中两个void*类型的参数 p1 和 p2 用来存放数组中待比较的两个元素的地址。如果compar函数的返回值小于0,会把p1指向的元素排到p2指向的元素前面;如果返回值等于0,不会改变p1和p2指向的元素位置;如果返回值大于0,会把p1指向的元素排到p2指向的元素后面。
三、qsort实现排序
3.1 qsort实现整型数组排序
# define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<stdlib.h>int comper(const void* e1, const void* e2)
{//通过强制类型转换,比较e1,e2.return *(int*)e1 - *(int*)e2;//void* 不能解引用
}int main()
{int arr[] = { 5,3,6,7,8,1,9,4,2,0 };int sz = sizeof(arr) / sizeof(arr[0]);//传入参数qsort(arr, sz, sizeof(arr[0]), comper);//打印排序后的数组int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}
3.2 qsort实现结构体数组排序
按照年龄大小的方式进行排序
# define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<stdlib.h>struct Stu
{char name[20];int age;
};int comper_by_age(const void* e1, const void* e2)
{return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age; //结构体指针不需要解引用
}int main()
{struct Stu s[] = { {"zhangsan",20},{"lisi",30},{"wangwu",25} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), comper_by_age);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}return 0;
}
运行结果:
zhangsan 20
wangwu 25
lisi 30
按照名字进行排序
# define _CRT_SECURE_NO_WARNINGS#include<stdio.h>
#include<stdlib.h>
#include<string.h>struct Stu
{char name[20];int age;
};int comper_by_name(const void* e1, const void* e2)
{return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e1)->name);//名字是字符串,通过strcmp函数来比较
}int main()
{struct Stu s[] = { {"zhangsan",20},{"lisi",30},{"wangwu",25} };int sz = sizeof(s) / sizeof(s[0]);qsort(s, sz, sizeof(s[0]), comper_by_name);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", s[i].name, s[i].age);}return 0;
}
运行结果:
lisi 30
wangwu 25
zhangsan 20
四、模拟实现qsort函数
程序员A:写一个bubble_sort()函数,可以让别人直接拿来调用
于是程序员A想要利用冒泡排序的方式,来模拟实现qsort()函数排序
qsort的底层是通过快速排序来实现的
为了能对任意数组进行排序,程序员A对冒泡排序进行了一定的更改
和qsort函数一样,bubble_sort也需要传入四个参数:
void* arr //接收首元素地址
size_t sz //接收元素个数
size_t width //接收元素宽度
int(*comper)(const void*e1,const void*e2)
于是,
void bubble_sort(void*arr,size_t sz,size_t width,int(*comper)(const void*e1,const void*e2))
现在需要完成bubble_sort内部,也就是实现排序
void bubble_sort(void* arr, size_t sz, size_t width, int(*comper)(const void* e1, const void* e2))
{size_t i = 0;//趟数for (i = 0; i < sz - 1; i++){//一趟冒泡排序的过程size_t j = 0;for (j = 0; j < sz - 1 - i; j++){/*............................ */}}
}
在冒泡排序中,运用下面代码,使得相邻两个元素进行交换:
//每一轮冒泡要进行多少次两两比较if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}
但是,这只适用于整型,不通用
那么,如何去比较呢?如何去交换两个元素呢?
for (j = 0; j < sz-1-i; j++){if (comper((char*)arr+j*width,(char*)arr+(j+1)*width)>0)//把arr强转为char*,arr就可以正常使用//char类型指针+1只会跳过一个字节//+j*width表示跳过j个元素{//交换//由于这里的数组名已经被转为char类型的指针//所以要交换数组中的元素,就只能一个字节一个字节进行交换Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width);//前两个参数是待交换元素的地址,第三个参数是元素的宽度}}
这样,就把交换条件普适化了,不只是能用在整型类型中
那么…交换呢?
根据以前的经验,我们知道使得两个元素交换,可以引入一个新的变量来暂时存一下,从而去交换,但是这有限制。
解决方案:一个字节一个字节地交换
我们将交换地函数,封装在这里面:
Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width)
对Swap函数进行加工:
void Swap(char* ele1, char* ele2,int width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *ele1;*ele1 = *ele2;*ele2 = tmp;ele1++;ele2++;}
}
这样,程序员A就将 bubble_sort()函数完成了
程序员B要想是使用该函数,直接引入 bubble_sort函数,自己写一个比较函数就可以了。