什么是冒泡排序
在qsort函数 - (Quick Sort)【快速排序的使用方法】中提到了一种排序方法为快速排序，快速排序是c语言中的一种
冒泡排序是一种简单的算法，是用来排列一组数据的简单算法。
冒泡排序的使用
存在一组无序数组
arr[] = {9,3,1,5,4,6,2,7,8,0};
要将该数排列为升序，冒泡排序的中心想法即为两两相比较，排成升序时，若是前面的数比后面的数大则进行交换，降序则相反。
void bubble_sort(int arr[], int sz) { int i = 0; int j = 0; for (i = 0; i < sz - 1; i++) {//冒泡排序的趟数 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; } } } } void print(int arr[], int sz) {//打印函数 for (int i = 0; i < sz ; i++) { printf("%d ", arr[i]); } } void test1() { int arr[] = { 9,3,1,5,4,6,2,7,8,0 };//待排列的数据 int sz = sizeof(arr) / sizeof(arr[0]);//数组内元素个数 bubble_sort(arr, sz);//传入数组首元素地址，与数组内元素个数 print(arr, sz); } int main() { test1(); return 0; }
但是冒泡排序在排序中有一定的限制 - 对于排列数据的种类有了限制，所以在进行数据排序的时候大多会使用qsort函数 - 快速排序；但是能否将冒泡排序优化成像是快速排序没有类型限制的排序呢？
冒泡排序模拟实现快速排序
根据cplusplus给出的功能及参数可知，使用qsort函数时需要的参数为：
数组首元素地址
数组元素个数
数组单个元素大小
指向一个能接收两个元素数据并返回一定值的函数的函数指针
假设存在同样的整形数组，并将其排序：
arr[] = {9,3,1,5,4,6,2,7,8,0};
冒泡排序的参数想法与qsort函数的想法类似；
void bubble_sort(void*base,size_t num,size_t width,int (*compar)(void*p1,void*p2));
void* base - 传递首元素地址(不知使用者需要排序什么类型的数据所以转为void* )
size_t num - 传递需要排列数组的元素个数
size_t width - 传递单个元素的大小
int (* compar)(void *p1,void *p2) - 传递一个函数指针，指针指向的函数可以用来接收两个待排序数组内的元素，同时在设置时不知使用者应排列什么数据所以使用void型指针进行接收。
void bubble_sort_plus(void* base, size_t num, size_t width, int(*compar)(void* p1, void* p2)) { for (int i = 0; i < num - 1; i++) { for (int j = 0; j < num - 1 - i; j++) { if (compar((char*)base+j*width, (char*)base + (j+1) * width)>0) { Swap((char*)base + j * width, (char*)base + (j + 1) * width,width); } } } }
和冒泡排序的方式类似，循环次数为冒泡排序的趟数，每趟利用compar函数的返回值进行判断，但是在判断的过程中应该如何进行传参？
已知设定的参数为void*，而该类指针无法直接解引用，故先将该指针转换为字符类型指针，每次越过的空间即为width。
if (compar((char*)base+j*width, (char*)base + (j+1) * width)>0);
若是条件成立则进行交换：
void Swap(char*buf1,char*buf2,size_t width) { for (size_t i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } }
同时为了避免大部分数据都为需要排列的顺序而重复进行判断，可以在循环中加入开关 - flag。
void bubble_sort_plus(void* base, size_t num, size_t width, int(*compar)(void* p1, void* p2)) { for (int i = 0; i < num - 1; i++) { int flag = 1; for (int j = 0; j < num - 1 - i; j++) { if (compar((char*)base+j*width, (char*)base + (j+1) * width)>0) { Swap((char*)base + j * width, (char*)base + (j + 1) * width,width); flag = 0; } } if (flag) { break; } } }
完整代码
void print(int arr[], int sz) {//打印函数 for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } } int compar(void* p1, void* p2) { return *(int*)p1 - *(int*)p2; } void Swap(char*buf1,char*buf2,size_t width) { for (size_t i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } } void bubble_sort_plus(void* base, size_t num, size_t width, int(*compar)(void* p1, void* p2)) { for (int i = 0; i < num - 1; i++) { int flag = 1; for (int j = 0; j < num - 1 - i; j++) { if (compar((char*)base+j*width, (char*)base + (j+1) * width)>0) { Swap((char*)base + j * width, (char*)base + (j + 1) * width,width); flag = 0; } } if (flag) { break; } } } void test1() { int arr[] = { 9,3,1,5,4,6,2,7,8,0 }; int sz = sizeof(arr) / sizeof(arr[0]); bubble_sort_plus(arr,sz,sizeof(arr[0]),compar); print(arr, sz); } int main() { test1(); return 0; }
