C語言中的結(jié)構(gòu)體快排算法

更新時間：2022年11月11日 12:11:52 作者：王睿丶

這篇文章主要介紹了C語言中的結(jié)構(gòu)體快排算法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

C語言結(jié)構(gòu)體快排算法

代碼：

#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為結(jié)構(gòu)體的成員，bb->c也為結(jié)構(gòu)體的成員 
}
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);	//參數(shù)1：結(jié)構(gòu)體數(shù)組名，個數(shù)，首地址的字符數(shù)，自定義比較函數(shù)名 
	for(i=0;i<n;i++)
	printf("%s %s %d\n",stu[i].name,stu[i].xue,stu[i].c);
	return 0;
}

基于結(jié)構(gòu)體數(shù)組的快速排序

用普通的數(shù)組快速排序，改造成任意數(shù)據(jù)的排序，比如結(jié)構(gòu)體數(shù)組、鏈表、棧的排序等。只需要在排序中調(diào)用自己的compare函數(shù)，在其中把想要排序的值做一個比較即可，代碼如下：

#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;//排序結(jié)束 
	}
	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;
}

運行結(jié)果如下：

如果是鏈表的排序，只需要把quicksort函數(shù)的第一個參數(shù)換成鏈表的指針，然后在排序中換成相應獲取鏈表里的數(shù)據(jù)即可。

另外，C語言提供一個庫函數(shù)，已經(jīng)封裝好了快速排序的算法：

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

具體的信息如下：Copy from baidu

參數(shù)base - base指向數(shù)組的起始地址，通常該位置傳入的是一個數(shù)組名
參數(shù)nmemb - nmemb表示該數(shù)組的元素個數(shù)
參數(shù)size - size表示該數(shù)組中每個元素的大?。ㄗ止?jié)數(shù)）
參數(shù)(*compar)(const void *, const void *) - 此為指向比較函數(shù)的函數(shù)指針，決定了排序的順序。

函數(shù)返回值：無

注意：如果兩個元素的值是相同的，那么它們的前后順序是不確定的。也就是說qsort()是一個不穩(wěn)定的排序算法。

compar參數(shù)

compar參數(shù)指向一個比較兩個元素的函數(shù)。比較函數(shù)的原型應該像下面這樣。
注意兩個形參必須是const void *型，同時在調(diào)用compar 函數(shù)（compar實質(zhì)為函數(shù)指針，這里稱它所指向的函數(shù)也為compar）時，
傳入的實參也必須轉(zhuǎn)換成const void *型。在compar函數(shù)內(nèi)部會將const void *型轉(zhuǎn)換成實際類型，見下文。

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函數(shù)可以寫成這樣：

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;
}

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: