四、利用冒泡排序模拟实现qsort函数
4.1：冒泡排序
关于冒泡排序的详细讲解可以参考我的这篇文章：初级C语言之【数组】里面详细介绍了冒泡排序
//冒泡排序函数 void bulle_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[10] = { 9,8,7,6,5,4,3,2,1,0 }; int sz = sizeof(arr) / sizeof(arr[0]); bulle_sort(arr,sz); int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } return 0; } //结果： 0 1 2 3 4 5 6 7 8 9
缺陷1：
用来接收待排序数组首元素地址的指针arr已经被写死了，是int*型，说明只能对整型数组进行排序
缺陷2：
缺陷2如上图所示，红色方框框起来的部分只适用于对整数之间的大小关系进行比较，然后交换
4.2：模拟实现qsort函数
//利用冒泡排序模拟实现qsort 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++; } } void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2)) //第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收 //第二个参数 - 用来接收数组元素个数 //第三个参数 - 用来接收数组元素的宽度 { size_t i = 0; //趟数 for (i = 0; i < sz - 1; i++) { //一趟冒泡的过程 size_t j = 0; 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); //前两个参数是待交换元素的地址，第三个参数是元素的宽度 } } } }
这里说的利用冒泡排序来实现qsort函数，仅仅是实现了qsort函数可以对任意类型的数组进行排序这一特点，并不是说实现qsort函数的底层原理，qsort的底层是通过快速排序来实现的。
因此，为了使改变之后的冒泡函数能够对任意类型的数组进行排序，原本冒泡排序函数的参数就要发生改变，和qsort函数一样，新的冒泡排序函数也要有以下4个参数：
void* arr
size_t sz
size_t width
int(*comper)(const void*e1,const void*e2)
arr用来接收待排序数组首元素的地址，sz用来接收待排序数组的元素个数，width用来接收数组中每个元素的大小（单位是字节），comper用来接收比较函数的地址。参数的改变解决了原冒泡排序函数的缺陷1。
接下来要解决原冒泡排序函数的缺陷2，缺陷2的主要问题在于它的普适性不够强，首先要对交换的判断条件，即if后面的判断语句做出改变，让他能够比较任意两个类型的数据，这时，比较函数就发挥作用了，我们只需要把待比较的两个元素地址传给比较函数，由比较函数来判断它们之间的关系
新的问题又出现了，comper函数的形参需要接收两个待比较元素的地址，这里的待比较元素一定是当前待排序数组里面的元素，但是待排序数组的首元素地址是用空指针（void*）来接收的，无法直接使用，这意味着现在无法通过数组首元素的地址，顺藤摸瓜去访问数组中的元素。这里问题的关键就是空指针无法使用，那我们就想到把空指针进行强制类型转化，把空指针变成有具体指向的指针不就可以正常使用了，问题又出现了，有那么多的指针类型，到底把空指针强转成什么类型的指针呢？？？答案是：把空指针强转成字符指针（char*）。这里是因为，字符指针+1仅跳过一个字节，我们可以通过改变加数的数值，使指针指向任意内存空间，这也就意味着强转后的arr指针可以存放任意内存单元的地址，并且可通过地址去访问内存中的数据。
(char*)arr+j*width
这里先把arr指强制类型转化成char*类型，这里的加数是：j*width。其中width表示当前数组中每个元素的大小（单位是字节），这里的+j*width就是跳过j*width个字节，由于width是一个元素的字节，所以+j*width也就意味着跳过了j个元素，此时 (char*)arr+j*width就表示下标为j的元素的地址。
(char*)arr+(j+1)*width
同理(char*)arr+(j+1)*width就表示下标为j+1的元素的地址。
此时就可以把待比较的两个元素的地址传给用户自己写的comper函数了，通过comper函数的返回值来判断这两个元素是否要交换。
到这里缺陷2中的问题只解决了一半，即：只把交换的判断条件做了修改，增强了交换判断条件的普适性，使其可以对任意类型的数组中的元素进行比较。具体的交换步骤还没有修改，当前的交换步骤仅仅适用于整型数据。根据经验，对两个变量进行交换，需要创建一个中间变量，比如：交换两个整型变量，需要创建一个整形的中间变量；交换两个字符型变量，需要创建一个字符型的中间变量……可见，对于不同类型的数据元素，在交换时创建的中间变量的类型也是不同的，由于无法预知要交换数据的类型，所以也无法提前确定中间变量的类型。这里的解决方案是：一个字节一个字节的交换，这样中间变量的类型就能确定下来了，即为char型。不同的数据类型对应着不同的字节数，但是它们都是由字节组成，我们有了数组中每个元素的字节大小时，就可以写一个循环，从元素的首个字节开始，一个字节一个字节的交换，直到最后一个字节。这里我们写了一个交换函数Swap
void Swap(char* ele1, char* ele2,int width)
Swap函数有三个参数，ele1和ele2分别用来接收待交换的两个元素的地址，width用来接收数组中每个元素的大小（单位是字节）。
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++; } }
到此，原来冒泡排序中的两个缺陷已经被成功地解决，经过改造后的冒泡函数bulle_sort就可以对任意类型数组进行排序。
4.3：实际应用
4.3.1：利用bulle_sort函数对整型数组排序：
//利用冒泡排序模拟实现qsort //交换函数 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++; } } //改造后的冒泡排序函数 void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2)) //第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收 //第二个参数 - 用来接收数组元素个数 //第三个参数 - 用来接收数组元素的宽度 { size_t i = 0; //趟数 for (i = 0; i < sz - 1; i++) { //一趟冒泡的过程 size_t j = 0; 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个元素 { //交换 Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width); //前两个参数是待交换元素的地址，第三个参数是元素的宽度 } } } } //比较函数 int comper_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } //主函数 int main() { int arr[10] = { 9,8,7,6,5,4,3,2,1,0 }; int sz = sizeof(arr) / sizeof(arr[0]); bulle_sort(arr, sz, sizeof(arr[0]), comper_int);//调用bulle_sort来排序 int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; } //结果： 0 1 2 3 4 5 6 7 8 9
4.3.2：利用bulle_sort函数对结构体数组排序：
按照年龄排序：
//利用冒泡排序模拟实现qsort //交换函数 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++; } } //改造后的冒泡排序函数 void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2)) //第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收 //第二个参数 - 用来接收数组元素个数 //第三个参数 - 用来接收数组元素的宽度 { size_t i = 0; //趟数 for (i = 0; i < sz - 1; i++) { //一趟冒泡的过程 size_t j = 0; 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个元素 { //交换 Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width); //前两个参数是待交换元素的地址，第三个参数是元素的宽度 } } } } //声明一个结构体 struct Stu { char name[20]; int age; }; //按照年龄进行比较 int comper_age(const void* e1, const void* e2) { return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age; } //主函数 int main() { struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} }; int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; //排序前打印 for (i = 0; i < sz; i++) { printf("%s %d ", arr[i].name, arr[i].age); } printf("\n"); //按照年龄进行排序 bulle_sort(arr, sz, sizeof(arr[0]), comper_age); //排序后打印 for (i = 0; i < sz; i++) { printf("%s %d ", arr[i].name, arr[i].age); } printf("\n"); return 0; } //结果： zhangsan 100 lisi 20 wangwu 3 wangwu 3 lisi 20 zhangsan 100
按照名字排序：
//利用冒泡排序模拟实现qsort //交换函数 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++; } } //改造后的冒泡排序函数 void bulle_sort(void* arr , size_t sz,size_t width,int(*comper)(const void*e1,const void*e2)) //第一个参数 - 用来接收待排序数组的首元素地址，可能会排序各种数组，所以形参数组用void*来接收 //第二个参数 - 用来接收数组元素个数 //第三个参数 - 用来接收数组元素的宽度 { size_t i = 0; //趟数 for (i = 0; i < sz - 1; i++) { //一趟冒泡的过程 size_t j = 0; 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个元素 { //交换 Swap((char*)arr + j * width, (char*)arr + (j + 1) * width,width); //前两个参数是待交换元素的地址，第三个参数是元素的宽度 } } } } //声明一个结构体 struct Stu { char name[20]; int age; }; //按照名字比较 int comper_name(const void* e1, const void* e2) { return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);//名字是字符串，所以名字的比较要用到字符串比较 函数strcmp } //主函数 int main() { struct Stu arr[3] = { {"zhangsan",100},{"lisi",20},{"wangwu",3} }; int sz = sizeof(arr) / sizeof(arr[0]); int i = 0; //排序前打印 for (i = 0; i < sz; i++) { printf("%s %d ", arr[i].name, arr[i].age); } printf("\n"); //按照名字进行排序 bulle_sort(arr, sz, sizeof(arr[0]), comper_name); //排序后打印 for (i = 0; i < sz; i++) { printf("%s %d ", arr[i].name, arr[i].age); } printf("\n"); return 0; } //结果： zhangsan 100 lisi 20 wangwu 3 lisi 20 wangwu 3 zhangsan 100
