一.冒泡排序
void bubble_sort(int arr[], int sz) { int i, j; for (i = 0; i < sz - 1; i++) { int flag = 1; for (j = 0; j < sz - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 0;//说明不有序 } } if (flag == 1)//说明有序 break; } }
但是这个冒泡排序仅仅限于整数进行排序，对于浮点数，结构体等类型无法进行排序，而我们知道库函数的qsort函数是可以实现任何类型的排序。
二.qsort函数
在msdn上我们可以看到qsort函数是这样定义的。我们可以分析一下
我们发现qsort函数是有包含一个函数指针的，那就是它的最后一个元素，它取决于我们怎么比较
如果返回一个大于0的数，那么就要进行交换，如果返回一个小于等于0的数，则不变。
比如两个结构体怎么比较呢？
我们简单的用了一个结构体，然后对其中的元素进行排序，由于结构体的两个元素分别是名字和年龄，我们针对于这两个分别设计了比较函数。
#include<string.h> #include<stdlib.h> #include<stdio.h> struct Stu { char name[20]; int age; }; int cmp_int_by_age(const void* e1, const void* e2) { return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age; } int cmp_int_by_name(const void* e1, const void* e2) { return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name); //字符串比较大小必须要strcmp，返回值恰好是>0,<0,=0的数。 } void test2() { struct Stu s[] = { {"张三",15},{"李四",30},{"王五",25} }; int sz = sizeof(s) / sizeof(s[0]); //qsort(s, sz, sizeof(s[0]), cmp_int_by_age); qsort(s,sz,sizeof(s[0]),cmp_int_by_name); int i = 0; for (i = 0; i < 3; i++) { printf("%s ", s[i].name); } printf("\n"); } int main() { test2(); return 0; }
三.利用冒泡排序的思想实现qsort函数
这个函数构造还是比较有意思的。
void Swap(char* buf1, char* buf2, int width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } //全部要交换 } void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2)) { //这里我们还是利用冒泡排序的思想，只不过需要对函数加以改造 int i, j; for (i = 0; i < sz - 1; i++) { int flag = 1;//已经有序的不必再比较 for (j = 0; j < sz - i - 1; j++) { //因为qsort传参是无符号类型，所以我们可以利用起始位置+偏移量的方式 if (cmp((char*)base + j * (width), (char*)base + (j + 1) * (width)))//base是void*，我们要转换为char* //找地址，转换成char*+j*width //(char*)base+(j+1)*width { //交换 Swap((char*)base + j * (width), (char*)base + (j + 1) * (width), width);//宽度,传宽度进来是 //是因为不同数据类型的大小是不一样的，要进行交换，需要传数据类型大小 flag = 0;//说明无序 } } if (flag == 1) break; } }
，接下来我们可以验证一下是否成功.
四.验证冒泡排序实现qsort函数
①验证数组的排序
代码：
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2)) { //这里我们还是利用冒泡排序的思想，只不过需要对函数加以改造 int i, j; for (i = 0; i < sz - 1; i++) { int flag = 1;//已经有序的不必再比较 for (j = 0; j < sz - i - 1; j++) { //因为qsort传参是无符号类型，所以我们可以利用起始位置+偏移量的方式 if (cmp((char*)base + j * (width), (char*)base + (j + 1) * (width)))//base是void*，我们要转换为char* //找地址，转换成char*+j*width //(char*)base+(j+1)*width { //交换 Swap((char*)base + j * (width), (char*)base + (j + 1) * (width), width);//宽度,传宽度进来是 //是因为不同数据类型的大小是不一样的，要进行交换，需要传数据类型大小 flag = 0;//说明无序 } } if (flag == 1) break; } } void print(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } void test2() { int arr[] = { 9,8,2,3,7,6,4,2,1,0 }; int sz = sizeof(arr) / sizeof(arr[0]); print(arr, sz); bubble_sort(arr, sz, sizeof(arr[0]), cmp_int); print(arr, sz); } int main() { test2(); return 0; }
我们发现，它完美实现了排序的功能。
②验证结构体的排序
#include<stdio.h> #include<stdlib.h> #include<string.h> struct Stu { char name[20]; int age; }; int cmp_int_by_name(const void* e1, const void* e2) { return strcmp(((struct Stu*)e1)->name, (((struct Stu*)e2)->name)); } void Swap(char* buf1, char* buf2, int width) { int i = 0; for (i = 0; i < width; i++) { char tmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; } //全部要交换 } void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2)) { //这里我们还是利用冒泡排序的思想，只不过需要对函数加以改造 int i, j; for (i = 0; i < sz - 1; i++) { int flag = 1;//已经有序的不必再比较 for (j = 0; j < sz - i - 1; j++) { //因为qsort传参是无符号类型，所以我们可以利用起始位置+偏移量的方式 if (cmp((char*)base + j * (width), (char*)base + (j + 1) * (width)))//base是void*，我们要转换为char* //找地址，转换成char*+j*width //(char*)base+(j+1)*width { //交换 Swap((char*)base + j * (width), (char*)base + (j + 1) * (width), width);//宽度,传宽度进来是 //是因为不同数据类型的大小是不一样的，要进行交换，需要传数据类型大小 flag = 0;//说明无序 } } if (flag == 1) break; } } void print2(struct Stu s[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%s %d\n", s[i].name, s[i].age); } } void test3() { //测试使用qsort来排序结构数据 struct Stu s[] = { {"张三",15},{"李四",30},{"王五",25} }; int sz = sizeof(s) / sizeof(s[0]); print2(s, sz); printf("********************\n"); bubble_sort(s, sz, sizeof(s[0]), cmp_int_by_name); print2(s, sz); } int main() { test3(); return 0; }
结果也是非常正确。好了，今天的分享就到这里了
