一、设计bubble_sort函数原型
类比qsort函数原型：
void qsort (void* base, size_t num, size_t size, int (*compar)(const void* e1,const void* e2))
所以设计bubble_sort函数原型：
void bubble_sort (void* base, size_t num, size_t size, int (*compar)(const void* e1,const void* e2))
二、冒泡排序算法
以下代码只能排序整型数组，要想排序任意类型数据还需改造
void bubble_sort(int *arr, size_t size) { for (int i = 0; i < size - 1; i++)//冒泡次数为待排序元素个数-1 { int flag = 0; for (int j = 0; j < size - 1 - i; j++)//每次比较的次数为剩余待排序元素个数-1 { if (arr[j] > arr[j + 1]) { flag = 1; int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } if (flag == 0)//提前排序完成，结束排序 { break; } } }
三、实现bubble_sort冒泡排序函数排序任意类型数据
//交换函数，一个字节一个字节地交换 void swap(char* buf1, char* buf2, size_t size)//用字符指针接收，这样解引用时就可以只取到一个字节 { for (int i = 0; i < size; i++)//每次交换1个字节的内容，一共交换的次数为待排序元素的字节大小 { char p = *buf1; *buf1 = *buf2; *buf2 = p; buf1++; buf2++; } } void bubble_sort(void* base, size_t num, size_t size, int(*compar)(const void* e1, const void* e2)) { for (int i = 0; i < num - 1; i++) { int flag = 0; for (int j = 0; j < num - 1 - i; j++) { //if (arr[j] > arr[j + 1]) //因为无法确定待排序元素的具体类型，但已知元素的字节大小，所以只能将其强制转换为char*，这样加减整数就只移动一个字节，根据元素字节大小可以找到元素起始地址 if (compar((char*)base + j * size, (char*)base + (j + 1) * size) > 0) { //交换（因为无法确定待排序元素的具体类型，所以需要一个字节一个字节地交换，已知待排序元素地字节大小） flag = 1; //int tmp = arr[j]; //arr[j] = arr[j + 1]; //arr[j + 1] = tmp; swap((char*)base + j * size, (char*)base + (j + 1) * size, size);//交换函数 } } } }
四、测试：排序整型数组，结构体数组
1.排序整型数组
int cmp_int(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int main() { int arr[10] = { 10,9,8,7,6,5,4,3,2,1 }; Print(arr, sizeof(arr) / sizeof(arr[0])); //bubble_sort(arr, sizeof(arr) / sizeof(arr[0])); bubble_sort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), cmp_int); Print(arr, sizeof(arr) / sizeof(arr[0])); return 0; }
2.排序结构体数组——按姓名首字母排序
struct stu { int age; char name[20]; }s1,s2,s3; void Print(struct stu* arr, size_t num) { for (int i = 0; i < num; i++) { printf("%s ", arr[i].name); } printf("\n"); } int cmp_struct_name(const void* e1, const void* e2) { return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name); } int main() { s1.age = 20; strcpy(s1.name, "Tom"); s2.age = 30; strcpy(s2.name, "Jerry"); s3.age = 40; strcpy(s3.name, "Allen"); /*struct stu s1 = { 20,"Tom" }; struct stu s2 = { 30,"Jerry" }; struct stu s3 = { 40,"Allen" };*/ struct stu arr[] = { s1,s2,s3 }; Print(arr, sizeof(arr) / sizeof(arr[0])); bubble_sort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), cmp_struct_name); Print(arr, sizeof(arr) / sizeof(arr[0])); return 0; }
