玩转qsort——“C”

各位CSDN的uu们你们好呀，今天小雅兰的内容还是我们的深度剖析指针呀，上篇博客我们学习了回调函数这个知识点，但是没有写完，因为：小雅兰觉得qsort值得单独写出来！！！好啦，就让我们进入指针的世界吧

qsort是一个库函数，是用来排序的库函数，使用的是快速排序的方法 

quicksort

我们先来复习一下之前所学习过的一种算法——冒泡排序

冒泡排序——“C”_认真学习的小雅兰.的博客-CSDN博客

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void bubble_sort(int arr[], int sz)
{int i = 0;for (i = 0; i < sz - 1; i++){//一趟冒泡排序的过程int j = 0;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_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}
int main()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };//排序//使用冒泡排序的算法，来排序int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);//打印print_arr(arr, sz);return 0;
}

但是，这个算法最大的缺点就是只能排序整型，如果未来要排序浮点数呢？如果未来要排序一些字符串呢？结构体呢？那么，这个函数就搞不定了，仅仅能排序固定类型的数据

 qsort的好处：

• 现成的
• 可以排序任意类型的数据

 void qsort( void *base,//指向了待排序数组的第一个元素

                     size_t num,//待排序的元素个数

                     size_t width,//每个元素的大小，单位是字节

                     int (__cdecl *compare )(const void *elem1, const void *elem2 )

                     //函数指针

                     //指向一个函数，这个函数可以比较两个元素的大小

                   );

qsort是可以排序任意类型的数据的

1. 比较两个整数的大小，>  <  =
2. 比较两个字符串，strcmp
3. 比较两个结构体数据（学生：张三、李四），指定比较的标准，拿什么比较？ 

int a=10;

void * p=&a;

//void * ——无具体类型的指针，所以它可以接收任何类型的地址

//*p;//err void*的指针不能使用解引用操作符

//p++;//err

下面，我们来使用一下qsort函数：

#include<stdio.h>
#include<stdlib.h>
//qsort函数的使用者提供这个函数
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
void print_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
test1()
{int arr[] = { 9,8,7,6,5,4,3,2,1,0 };int sz = sizeof(arr) / sizeof(arr[0]);//使用qsort来排序整型数组，这里就要提供一个比较函数，这个比较函数能够比较2个整数的大小//qsort默认是排成升序的qsort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}
int main()
{test1();return 0;
}

 

 qsort这个库函数是不是很神奇呢？下面还有更加神奇的！！！

我们来测试一下qsort排序结构体数据

#include<stdio.h>
#include<stdlib.h>
//qsort函数的使用者提供这个函数
int cmp_int(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
struct Stu
{char name[20];int age;
};
int cmp_stu_by_age(const void* p1, const void* p2)
{return ((struct  Stu*)p1)->age - ((struct Stu*)p2)->age;
}
void print(struct Stu* ps, int sz)
{int i = 0;for (i = 0; i < 3; i++){printf("%d\n", ps[i].age);}
}
void test2()
{struct Stu s[] = { {"zhangsan",30},{"lisi",25 }, { "wangwu",50 } };int sz = sizeof(s) / sizeof(s[0]);//测试按照年龄来排序qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);print(s, sz);
}
int main()
{test2();return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Stu
{char name[20];int age;
};
int cmp_stu_by_name(const void* p1, const void* p2)
{return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
void print(struct Stu *ps, int sz)
{int i = 0;for (i = 0; i < 3; i++){printf("%s\n", ps[i].name);}
}
void test2()
{struct Stu s[] = { {"zhangsan",30},{"lisi",25},{"wangwu",50} };int sz = sizeof(s) / sizeof(s[0]);//测试按照名字来排序qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);print(s, sz);
}
int main()
{test2();return 0;
}

qsort底层是快速排序，但是小雅兰还没有学习快速排序的思想，所以暂时还不能之间实现qsort，所以使用冒泡排序的思想来实现一个类似于qsort这个功能的冒泡排序函数bubble_sort

使用回调函数，模拟实现qsort（采用冒泡的方式）。

测试函数：

void test3()
{int arr[] = { 3,1,5,2,4,9,8,6,7,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}

主函数：

int main()
{test3();return 0;
}

模拟实现的bubble_sort()函数：

//假设排序为升序
//希望这个bubble_sort函数可以排序任意类型的数据
void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2))
{//base 待排序数组的第一个元素//元素个数和元素个数的大小不可能是负数，所以是size_t类型//函数指针//要确定趟数size_t i = 0;for (i = 0; i < num - 1; i++){//一趟冒泡排序的过程size_t j = 0;int flag = 1;//假设已经有序了//标记变量for (j = 0; j < num - 1 - i ; j++){//两个相邻的元素比较//arr[j] arr[j+1]if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//强制类型转换为char*//因为base为void类型，不能之间进行加减乘除，所以强制类型转换，但是又不能转换为int*，因为不一定就排序整型数组flag = 0;//交换Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}if (flag == 1){break;}}
}

在bubble_sort()函数中，调用了自定义的函数Swap，是用来交换元素的：

int cmp_int(const void* p1, const void* p2)//不知道要排序什么类型的数组,所以用void*
{return *(int*)p1 - *(int*)p2;
}
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 print_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}

 

完整代码如下所示：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int cmp_int(const void* p1, const void* p2)//不知道要排序什么类型的数组,所以用void*
{return *(int*)p1 - *(int*)p2;
}
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++;}
}
//假设排序为升序
//希望这个bubble_sort函数可以排序任意类型的数据
void bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* p1, const void* p2))
{//base 待排序数组的第一个元素//元素个数和元素个数的大小不可能是负数，所以是size_t类型//函数指针//要确定趟数size_t i = 0;for (i = 0; i < num - 1; i++){//一趟冒泡排序的过程size_t j = 0;int flag = 1;//假设已经有序了//标记变量for (j = 0; j < num - 1 - i ; j++){//两个相邻的元素比较//arr[j] arr[j+1]if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0){//强制类型转换为char*//因为base为void类型，不能之间进行加减乘除，所以强制类型转换，但是又不能转换为int*，因为不一定就排序整型数组flag = 0;//交换Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);}}if (flag == 1){break;}}
}
void print_arr(int arr[], int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}printf("\n");
}
void test3()
{int arr[] = { 3,1,5,2,4,9,8,6,7,0 };int sz = sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);print_arr(arr, sz);
}
int main()
{test3();return 0;
}

---

 好啦，小雅兰玩转的qsort就到这里啦，这篇博客难度很大，确实花了小雅兰很多时间，未来还要继续加油呀！！！