冒泡排序与其C语言通用连续类型排序代码
冒泡排序
冒泡排序为交换排序的一种：
- 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。
- 交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
而冒泡排序升序时每遍历一次会将未排好的集合中大的值移动到后面（或小的移到前面），直到排好序。
动图展示：
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N ^ 2)
- 空间复杂度：O(1)
- 稳定性：稳定
冒泡排序排整型数据参考代码（VS2022C语言环境）：
#include <stdio.h>
#include <stdbool.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// 要排序的数组 数组大小
int bubbleSort(int* arr, int sz)
{
// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
for (int i = 0; i < sz - 1; ++i)
{
bool flag = true; // 3.检查是否有序
// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
for (int j = 0; j < sz - 1 - i; ++j)
{
if (arr[j] > arr[j + 1])
{
flag = false; // 3.表示无序
swap(&arr[j], &arr[j + 1]);
}
}
if (flag == true) // 3.有序直接退出循环
{
break;
}
}
}
int main()
{
int arr[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };
int sz = 10;
bubbleSort(arr, sz);
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
return 0;
}
冒泡排序C语言通用连续类型排序代码
上述C语言冒泡排序代码只支持整型排序，这里将其扩展为通用的连续类型排序代码。
参考C语言内置的qsort排序：
可以得到函数为：
void swap(char* a, char* b, size_t width)
{
for (int i = 0; i < width; ++i)
{
char temp = *(a + i);
*(a + i) = *(b + i);
*(b + i) = temp;
}
}
// 要排序的数组 数组大小 每个元素宽度 比较的函数指针
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{
// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
for (int i = 0; i < sz - 1; ++i)
{
bool flag = true; // 3.检查是否有序
// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
for (int j = 0; j < sz - 1 - i; ++j)
{
if (compare((char*)base + j * width, (char*)base + j * width + width) > 0)
{
flag = false; // 3.表示无序
swap((char*)base + j * width, (char*)base + j * width + width, width);
}
}
if (flag == true) // 3.有序直接退出循环
{
break;
}
}
}
事实上，我们只需要对其两个地方大幅度更改，就可以得到通用的排序：
对比较的方式更改：
将比较方式改为函数指针的方式，这样使用者使用时可以自己写比较的类型函数（不仅包含内置类型，struct 定义的也可以，但前提是连续的）
如果使用者对整型排序，则自己写的compare为（只供参考，方法不唯一）：
int cmp(const void* e1, const void* e2)
{
// (int*)e1 表示将泛型指针转为整型指针
// *((int*)e1) 表示对整型指针解引用从而得到整型的数
// 两整型的数相减，为正则e1大，为负则e2大，为0则相等
return *((int*)e1) - *((int*)e2);
}
对交换的方式更改：
这里只需将交换方式改为一个字节一个字节的方式交换即可。
则swap应改为：
void swap(char* a, char* b, size_t width)
{
// a 和 b 表示两个数开始的地址
// a + i 表示 a 元素第 i 块字节的地址，同理于b
// *(a + i) 表示 a 元素第 i 块字节的内容，同理于b
// 通过一个字节一个字节的交换，确保内容不会丢失
for (int i = 0; i < width; ++i)
{
char temp = *(a + i);
*(a + i) = *(b + i);
*(b + i) = temp;
}
}
结果验证：
内置类型：
完整代码：
#include <stdio.h>
#include <stdbool.h>
void swap(char* a, char* b, size_t width)
{
for (int i = 0; i < width; ++i)
{
char temp = *(a + i);
*(a + i) = *(b + i);
*(b + i) = temp;
}
}
// 要排序的数组 数组大小 每个元素宽度 比较的函数指针
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{
// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
for (int i = 0; i < sz - 1; ++i)
{
bool flag = true; // 3.检查是否有序
// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
for (int j = 0; j < sz - 1 - i; ++j)
{
if (compare((char*)base + j * width, (char*)base + j * width + width) > 0)
{
flag = false; // 3.表示无序
swap((char*)base + j * width, (char*)base + j * width + width, width);
}
}
if (flag == true) // 3.有序直接退出循环
{
break;
}
}
}
int cmp(const void* e1, const void* e2) // 对整形
{
return *((int*)e1) - *((int*)e2);
}
int cmp1(const void* e1, const void* e2) // 对字符
{
return *((char*)e1) - *((char*)e2);
}
int cmp2(const void* e1, const void* e2) // 对浮点
{
double num1 = *(double*)e1;
double num2 = *(double*)e2;
// double 返回与 int 冲突会影响，只需更改一下返回逻辑
return num1 > num2 ? 1 : -1;
}
int main()
{
int arr[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };
int sz = 10;
bubbleSort(arr, sz, sizeof(int), cmp);
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
char arr1[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };
double arr2[10] = { 3.1, 9.4, 2.9, 7.8, 8.8, 5.1, 6.2, 1.0, 10.1, 4.4 };
bubbleSort(arr1, sz, sizeof(char), cmp1);
bubbleSort(arr2, sz, sizeof(double), cmp2);
for (int i = 0; i < sz; ++i)
{
printf("%d ", arr1[i]);
}
printf("\n");
for (int i = 0; i < sz; ++i)
{
printf("%.2lf ", arr2[i]);
}
printf("\n");
return 0;
}
自定义类型：
完整代码：
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
void swap(char* a, char* b, size_t width)
{
for (int i = 0; i < width; ++i)
{
char temp = *(a + i);
*(a + i) = *(b + i);
*(b + i) = temp;
}
}
// 要排序的数组 数组大小 每个元素宽度 比较的函数指针
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{
// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
for (int i = 0; i < sz - 1; ++i)
{
bool flag = true; // 3.检查是否有序
// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
for (int j = 0; j < sz - 1 - i; ++j)
{
if (compare((char*)base + j * width, (char*)base + j * width + width) > 0)
{
flag = false; // 3.表示无序
swap((char*)base + j * width, (char*)base + j * width + width, width);
}
}
if (flag == true) // 3.有序直接退出循环
{
break;
}
}
}
typedef struct Student
{
char name[20];
int age;
char id[10];
} Student;
int cmpAge(const void* e1, const void* e2)
{
return ((Student*)e1)->age - ((Student*)e2)->age;
}
int cmpId(const void* e1, const void* e2)
{
return strcmp(((Student*)e1)->id, ((Student*)e2)->id);
}
int main()
{
Student arr[5] = {
{.name = "张三", .age = 20, .id = "1" },
{.name = "李四", .age = 21, .id = "2" },
{.name = "王二", .age = 18, .id = "3" },
{.name = "麻子", .age = 30, .id = "4" } };
int sz = 4;
bubbleSort(arr, sz, sizeof(Student), cmpAge);
printf("以年龄排序：\n");
for (int i = 0; i < sz; ++i)
{
printf("%s ", arr[i].name);
printf("%d ", arr[i].age);
printf("%s\n", arr[i].id);
}
printf("\n");
bubbleSort(arr, sz, sizeof(Student), cmpId);
printf("以ID排序：\n");
for (int i = 0; i < sz; ++i)
{
printf("%s ", arr[i].name);
printf("%d ", arr[i].age);
printf("%s\n", arr[i].id);
}
printf("\n");
return 0;
}
注意：
上述代码对不连续的数据无效，如链表的每个元素是以指针连接存储的，compare函数 和 swap函数 需要更改来解决。
