C语言学习系列--＞【关于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函数，自己写一个比较函数就可以了。