c语言-qsort函数-Toy模板网

这篇具有很好参考价值的文章主要介绍了c语言-qsort函数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、函数介绍

二、qsort函数的使用

1、对int类型数组排序

2、对char类型排序

3、对浮点型排序

4.比较字符串

4.1按首字母排序

4.2按长度排序

4.3按字典顺序

5.结构体排序

5.1 多级排序

三、模拟实现qsort函数

【冒泡排序的实现】

【主函数部分】

【代码详解】

【代码实现之整型排序】

【代码实现之结构体类型排序】

四、快速排模拟实现qsort()函数

一、函数介绍

qsort就是C语言中的快排函数，包含在stdlib.h头文件中，函数一共有四个参数，没有返回值。

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

1. void * base : 首先来了解一下什么是 void* ，这个是无具体类型的指针，void * 的指针是非常宽容的，可以接收任意类型的数据。常常用来临时存放数据，等到需要使用数据时，我们必须要强制类型转换成某一具体类型的数据，才能对数据进行操作。

c语言-qsort函数,C语言,c语言,开发语言

对void *pa,接收了一个整型 a 的地址，我们对指针pa 进行强制类型转换（int*），再解引用 pa即可对变量a 进行操作。

void *base 存的就是待排序数据的起始地址（不能直接访问）。

这个参数是 qsort() 函数能够对任意数据排序的基础。

2. size_t num : 记录待排序数据元素个数。

3. size_t size : 记录待排序数据任意一个元素的所占的字节数（元素的大小）。

4. int (*compar) (const void* , const void* ) :

这其实是一个函数类型的指针，可以用来存储函数的地址，然后也提前声明了函数的参数，返回值

返回值是 int 类型，参数部分是两个 void * 类型的接收。这个函数的作用是来比较两个参数的大小，然后返回比较果结，怎么比呢？如果是整型数据使两个参数相减，返回结果。如果是字符串，我们可以使用 strcmp(“字符串”，“字符串”);strcmp 函数的返回值也是整型数据（这个是根据对应的场景，选择比较方式），即可得到相应的结果。

这第四个参数需要我们自己设计实现，函数的作用就是比较任意两个参数，返回一个整型数据，就可以利用这个数据来判断两个元素大小，所以这是个比较排序。

对于陌生的库函数，可通过cplusplus网站来了解它

【qsort参数介绍】

c语言-qsort函数,C语言,c语言,开发语言

【比较函数的返回值】

c语言-qsort函数,C语言,c语言,开发语言

qsort函数大致的模板为

int compare(const void* p1, const void* p2) //
{
	return p1 - p2; //返回的是升序
	return p2 - p1; //返回的是降序   
    
    //注：p1和p2的类型根据实际情况写
}
 
int main()
{
	int arr[] = { 1,3,4,6,7,2,10,8,5,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素个数 40 / 4 = 10
 
	qsort(arr, sz, sizeof(arr[0]), compare);
	//arr - 指向要排序的数组的第一个元素的指针。
	//sz -  由 arr 指向的数组中元素的个数
	//sizeof(arr[0]) - 数组中每个元素的大小，以字节为单位。
	//compar - 用来比较两个元素的函数。
 
	return 0;
}

Q：为什么compare的形参的两个参数是void*类型？

因为qsort函数可以实现对数组(int)、字符串(char)、结构体(stuct)等类型进行升序或降序排序，void*是无具体类型的指针，是不介意类型的，就像一个“垃圾桶”，任意的类型的地址都能往void*塞，但就是不能对其直接使用（解引用操作，++，--等等）。若想使用，只要进行强制类型转化即可。

二、qsort函数的使用

1、对int类型数组排序

//升序的情况
#include <stdlib.h>  //使用qsort需要包含头文件
#include <stdio.h>  
int compare_int(const void* p1, const void* p2) 
{
	return *(int*)p1 - *(int*)p2; //强制类型转化并解引用
}
 
int main()
{
	int arr[] = { 1,3,4,6,7,2,10,8,5,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	qsort(arr, sz, sizeof(arr[0]), compare_int);
	
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
 
	return 0;
}

//降序的情况
#include <stdlib.h>  //使用qsort需要包含头文件
#include <stdio.h>  
int compare_int(const void* p1, const void* p2) 
{
	return *(int*)p2 - *(int*)p1; //强制类型转化并解引用
}
 
int main()
{
	int arr[] = { 1,3,4,6,7,2,10,8,5,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	qsort(arr, sz, sizeof(arr[0]), compare_int);
	
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
 
	return 0;
}

2、对char类型排序

//升序的情况
#include <stdio.h>
#include <stdlib.h>
 
int compare_char(const void* p1, const void* p2) 
{
	return *(char*)p1 - *(char*)p2; //强制类型转化并解引用
}
 
int main()
{
	char arr[] = { 'f', 'b','e','a','d','c'};
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	
	qsort(arr, sz, sizeof(arr[0]), compare_char);
	
	for (int i = 0; i < sz; i++)
	{
		printf("%c ", arr[i]);
	}
	return 0;
}

3、对浮点型排序

#include <stdio.h>
#include <stdlib.h>
 
int compare_double(const void* p1, const void* p2) 
{
	return (*(double*)p1 > *(double*)p2 ? 1 : -1); //三目操作符
}
 
int main()
{
	double arr[] = { 3.14,2.6,2.3,1.7};
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	
	qsort(arr, sz, sizeof(arr[0]), compare_double);
	
	for (int i = 0; i < sz; i++)
	{
		printf("%lf ", arr[i]);
	}
 
 
	return 0;
}

注意

用qsort对浮点型的一定要用三目运算符，由于浮点数的精度问题，如果是两个很接近的数相减，则可能返回一个接近0的小数，而compare_double的返回值是int型，因此会将这个小数返回0。

4.比较字符串

4.1按首字母排序

#include<stdio.h>
#include<stdlib.h>
#define L 10
#define K 10
int inc(const void *a, const void *b)
{
	return *(char *)a - *(char *)b;
 } 
int main ()
{
	char a[L][K] = {
		"rbsc",
		"jcse",
		"efgd",
		"arbs",
		"bbs",
		"cbfe",
		"dgafg" ,
		"ewqrta",
		"ofgd",
		"mbcv",
	};
	qsort(a, L, sizeof(char) * K, inc);
	for (int i = 0; i < L; i++)
	{
		printf("%s\n", a[i]);
	}
 }

4.2按长度排序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define L 10
#define K 10
int inc(const void *a, const void *b)
{
	return strlen((char *)a) > strlen((char *)b) ? 1 : -1;
 } 
int main ()
{
	char a[L][K] = {
		"rbsc",
		"jcsse",
		"efgdsd",
		"arbs",
		"bbs",
		"cbfefaa",
		"dgafg" ,
		"ewqrta",
		"ofgd",
		"mbcv312",
	};
	qsort(a, L, sizeof(char) * K, inc);
	for (int i = 0; i < L; i++)
	{
		printf("%s\n", a[i]);
	}
 }

4.3按字典顺序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define L 10
#define K 10
int inc(const void *a, const void *b)
{
	return strcmp((char * )a, (char *)b);
 } 
int main ()
{
	char a[L][K] = {
		"rbsc",
		"jcsse",
		"afgdsd",
		"arbs",
		"abs",
		"cbfefaa",
		"cgafg" ,
		"ewqrta",
		"ofgd",
		"mbcv312",
	};
	qsort(a, L, sizeof(char) * K, inc);
	for (int i = 0; i < L; i++)
	{
		printf("%s\n", a[i]);
	}
 }

5.结构体排序

5.1 多级排序

结构体体的三级排序测试：
第一级是对学生成绩整体从小到大排序；
第二级是对相同成绩的学生，按照姓名进行排序；
第三级是对相同成绩、姓名的学生，按照学号进行排序；

#include<stdio.h>
#include<stdlib.h>
#include<string.h> 
typedef struct student
{
    int id;
	char name[10];
    int grade;	
}student;
 
int cmp1(const void *a, const void *b)//一级排序
{
    student *s1 = (student*)a;
    student *s2 = (student*)b;
    return s1->id - s2->id;
}

int cmp2(const void *a,const void *b)//二级排序
{
	student *s1 = (student*)a;
    student *s2 = (student*)b;
	if(strcmp(s1->name , s2->name) != 0)
		return strcmp(s1->name , s2->name);	
	else	
		return s1->id - s2->id;				
}

int cmp3(const void *a,const void *b)//三级排序
{
	student *s1 = (student*)a;
    student *s2 = (student*)b;
	if(s1->grade != s2->grade)	
		return s1->grade - s2->grade;
	else
	{
		if(strcmp(s1->name , s2->name) != 0)
			return strcmp(s1->name , s2->name);
		else
			return s1->id - s1->id;
	}
}

int main()
{
    int i,N,C;
	scanf("%d %d",&N,&C);
	
	student *stu;
	stu=(student*)malloc(N*sizeof(student));

	for(i = 0 ; i < N ; i++)
		scanf("%d %s %d" , &stu[i].id , stu[i].name , &stu[i].grade);
	switch(C)
	{
		case 1:	qsort(stu, N, sizeof(student), cmp1);break;//一级排序
		case 2:	qsort(stu, N, sizeof(student), cmp2);break;//二级排序
		case 3:	qsort(stu, N, sizeof(student), cmp3);break;//三级排序
	}
	printf("排序结果:\n");
	for(i = 0 ; i < N ; i++)
		printf("%03d %s %d\n" , stu[i].id , stu[i].name , stu[i].grade);
    return 0;
}

三、模拟实现qsort函数

模拟实现qsort函数是要基于冒泡排序实现的（冒泡排序讲解）

【冒泡排序的实现】

#include <stdio.h>
void Sort(int arr[], int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		
		for (int 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;
			}
		}
	}
}
int main()
{
	int arr[] = { 2,6,8,7,6,0,1,5,9,3 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Sort(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

现要求改造冒泡排序，使整个函数可以排序任意类型的数组

以整型数组为例

【主函数部分】

#include <stdio.h>
int cmp_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
 
int main()
{ 
	int arr[] = { 2,6,8,7,6,0,1,5,9,3 };
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	Sort(arr, sz, sizeof(arr[0]), cmp_int); 
 
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

【Sort函数部分】

参考qsort函数的参数

c语言-qsort函数,C语言,c语言,开发语言

void Swap(char* x1, char* x2, int width)
{
	//因为不知道是什么类型，要一个字节一个字节交换
	for (int i = 0; i < width; i++)
	{
		char tmp = *x1;
		*x1 = *x2;
		*x2 = tmp;
		x1++;
		x2++;
	}
}
 
//void* base - 要求排序不同类型的数组，void*恰好能接收任意类型
//int sz - 元素个数
//int width - 一个元素的大小
//int (*p)(const void*, const void*)  函数传参函数指针接收
//size_t - 无符号整型
 
void Sort(void* base, size_t sz, size_t width, int (*p)(const void*, const void*))
{
	for (size_t i = 0; i < sz - 1; i++)
	{
		for (size_t j = 0; j < sz - 1 - i; j++)
		{
            //通过函数指针p调用的函数cmp_int,所以这是个回调函数
			if (p((char*)base + j * width,(char*)base + (j + 1) * width) > 0)
			{
				//写一个Swap函数来交换
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

【代码详解】

c语言-qsort函数,C语言,c语言,开发语言

【代码实现之整型排序】

int cmp_int(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
 
void Swap(char* x1, char* x2, int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *x1;
		*x1 = *x2;
		*x2 = tmp;
		x1++;
		x2++;
	}
}
 
void Sort(void* base, size_t sz, size_t width, int (*p)(const void*, const void*))
{
	for (size_t i = 0; i < sz - 1; i++)
	{
		for (size_t j = 0; j < sz - 1 - i; j++)
		{
			if (p((char*)base + j * width,(char*)base + (j + 1) * width) > 0)
			{
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}
 
int main()
{ 
	int arr[] = { 2,6,8,7,6,0,1,5,9,3 };
	int sz = sizeof(arr) / sizeof(arr[0]);
 
	Sort(arr, sz, sizeof(arr[0]), cmp_int); 
 
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

【代码实现之结构体类型排序】

以排列姓名为例

struct Stu
{
	char name[20];
	int age;
};
int compare_name(const void* p1, const void* p2)
{
	return strcmp(((struct Stu*)p1)->name, ((struct Stu*)p2)->name);
}
 
 
void Swap(char* x1, char* x2, int width)
{
	for (int i = 0; i < width; i++)
	{
		char tmp = *x1;
		*x1 = *x2;
		*x2 = tmp;
		x1++;
		x2++;
	}
}
 
void Sort(void* base, size_t sz, size_t width, int (*p)(const void*, const void*))
{
	for (size_t i = 0; i < sz - 1; i++)
	{
		for (size_t j = 0; j < sz - 1 - i; j++)
		{
			if (p((char*)base + j * width,(char*)base + (j + 1) * width) > 0)
			{
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}
 
int main()
{ 
	struct Stu s[3] = { {"张三",10},{"李四",30},{"王五",21} };
	int sz = sizeof(s) / sizeof(s[0]);
 
	Sort(s, sz, sizeof(s[0]), compare_name);
 
	for (int i = 0; i < sz; i++)
	{
		printf("%s %d\n", s[i].name,s[i].age);
	}
	return 0;
}

四、快速排模拟实现qsort()函数

#include <stdio.h>
#include <stdlib.h>
 
int Cmp_qsort(void const* p1, void const* p2)//用户输入，
{
	int size1 = (*(int*)p1 - *(int*)p2);
	return size1;
}
 
//交换数据
void Swap(char* base1, char* base2, int size)
{
	for (int i = 0; i < size; ++i)//按字节转换
	{
		char tmp = *base1;
		*base1 = *base2;
		*base2 = tmp;
		++base1;
		++base2;	
	}
}
 
//模拟实现
void _Quick_qsort(void const* base, int left, int right, int size, int(*Cmp_qsort)(void const* p1, void const* p2))
{
	if (left >= right)
	{
		return;
	}
 
	int begin = left;
	int end = right;
	int key = begin;//记录坑位的下标、
 
	while (begin < end)
	{
 
		while (begin < end && (Cmp_qsort((char*)base+ key*size, (char*)base + end * size) <= 0))
			--end;
 
		while (begin < end && (Cmp_qsort((char*)base+ key*size, (char*)base + begin * size) >= 0))
			++begin;
		Swap((char*)base +begin * size, (char*)base+end*size, size);
 
	}
	Swap((char*)base + begin * size, (char*)base + key * size, size);
 
	_Quick_qsort(base, left, begin - 1, size, Cmp_qsort);
	_Quick_qsort(base, begin + 1, right, size, Cmp_qsort);
 
}
 
 
//过渡一下
void Quick_qsort(void const* base, int len, int size,int(*Cmp_qsort)(void const *p1,void const *p2))
{
	_Quick_qsort(base, 0, len - 1, size, Cmp_qsort);//左右区间写入参数，
}
 
//打印
void Print(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
}
 
//快排左右指针法
int main()
{
	int a[] = {6,1,2,10,7,9,9,3,4,5,10,8};
	int len = sizeof(a) / sizeof(a[0]);
	int size = sizeof(a[0]);
 
	Quick_qsort(a, len, size,Cmp_qsort);//快速排序模拟实现
 
	Print(a, len);//打印
	return 0;
 
}

文章存在借鉴，如有侵权请联系修改删除！文章来源地址https://www.toymoban.com/news/detail-640959.html

到了这里，关于c语言-qsort函数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！