C语言中的结构体快排算法

C语言结构体快排算法代码: include include include struct Stu

C语言结构体快排算法

代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Stu{
	char name[100];	//名字 
	char xue[100];	//学号 
	int c;			//成绩 
}stu[10010];
int comp(const void* a,const void* b)
{
	struct Stu *aa = (struct Stu *)a;
	struct Stu *bb = (struct Stu *)b;
	return ((aa->c)-(bb->c));		//aa->c为结构体的成员,bb->c也为结构体的成员 
}
int main()
{
	int n;
	int i,j;
	scanf("%d",&n);
	getchar();
	for(i=0;i<n;i++)
	{
		scanf("%s%s%d",&stu[i].name,&stu[i].xue,&stu[i].c);
	}
	printf("\n");
	qsort(stu,n,sizeof(stu[0]),comp);	//参数1:结构体数组名,个数,首地址的字符数,自定义比较函数名 
	for(i=0;i<n;i++)
	printf("%s %s %d\n",stu[i].name,stu[i].xue,stu[i].c);
	return 0;
}

基于结构体数组的快速排序

用普通的数组快速排序,改造成任意数据的排序,比如结构体数组、链表、栈的排序等。只需要在排序中调用自己的compare函数,在其中把想要排序的值做一个比较即可,代码如下:

#include <stdio.h>
#include <strings.h>

typedef int (*Z_COMPARE)(void* obj1, int obj1size, void* obj2, int obj2size);
typedef struct
{
	char name[20];
	char brief_name[20];
	char desc[20];
}ROOM_INFO;

int room_info_cmp(void* obj1, int obj1size, void* obj2, int obj2size)
{
	ROOM_INFO* item1 = (ROOM_INFO*)obj1;
	ROOM_INFO* item2 = (ROOM_INFO*)obj2;
	
	if(atoi(item1->brief_name) < atoi(item2->brief_name))
	{
		return 1;
	}
	else if(atoi(item1->brief_name) > atoi(item2->brief_name))
	{
		return 0;
	}
	return -1;
}

int quicksort(ROOM_INFO* room_info, int left, int right, Z_COMPARE cmp)
{
	ROOM_INFO tmp = {0};
	ROOM_INFO f = {0};
	int rtemp,ltemp;
	
	ltemp = left;
	rtemp = right;
	if(ltemp >= rtemp)
	{
		return 0;//排序结束 
	}
	memcpy(&f, &room_info[left], sizeof(ROOM_INFO));//保存基准值
	
	while(ltemp < rtemp)
	{
		while(cmp(&room_info[rtemp], sizeof(ROOM_INFO), &f, sizeof(ROOM_INFO)) == 0 && ltemp < rtemp)
		{
			--rtemp;
		}
		if(ltemp != rtemp)
		{
			memcpy(&room_info[ltemp], &room_info[rtemp], sizeof(ROOM_INFO));
			ltemp++;
		}
		while(cmp(&room_info[ltemp], sizeof(ROOM_INFO), &f, sizeof(ROOM_INFO)) == 1 && ltemp < rtemp)
		{
			++ltemp;
		}
		if(ltemp != rtemp)
		{
			memcpy(&room_info[rtemp], &room_info[ltemp], sizeof(ROOM_INFO));
			rtemp--;
		}
	}
	memcpy(&room_info[ltemp], &f, sizeof(ROOM_INFO));

	if(left < rtemp)
	{
		quicksort(room_info, left, ltemp-1, cmp);
	}
	if(ltemp < right)
	{
		quicksort(room_info, rtemp+1, right, cmp);
	}
	return 0;
}

int main()
{
	ROOM_INFO room_info[10] = {0};
	int i = 0;
	srand(time(NULL));
	for(i = 0; i < 10; i++)
	{
		snprintf(room_info[i].brief_name, sizeof(room_info[i].brief_name), "%d", rand()%100);
	}
	
	for(i = 0; i < 10; i++)
	{
		printf("111111,room_info[%d].brief_name=%s\n",i, room_info[i].brief_name);
	}
	printf("\n\n"); 
	quicksort(room_info, 0, 9, room_info_cmp);
	for(i = 0; i < 10; i++)
	{
		printf("222222,room_info[%d].brief_name=%s\n",i, room_info[i].brief_name);
	}
	return 0;
}

运行结果如下:

如果是链表的排序,只需要把quicksort函数的第一个参数换成链表的指针,然后在排序中换成相应获取链表里的数据即可。

另外,C语言提供一个库函数,已经封装好了快速排序的算法:

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

具体的信息如下:Copy from baidu

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

函数返回值:无

注意:如果两个元素的值是相同的,那么它们的前后顺序是不确定的。也就是说qsort()是一个不稳定的排序算法。

compar参数

  • compar参数指向一个比较两个元素的函数。比较函数的原型应该像下面这样。
  • 注意两个形参必须是const void *型,同时在调用compar 函数(compar实质为函数指针,这里称它所指向的函数也为compar)时,
  • 传入的实参也必须转换成const void *型。在compar函数内部会将const void *型转换成实际类型,见下文。

int compar(const void *p1, const void *p2);

  • 如果compar返回值小于0(< 0),那么p1所指向元素会被排在p2所指向元素的前面
  • 如果compar返回值等于0(= 0),那么p1所指向元素与p2所指向元素的顺序不确定
  • 如果compar返回值大于0(> 0),那么p1所指向元素会被排在p2所指向元素的后面

因此,如果想让qsort()进行从小到大(升序)排序,那么一个上面的compar函数可以写成这样:

int room_info_cmp(void* obj1, void* obj2)
{
	ROOM_INFO* item1 = (ROOM_INFO*)obj1;
	ROOM_INFO* item2 = (ROOM_INFO*)obj2;
	
	if(atoi(item1->brief_name) < atoi(item2->brief_name))
	{
		return -1;
	}
	else if(atoi(item1->brief_name) > atoi(item2->brief_name))
	{
		return 1;
	}
	return 0;
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持好代码网。

您可能有感兴趣的文章
C和C++的区别详解

浅谈C结构和C++结构之间的区别

c语言颜色代码详解

C语言三种函数调用约定

C语言指针用法总结