【C语言】指针篇-精通库中的快速排序算法：巧妙掌握技巧（4/5）

🌈个人主页：是店小二呀

🌈C语言笔记专栏：C语言笔记

🌈C++笔记专栏： C++笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅

文章目录

• 一、回调函数
• 二、快速排序(Qsort)
• • 2.1 Qsort参数部分介绍
  • 2.2 不同类型的比较方法
  • 2.3 简单使用Qsort(对任意数据类型进行排序)
  • 三、冒泡排序思想模拟实现快速排序(不是真正的快速排序)
  • • 3.1 函数内部:
    • 3.2 底层逻辑解析：
    • • 3.2.1 判断语句:
      • 3.2.2 比较函数:
      • 3.2.3 Swap函数参数:
      • 3.2.4 Swap内部逻辑:

        ---

        一、回调函数

        回调函数：通过一个函数指针调用的函数。把一个函数的地址作为一个参数传递给另外一个函数，当这个地址被用来调用其指向的函数时，被调用函数称为回调函数（跟函数嵌套差不多）

        //使⽤回到函数改造后
        #include 
        int add(int a, int b)
        {
        	return a + b;
        }
        int sub(int a, int b)
        {
        	return a - b;
        }
        int mul(int a, int b)
        {
        	return a * b;
        }
        int d(int a, int b)
        {
        	return a / b;
        }
        void calc(int(*pf)(int, int))
        {
        	int ret = 0;
        	int x, y;
        	printf("输⼊操作数：");
        	scanf("%d %d", &x, &y);
        	ret = pf(x, y);
        	printf("ret = %d\n", ret);
        }
        int main()
        {
        	int input = 1;
        	do
        	{
        		scanf("%d", &input);
        		switch (input)
        		{
        		case 1:
        			calc(add);
        			break;
        		case 2:
        			calc(sub);
        			break;
        		case 3:
        			calc(mul);
        			break;
        		case 4:
        			calc(d);
        			break;
        		case 0:
        			printf("退出程序\n");
        			break;
        		default:
        			printf("选择错误\n");
        			break;
        		}
        	} while (input);
        	return 0;
        }
        

        ---

        二、快速排序(Qsort)

        快速排序属于九大排序之一，并且该函数在头文件stdlib.h 声明

        

        2.1 Qsort参数部分介绍

        void qsoer(void *base, size_t num, size_t size, int (*compare)(const void*,const void*))；
        

        • void * base:待排序数据的起始位置，第一个元素
        • size_t num:待排序数据的元素个数
        • size_t size:待排序数据的每个元素的大小，单位是字节
        • int (*compare)(const void *,const void *):函数指针-指针指向的函数是来比较待排序数据中的两个元素大小关系

          【注意】:void 是无具体类型的指针(通用指针类型)，对此可以接收任意数据类型的地址

          2.2 不同类型的比较方法

          【提前说明】:关于比较函数的参数部分，void *是无具体类型的指针(通用指针类型)，对此可以接收任意数据类型的地址。

          整形类型:

          int int_compare(const void* e1, const void* e2)
          {
          	return *((int*)e1) - *((int*)e2);
          }
          

          字符类型(比较单字符的大小，字符串函数头文件string.h):

          int char_compare(const void* e1, const void* e2)
          {
          	return strcmp((char*)e1, (char*)e2);
          } 
          

          字符串长度：

          int charnums_compare(const void* e1, const void* e2)
          {
          	return strlen((char*) e1) - strlen((char*) e1);
          }
          

          结构体整形成员：

          int  int_age_compare(const void* e1, const void* e2)
          {
          	return ((struct su*)e1)->age - ((struct su*)e2)->age;
          }
          

          结构体字符串成员：

          int char_name_compare(const void* e1, const void* e2)
          {
          	return strcmp(((struct su*)e1)->name, ((struct su*)e1)->name);
          }
          

          【说明】:不同类型数据的比较不能单单只通过大于小于号去判断，需要掌握不同类型的比较方法，以便于更好的使用qsort函数，但是在C++中，一般使用sort，而不是qsort函数，因为使用起来很复杂，而且需要自己实现个比较函数。

          2.3 简单使用Qsort(对任意数据类型进行排序)

          struct su
          {
              int age;
              char name[100];
          };
          int main()
          {
              int nums[] = { 2,6,7,9,10,1,8,5,3 };
              int sz = sizeof(nums) / sizeof(nums[0]);
              qsort(nums, sz, sizeof(nums[0]), compare);//函数名变身就是一个函数指针变量
              
              //结构体数组
              struct su s[] = { {18,"zhangsana"},{14,"xiaoming"},{9,"lierdan"} };
              int sz2 = sizeof(s) / sizeof(s[0]);
              qsort(s, sz, sizeof(s[0]), age_compare);
              return 0;
          }
          

          ---

          三、冒泡排序思想模拟实现快速排序(不是真正的快速排序)

          前文:冒泡排序是一种简单的排序，但是只能排序整形数据，无法适应不同类型的场景。对此，我们将通过冒泡排序的思想模拟实现一个对任意类型能排序的快速排序

          【注意】:快速排序的底层不是这样子实现的，对此这里不是真正的快速排序

          int main()
          {
          	int nums[] = { 2,6,7,9,10,1,8,5,3 };
          	int sz = sizeof(nums) / sizeof(nums[0]);
          	int with = sizeof(nums[0]);
          	my_qsort(nums, sz, with, int_compare);
              return
          }
          

          3.1 函数内部:

          void my_qsort(int* p, int sz, int width, int (*compare)(const void* e1, const void* e2))
          {
          	for (int i = 0; i 0)//compare 根据类型去定义
          			{ 
          				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
          			}
          		}
          	}
          }
          

          【说明】:函数实现框架跟冒泡排序相似，主要的不同在于判断和交换语句底层逻辑的不同

          ---

          3.2 底层逻辑解析：

          3.2.1 判断语句:

          if(compare((char*)base+j*width,(char *)base+(j+1)*width))

          【说明】:

          强制类型转化为char*类型(char *类型对于±整形，偏移量为一个字节)。width是某个类型的大小，那么这两个参数之间相差width大小，正好跳过某个类型元素。(适用于任意的数据进行比较)

          3.2.2 比较函数:

          int int_compare(const void* e1, const void* e2)//对比分类型
          {
          	return *(int*)e1 - *(int*)e2;
          }
          

          【函数名】:int_compare表明了这里适合对整形数据对比，对于不同数据类型有不同的比较方法，在上面使用库函数qsort中有所涉及

          3.2.3 Swap函数参数:

          Swap((char*)base + j * width, (char*)base + (j + 1) * width, width)

          【说明】:base是待排序数据的起始位置(首元素的地址)，强制类型转化为char*类型，使得对于±整型，偏移量为一个字节。width是某个类型的大小，那么这两个参数之间相差width大小，正好跳过某个类型元素(j * width –(j + 1) * width )。(适用于任意的数据进行比较)

          3.2.4 Swap内部逻辑:

          void Swap(char* e1, char* e2,int width)
          {
          	for (int i = 0; i
          		char tmp = *e1;
          		*e1 = *e2;
          		*e2 = tmp;
          		e1++;
          		e2++;
          	  }
          }