使用冒泡排序模拟实现qsort函数

1.冒泡排序

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>int main()
{int arr[] = { 0,2,5,3,4,8,9,7,6,1 };int sz = sizeof(arr) / sizeof(arr[0]);//冒泡排序一共排序 sz-1 趟for (int i = 0; i < sz - 1; ++i){//标志位，如果有序，直接退出int flag = 0;//第一趟比较sz-1次，//以后每趟比较次数-1for (int j = 0; j < sz - 1 - i; ++j){if (arr[j] > arr[j + 1]){flag = 1;int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (!flag)break;}for (int i = 0; i < sz; ++i)printf("%d ", arr[i]);return 0;
}

2.模拟实现

2.1认清障碍

qsort函数可以实现任意数据的排序

但此时的冒泡排序不行，阻碍点：

（1）

冒泡排序中 if 条件判断中的 >

注定了该算法不能实现其他数据的比较

想到：

模仿qsort函数，在冒泡排序内部

调用相关函数实现数据比较

然后根据调用函数的返回值进行后续操作

（2）

上面的交换方式也受到了限制

想到：

需要实现一个

可以实现数据交换的函数

2.2克服障碍

2.2.1依葫芦画瓢

 那就依葫芦画瓢，写下声明

void Bubble_sort(void*base,size_t num,size_t width,int(*cmp)(const void*p1,const void*p2));

此时：

从左往右，要传入的

第一个参数是 待排序数组的第一个元素的地址

 第二个参数是 元素个数

第三个参数是 每个元素的大小，单位是字节

第四个参数是 一个函数指针

Bubble_sort函数通过这个函数指针调用相关的函数

被调用的函数就是用来实现任意数据的比较方式的

被调用的函数：

返回值为int，形参为(const void*p1,const void*p2)

（1）

p1指向一个数组元素

p2指向的是p1指向的元素之后的第一个元素

(2)函数内部的要求：

（2.1）void*不能直接解引用或+-整数操作

所以需要根据需求进行相应的显式类型转换

（2.2）显示类型转换后，

当p1指向的内容大于p2时，函数返回 大于0的值

当p1指向的内容小于p2时，函数返回 大于0的值

当p1指向的内容等于p2时，函数返回 0

2.2.2逐步实现

void Bubble_sort(void*base,size_t num,size_t width,int(*cmp)(const void*p1,const void*p2))
{for (int i = 0; i < num - 1; ++i){int flag = 0;for (int j = 0; j < num - 1 - i; ++j){if(){}}if (!flag)break;}
}

冒牌排序外壳：

趟数、比较次数不用改变

2.2.2.1条件判断

if 语句中，根据函数调用返回值进行判断

假设，当当p1指向的内容大于p2时，才进行数据的交换

那么，代码如下：

void Bubble_sort(void*base,size_t num,size_t width,int(*cmp)(const void*p1,const void*p2))
{for (int i = 0; i < num - 1; ++i){int flag = 0;for (int j = 0; j < num - 1 - i; ++j){if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0){flag = 1;..}}if (!flag)break;}
}

详细解释：

（1）绿色方框框起来的意思是

（1.1）这是两个实参

（1.2）指针指向一种数据时，

总是指向该数据所占空间地址最小的那个字节

（1.3）base接收了数组首元素的地址，但是

我并不知道这是整型、浮点型、字符型的数组

所以我将它强制转换为(char*)类型的指针

这样，无论如何

(char*)base 都指向了数组首元素的第一个字节

（1.4）函数传参传进了width，

注意到：

如果是一个int型的数组

(char*)base 指向了数组首元素的第一个字节

(char*)base+width指向了数组第二个元素的第一个字节

(char*)base+2*width指向了数组第三个元素的第一个字节

如果是一个char型的数组

(char*)base 指向了数组首元素

(char*)base+width指向了数组第二个元素

(char*)base+2*width指向了数组第三个元素

所以：

实参就是

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

（2）橙色方框框起来的意思是

调用cmp函数

（3）红色方框框起来的意思是

当cmp函数返回值>0时，才进行后续的操作

2.2.2.2交换方式

避免代码冗余，创建一个Swap函数进行数据的交换

void Bubble_sort(void*base,size_t num,size_t width,int(*cmp)(const void*p1,const void*p2))
{for (int i = 0; i < num - 1; ++i){int flag = 0;for (int j = 0; j < num - 1 - i; ++j){if(cmp((char*)base+j*width,(char*)base+(j+1)*width)>0){flag = 1；Swap((char*)base+j*width,(char*)base+(j+1)*width, width);}}if (!flag)break;}
}

（1）我们并不知道元素的类型

但是因为我们知道元素的大小

所以我们可以逐字节地交换两个元素

（2）此时，传入的参数应该是

两个元素的第一个字节、元素的大小

 Swap((char*)base+j*width,(char*)base+(j+1)*width, width);

内部实现：

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

（1）width有多大，就交换几次

每次交换后，指针偏移

2.3测试

使用Bubble_sort函数与使用qsort函数一样

需要自己编写一个实现数据比较地函数

这是整型数据的比较

这是字符间的排序 :

注意，元素个数用strlen求！

这是字符串间的排序：