这是一篇介绍qsort函数模拟实现的博客,包含每一步实现的思路，对MSDN中qsort的使用进行了详细介绍。在实现的过程中，也对涉及到的知识点进行了一些简单介绍。希望可以给同为计算机小白的伙伴们一些帮助，若有错误，还望大佬们不吝赐教。
一、MSDN中对qsort的注解
1、 功能
执行快速排序； 运用自定义的比较函数，qsort可以对任何类型的数据进行排序；
2、参数
- void* base
目标数组的起点，此参数说明排序从哪开始；
- size_t num
数组中元素的个数；
- size_t width
数组中元素所占字节的大小；
- int (__cdecl *compare )(const void *elem1, const void *elem2 )
compare是一个函数指针，指向一个自定义的比较函数，返回值为int，e1，e2分别为所比较位置的起始位置；
3、标注
qsort是对一个数组执行快速排序的算法，这个数组包含num个元素，每个元素所占字节width个；参数base是指向所需排序数组起点的指针；qsort会将数组中的元素进行排序后覆写；参数compare是用户自定义的函数，通过返回值确定两个元素的大小；qsort会在排序中调用1次或多次此函数，每次调用对两个元素进行排序；
默认排序为升序，此时，自定义函数的返回值须满足：e1 < e2，返回值 < 0； e1 = e2，返回值 = 0；e1 > e2，返回值 > 0。若要降序，只需要交换自定义函数中e1，e2的位置即可。
二、基本功能的实现
1、自定义排序功能
不同于qsort采用快速排序，我们采用冒泡排序作为核心实现排序；
//自定义qsort函数
my_qsort(void* base, int num, int width, int (*cmp)(const void* e1, const void* e2))
{
//n - 1趟比较
for (int i = 0; i < num - 1; i++)
{
//比较
for (int j = 1; j < num; j++)
{
//交换，cmp返回值大于0则交换位置
if (cmp(((char*)base + (j - 1) * width), ((char*)base + j * width)) > 0)
{
swap(((char*)base + (j - 1) * width), ((char*)base + j * width), width);
}
}
}
}
2、交换元素数据
在自定义函数中，将指针强制类型转换为char*，以交换每一个字节的方式，达到两个字节交换的目的；
//交换
void swap(char* a, char* b, int w)
{
char tmp = 0;
for (int i = 0; i < w; i++)
{
tmp = *a;
*a = *b;
*b = tmp;
a++;
b++;
}
}
3、自定义比较函数
此处我们以整型举例:
- e1，e2为void*的指针，也就是说从此处访问并不清楚往后访问多少个字节，指针的步长并不确定，我们需要确定步长，也就是说，需要对e1，e2进行强制类型转换；
- 返回值为int，e1、e2强制类型转换后相减即可得，故代码得以简化；
//整型比较函数
int cmp_int(const void* e1, const void* e2)
{
return *((int*)e1) - *((int*)e2);
}
以上，对qsort函数的基本功能得以完全实现。
三、优化及收获
1、排序算法
函数的核心算法，可由冒泡排序改为快速排序，从而降低时间复杂度，从冒泡的O($n^2$)变为快排的O(nlogn)。
2、自定义的打印算法
通过qsort的模拟实现，我们发现： 在函数中，采用void*的指针，通过添加元素个数和元素宽度，一个函数的逻辑可以实现任意类型数据的访问，大大简化代码。
void print(void* a, int sz, int width)
{
for (int i = 0; i < sz; i++)
{
switch (width)
{
case 1:
printf("%c ", *((char*)a + i));
break;
case 4:
printf("%d ", *((int*)a + i));
break;
case 8:
printf("%f ", *((float*)a + i));
break;
default:
break;
}
}