C语言之qsort()函数的模拟实现

C语言之qsort()函数的模拟实现

1. 简介

qsort()函数全称为Quicksort，因为底层使用的是快速排序，对初学者来说只学过冒泡排序，使用我们使用冒泡排序来实现下qsort()函数，qsort()函数（冒泡排序版）

不知道qsort函数怎么使用的可以看看这篇qsort函数

2. 冒泡排序

既然要使用冒泡排序改模拟实现qsort，那得知道什么是冒泡排序
代码如下：

#include <stdio.h>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 tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;}}}
}int main()
{int arr[] = { 1,4,7,2,5,8,3,10,6,9 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);return 0;
}

3. 对冒泡排序进行改造

void bubble_sort(int arr[], int sz);
void qsort (void* base, size_t num, size_t size,            int (*compar)(const void*,const void*));

先来看看冒泡排序和qsort函数的函数声明
要想用冒泡排序模拟实现qsort函数，首先函数的形参要一致

void bubble_sort2(void* base,size_t sz,size_t width,  int (*cmp)(const void* p1,const void* p2));

仿照着qsort的形参来写

1. void*：由于我们不知道要排序什么数组，所以我们使用void*来接收
2. sz：为数组中元素的个数
3. width：为数组中一个元素的大小（单位为字节）
4. int (cmp)(const void p1,const void* p2)：是函数指针
   这个函数指针指向的函数是用来比较两个元素的大小
   p1指向一个元素，p2也指向一个元素

函数的声明部分写好了，就得改造函数内部了
先来看看冒泡排序中的代码

1. 首先函数的形参得更改吧 改为上边的函数声明
2. 趟数取决于数组中元素个数使用不需要修改
3. 冒泡排序只能排序整型，所以一趟冒泡排序中的比较部分需要修改
4. 交换两个元素的位置也需要修改

4. 改造部分

4.1 保留部分的冒泡排序

先将冒泡排序还能使用的部分保留下来

void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;//趟数for (i = 0; i < sz - 1; i++){int j = 0;//一趟冒泡排序for (j = 0; j < sz - 1 - i; j++){//比较两个元素的大小if (){//Swap用于交换两个元素的位置Swap();}}}
}int main()
{int arr[] = { 1,4,7,2,5,8,3,10,6,9 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

其中的比较部分和交换部分需要我们自己来实现

4.2 比较部分

cmp((char*)base + j * width, (char*)base + (j + 1) * width)

1. 由于我们得到的数组名，也就是首元素的地址，不知道第二个元素的地址
   我们可以通过指针偏移来找到第二个元素

2. 我们得到的是void类型的数据，我们需要将其强制转换成char类型的数据，以便于我们进行指针偏移

3. 不知道数组的类型，我们只知道一个元素的大小，我们可以通过(char*)base + j + width的方式来找到一个元素的地址，(char*)base + (j+1) + width的方式来找到后一个元素的地址
   用来模拟arr[j] 和 arr[j+1]
   

4. 为什么其他类型的指针不行呢，我来举个例子：

假设用来排序double类型的数据，也就是每个元素是8字节 width = 8
(char*)base + j * width 和 (char*)base + (j+1) * width
当j等于0时，char类型的指针会偏移8个字节，找到第二个元素
如果换成其他类型的指针 int* 在这个情况下就不能使用了，只有char*类型的指针偏移是1个字节，适用于任意类型的排序

4.3 交换部分

void Swap(char* p1, char* p2,size_t width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *p1;*p1 = *p2;*p2 = tmp;p1++;p2++;}
}

1. 由于在比较部分已经将数据强制转换成char类型，所以Swap函数的形参就可以使用char来接收
2. 由于不知道接收的是什么类型的数据，但是我们知道每个元素的大小，我们可以通过一个字节一个字节进行交换，和冒泡排序一样定义一个临时变量来交换两个元素，交换完一个字节的内容之后，p1++ p2++来找到第二个字节的内容，直到交换完成

5. bubble_sort2完整代码

void Swap(char* p1, char* p2,size_t width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *p1;*p1 = *p2;*p2 = tmp;p1++;p2++;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;//趟数for (i = 0; i < sz - 1; i++){int j = 0;//一趟冒泡排序for (j = 0; j < sz - 1 - i; j++){//比较两个元素的大小if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//Swap用于交换两个元素的位置Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);}}}
}

6. 使用bubble_sort2来排序整型数组

和使用qsort函数一样，第四个形象需要根据需要排序的数据类型来编写函数，然后将其传给qsort函数，整型数据的比较只需要两个元素作差就好了
代码如下：

int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}

排序整型数组的完整代码：

#include <stdio.h>void Swap(char* p1, char* p2,size_t width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *p1;*p1 = *p2;*p2 = tmp;p1++;p2++;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;//趟数for (i = 0; i < sz - 1; i++){int j = 0;//一趟冒泡排序for (j = 0; j < sz - 1 - i; j++){//比较两个元素的大小if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//Swap用于交换两个元素的位置Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);}}}
}int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}int main()
{int arr[] = { 1,4,7,2,5,8,3,10,6,9 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

代码运行结果如下：

7. 使用bubble_sort2来排序结构体数组

由于结构体中的数据类型较多，可以选择一种来排序，然后根据不同的数据类型来排序
按以下两种数据来举例子

struct Stu 
{char name[20];int age;
};```c
int main()
{struct Stu arr[] = { {"zhangsan",25},{"lisi",18} ,{"wangwu",30} };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_name);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", arr[i].name, arr[i].age);}return 0;
}

7.1 按名字来排序结构体数组

字符串的比较是比较ASCII，不是比较字符串的长度

int cmp_struct_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);//return strcmp((*(struct Stu*)p1).name, (*(struct Stu*)p2).name);//两段代码等价
}

完整代码如下：

#include <stdio.h>
#include <string.h>void Swap(char* p1, char* p2,size_t width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *p1;*p1 = *p2;*p2 = tmp;p1++;p2++;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;//趟数for (i = 0; i < sz - 1; i++){int j = 0;//一趟冒泡排序for (j = 0; j < sz - 1 - i; j++){//比较两个元素的大小if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//Swap用于交换两个元素的位置Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);}}}
}struct Stu 
{char name[20];int age;
};int cmp_struct_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);//return strcmp((*(struct Stu*)p1).name, (*(struct Stu*)p2).name);//两段代码等价
}int main()
{struct Stu arr[] = { {"zhangsan",25},{"lisi",18} ,{"wangwu",30} };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_name);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", arr[i].name, arr[i].age);}return 0;
}

代码运行结果如下：

7.2 按年龄来排序结构体数组

int cmp_struct_by_age(const void* p1, const void* p2)
{return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;//return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;//两段代码等价
}

完整代码如下：

#include <stdio.h>
void Swap(char* p1, char* p2,size_t width)
{int i = 0;for (i = 0; i < width; i++){char tmp = *p1;*p1 = *p2;*p2 = tmp;p1++;p2++;}
}
void bubble_sort2(void* base, size_t sz, size_t width, int (*cmp)(const void* p1, const void* p2))
{int i = 0;//趟数for (i = 0; i < sz - 1; i++){int j = 0;//一趟冒泡排序for (j = 0; j < sz - 1 - i; j++){//比较两个元素的大小if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//Swap用于交换两个元素的位置Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);}}}
}struct Stu 
{char name[20];int age;
};int cmp_struct_by_age(const void* p1, const void* p2)
{return ((struct Stu*)p1)->age - ((struct Stu*)p2)->age;//return (*(struct Stu*)p1).age - (*(struct Stu*)p2).age;//两段代码等价
}
int main()
{struct Stu arr[] = { {"zhangsan",25},{"lisi",18} ,{"wangwu",30} };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort2(arr, sz, sizeof(arr[0]), cmp_struct_by_age);int i = 0;for (i = 0; i < sz; i++){printf("%s %d\n", arr[i].name, arr[i].age);}return 0;
}

代码运行结果如下：