用冒泡排序完成库函数qsort的作用

在这里插入图片描述
Hello，今天分享的是我们用冒泡函数实现qsort，也就是快排，之前我们也讲过库函数qsort的使用方法，今天我们尝试用冒泡函数实现一下，当然我们也见过qsort，后面也会继续完善的。这几天我是破防大学生，唉！
先来看一下qsort是怎样的，我们可以登录网站cplusplus
在这里插入图片描述

通过该网站我们可以看到的是qsor的使用方法，首先我们可以看到它的返回类型是void，参数有base，num，size，还有compar我们通过英文可以看到的是base其实就是我们要排序的东西，前面用的是一个void*
的指针，void我们可以把它看成其实就是一个垃圾桶，它什么都能接收，它可以接收数组，也可以是结构体，所以这里void* 说明这个指针指向的类型可以是int 也可以是结构体也可以是double类型的，反正都可以的。

那我们先写一个冒泡函数是怎样的，相信看过我之前文章的人这个应该会了吧，手撕冒泡排序。

void bubble(int* arr, int sz)
{int i = 0;for (i = 0; i < sz - 1; i++){int j = 0;for (j = 0; i < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){int tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = arr[j];}}}
}

来看我们的冒泡程序，第一个循环决定的是我们排序的趟数，比如我们十个元素，难道我们要排序十次吗，其实九次就可以，最后一次已经有序了，那这样就不需要排序了，所以只需要九次，因为我们假设是升序，那就是前一个大于后一个的时候才要交换，所以第一趟的时候我们就可以把最大的数放到最后了，所以我们需要减去i在后面循环的时候。冒泡排序对于大家来说肯定已经很简单了。
那我们模拟实现qsort的时候用冒泡排序该怎么做呢，首先我们可以用qsort的参数

在这里插入图片描述
那我们也就可以这样写void bubble(void* base, int num, int sz, int (*cmp)(const void*, const void*))，这样之后我们需要做的其实和冒泡排序的思路是一样的，第一个循环的趟数，所以我们可以看到的是下面的代码

void bubble(void* base, int num, int sz, int (*cmp)(const void*, const void*))
{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 * sz, (char*)base + (j + 1) * sz) > 0){swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);}}}
}

我这里就全部放出来了，也比较好解释说明，首先我们比较这里是用一个函数来判断是否大于0，函数该怎么实现呢，这里穿的参数是一个特别重要的地方，为什么这么说，看到代码首先我们先要强转成char*类型，因为这样才方便我们后续的访问，我们可以先来看一下比较函数

int cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}

我们比较的是整型，所以我们要先强转成整型，然后才能开始访问解引用的操作，我们接收指针也用void类型，所以这里也有好处，就是我们可以比较任何类型的数据，比如double类型，我们需要改变的就是强转成double类型就可以，结构体也是可以进行排序的，这样是不是满足我们快排可以排很多的数据。
那我们再来完善一下swap函数，看代码发现其实我们传参数是一样的，这是为什么呢，因为我们不知道他是什么类型的数据，那这里需要我们一个一个字符，我们要知道这个类型的数据大小，所有还要传一个sz的参数，那我们来看一下交换函数的代码

void swap(char* e1, char* e2,int sz)
{int i = 0;for (i = 0; i < sz; i++){char tmp = *e1;*e1 = *e2;*e2 = tmp;e1++;e2++;}
}

这里有一个误区，我一开始也犯了，希望大家不要犯，首先我们是传指针过去，写的是char类型，接收的是char*这样的指针，然后交换的不是地址，因为指针就是地址，这个我们是知道的，所以这里我们是交换的是指针指向的字符，我们是一个一个交换的，所以外面还需要且套一个循环，这样才能全部交换，这里就是我们还要传一个参数sz的原因，下面是完整的代码

#include<stdio.h>
void print(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
int cmp(const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
void swap(char* e1, char* e2,int sz)
{int i = 0;for (i = 0; i < sz; i++){char tmp = *e1;*e1 = *e2;*e2 = tmp;e1++;e2++;}
}
void bubble(void* base, int num, int sz, int (*cmp)(const void*, const void*))
{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 * sz, (char*)base + (j + 1) * sz) > 0){swap((char*)base + j * sz, (char*)base + (j + 1) * sz, sz);}}}
}
int main()
{int arr[] = { 9,8,0,5,5,4,3,2,1 };int sz = sizeof(arr) / sizeof(arr[0]);print(arr,sz);bubble(arr, sz, sizeof(arr[0]), cmp);print(arr,sz);return 0;
}