妙用指针实现qsort

缺乏、安全感 2023-10-14 10:09 2阅读 0赞

### 妙用指针实现qsort ###

*  qsort是什么
 *  qsort代码使用例子
 *  冒泡排序引言
 *  冒泡排序模拟qsort函数

# qsort是什么 #

qsort函数是C语言标准库中的一个快速排序函数，位于stdlib.h头文件中。（可以对任意类型进行排序的函数）  
函数为：

void qsort(
        void *base,
        size_t nmemb,
        size_t size,
        int (*compar)(const void *, const void *)
        );

> 参数解释  
> 参数base - base指向数组的起始地址，通常该位置传入的是一个数组名  
> 参数nmemb - nmemb表示该数组的元素个数  
> 参数size - size表示该数组中每个元素的大小（字节数）  
> 参数(\*compar)(const void \*, const void \*) - 此为指向比较函数的函数指针，决定了排序的顺序。

# qsort代码使用例子 #

#include <stdlib.h>
    
    int cmp_int(const void* p1, const void* p2)
    {
        
    	return (*(int*)p1 - *(int*)p2);
    }
    
    void print(int arr[], int sz)
    {
        
    	int i = 0;
    	for (i = 0; i < sz; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    }
    
    //测试qsort排序整型数据
    test1()
    {
        
    	int arr[10] = {
         3,1,5,2,4,7,9,6,8,0 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	//默认是升序的
    	qsort(arr, sz, sizeof(arr[0]), cmp_int);
    	print(arr, sz);
    }
    
    //测试qsort排序结构体数据
    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 test2()
    {
        
    	struct Stu arr[] = {
         {
        "zhangsan", 20}, {
        "lisi", 50},{
        "wangwu", 15} };
    	int sz = sizeof(arr) / sizeof(arr[0]); 
    	qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
    }
    
    int cmp_stu_by_name(const void* p1, const void* p2)
    {
        
    	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
    }
    
    void test3()
    {
        
    	struct Stu arr[] = {
         {
        "zhangsan", 20}, {
        "lisi", 50},{
        "wangwu", 15} };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	qsort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
    }
    
    int main()
    {
        
    //以上均为升序排列
    	//test1();
    	//test2();
    	test3();
    
    	return 0;
    }

> 代码解释qsort函数第四个参数（函数指针），自定义compar函数规则是  
> ![在这里插入图片描述][5dedd7ad984b43c2944f49dc111cbc65.png]

# 冒泡排序引言 #

代码演示：

# include <stdio.h>
    int main(void)
    {
        
        int a[] = {
        2,0，1,8，11,5};
        int n;  //存放数组a中元素的个数
        int i;  //比较的轮数
        int j;  //每轮比较的次数
        int buf;  //交换数据时用于存放中间数据
        n = sizeof(a) / sizeof(a[0]);  /*a[0]是int型, 占4字节, 所以总的字节数除以4等于元素的个数*/
        for (i=0; i<n-1; ++i)  //比较n-1轮
        {
        
            for (j=0; j<n-1-i; ++j)  //每轮比较n-1-i次,
            {
        
                if (a[j] > a[j+1])
                {
        
                    buf = a[j];
                    a[j] = a[j+1];
                    a[j+1] = buf;
                }
            }
        }
        for (i=0; i<n; ++i)
        {
        
            printf("%d\x20", a[i]);
        }
        printf("\n");
        return 0;
    }

![在这里插入图片描述][923a6034cbc1459291850630618689d6.gif_pic_center]

> 解释：上面的冒泡排序只对整形进行排序，  
> 外循环控制趟数，内循环控制比较次数  
> 前后两个比较，不满足规则就交换-  
> 如果是升序排序，每次将最大的放在最后一个，最后一个就不动了  
> 如果是降序排序，每次将最小的放在最后一个，最后一个就不动了

# 冒泡排序模拟qsort函数 #

void Swap(char* buf1, char* buf2, int size)//交换arr[j],arr[j+1]这两个元素
    {
        
    	int i = 0;
    	char tmp = 0;
    	for (i = 0; i < size; i++)
    	{
        
    		tmp = *buf1;
    		*buf1 = *buf2;
    		*buf2 = tmp;
    		buf1++;
    		buf2++;
    	}
    }
    
    void bubble_sort(void* base, int num, int size, int (*cmp)(const void*, const void*))
    {
        
    	int  i = 0;
    	//趟数
    	for (i = 0; i < num - 1; i++)
    	{
        
    		int j = 0;
    		//一趟内部比较的对数
    		for (j = 0; j < num - 1 - i; j++)
    		{
        
    			//假设需要升序cmp返回>0，交换
    			if (cmp((char*)base+j*size, (char*)base+(j+1)*size)>0)//两个元素比较，需要将arr[j],arr[j+1]的地址要传给cmp
    			{
        
    				//交换
    				Swap((char*)base + j * size, (char*)base + (j + 1) * size, size);
    			}
    		}
    	}
    
    }
    
    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;
    }
    
    //测试bubble_sort 排序结构体数据
    //void test2()
    //{
        
    //	struct Stu arr[] = { {"zhangsan", 20}, {"lisi", 50},{"wangwu", 15} };
    //	int sz = sizeof(arr) / sizeof(arr[0]); 
    //	bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_age);
    //}
    
    int cmp_stu_by_name(const void* p1, const void* p2)
    {
        
    	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
    }
    
    
    void test3()
    {
        
    	struct Stu arr[] = {
         {
        "zhangsan", 20}, {
        "lisi", 50},{
        "wangwu", 15} };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	//printf("%d\n", sizeof(struct Stu));
    	bubble_sort(arr, sz, sizeof(arr[0]), cmp_stu_by_name);
    }
    
    
    //B
    int cmp_int(const void* p1, const void* p2)
    {
        
    	return (*(int*)p1 - *(int*)p2);
    }
    
     
    //测试bubble_sort 排序整型数据
    void test1()
    {
        
    	int arr[10] = {
         3,1,5,2,4,7,9,6,8,0 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
    }
    int main()
    {
        
    	//test1();
    	//test2();
    	test3();
    
    	return 0;
    }

\*\*注：void中文翻译为"无类型"。常用在程序编写中对定义函数的参数类型、返回值、函数中指针类型进行声明。  
void的字面意思是"无类型"，void *则为"无类型指针"，void 可以指向任何类型的数据。*

> 代码解释，以test3（）为例，运行到test（）；进入函数内部，初始化结构体,调用自定义模拟qsort函数bubble\_sort，外部循环和内部循环与冒泡排序相同，主要看判断，和交换函数，  
> 先看判断函数cmp\_stu\_by\_name，两个参数为const void*类型，表示他们两个为任意指针传参，函数内部将两个指针强转成我们需要的指针类型struct Stu*，然后比较name大小，这里用到了strcmp函数，他对两个字符数组首元素大小比较的，  
> p1的name首元素小于p2的首元素返回负值，p1的name首元素大于p2的首元素返回正值，p1的name首元素等于p2的首元素返回0，  
> 然后看交换函数Swap，这里用char*类型作为形参，是因为，我们不知道传过来的是什么指针类型，但我们知道大小，而char*的权重是最小的，他地址加1只会跳一个字节，当我们知道数据大小时就可以按字节交换，  
> 我们现在就可以理解这段代码了，当p1大于p2时交换p2放在前面，p1小于p2不交换  
> p1放在前面  
> ![在这里插入图片描述][03172ee1e0ab46c982492d7087f74ddf.png_pic_center]

[5dedd7ad984b43c2944f49dc111cbc65.png]: https://img-blog.csdnimg.cn/5dedd7ad984b43c2944f49dc111cbc65.png
[923a6034cbc1459291850630618689d6.gif_pic_center]: https://img-blog.csdnimg.cn/923a6034cbc1459291850630618689d6.gif#pic_center
[03172ee1e0ab46c982492d7087f74ddf.png_pic_center]: https://img-blog.csdnimg.cn/03172ee1e0ab46c982492d7087f74ddf.png#pic_center