快捷導(dǎo)航

C語言庫函數(shù)qsort的使用及模擬實(shí)現(xiàn)

更新時(shí)間：2022年08月18日 15:44:51 作者：敲代碼の流川楓

這篇文章主要介紹了C語言庫函數(shù)qsort的使用及模擬實(shí)現(xiàn)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下

1.qsort函數(shù)的介紹

函數(shù)定義：

函數(shù)參數(shù) ：

void* base

待排序的數(shù)據(jù)的起始位置

size_t num

待排序的數(shù)據(jù)元素的個(gè)數(shù)

size_t width

待排序的數(shù)據(jù)元素的大小，以字節(jié)為單位

int (*compar)(const void*,const void*)

是一個(gè)函數(shù)指針，函數(shù)功能是比較

因該排序算法要排序的數(shù)據(jù)的類型是不同的，比較方法也是有差異的，因此要給使用者提供一個(gè)自定義一個(gè)比較函數(shù)

2.qsort實(shí)現(xiàn)不同類型數(shù)據(jù)排序

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}
void test1()
{
 
	int arr[] = {9，8，7，6，5，4，3，2，1，0};
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
struct Stu
{
	char name[20];
	int age;
};
 
int cmp_stu_by_name(const void* e1, const* e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}
 
void test2()
{
	struct Stu s[] = { {"zhangsan",20},{"lisi",21},"wangwu",19};
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
		printf("%s %d ", s[i].name, s[i].age);
	}
}
int main()
{
	test1();
    prinf("\n");
	test2();
	return 0;
}

test1和test2兩個(gè)函數(shù)分別對int類型數(shù)據(jù)和結(jié)構(gòu)體類型數(shù)據(jù)進(jìn)行排序，這里void*值得一提

void*指針的作用:

int main()
{
	int a = 10;
	char* pa = &a;
	return 0;
}

如警告所說，他們的類型是不兼容的，但如果用void*定義一個(gè)指針變量來接收int*數(shù)據(jù)就不會(huì)有警告，這說明void*指針是無具體類型的指針，可以接受任意類型的地址，是泛型的，也正因?yàn)樗鼪]有具體的類型，它不能解引用，也不能加減操作，想要對它解引用，只需要對地址強(qiáng)制類型轉(zhuǎn)換即可，qsort的函數(shù)參數(shù)使用void*類型也是因?yàn)椴恢朗褂谜呔唧w會(huì)傳什么類型的數(shù)據(jù)的地址，用void*可以接收任意類型的地址，提高了qsort函數(shù)的實(shí)用性

3.qsort的模擬實(shí)現(xiàn)

分析：

參考qsort函數(shù)的參數(shù)我們知道：在設(shè)計(jì)函數(shù)的時(shí)候我們是不知道使用者要傳什么類型的數(shù)據(jù)，因此會(huì)使用到void*型的指針來記錄排序數(shù)據(jù)的起始位置，最后提供的一個(gè)比較函數(shù)也會(huì)用到void*；知道了元素個(gè)數(shù)和元素寬度，就能一一找到這些數(shù)據(jù)

如上圖所示， base被強(qiáng)制類型轉(zhuǎn)換為char*型指針后一次可以訪問一個(gè)字節(jié)，如果轉(zhuǎn)換為int *后一次跳過4個(gè)字節(jié)就太多了，轉(zhuǎn)換為char*后結(jié)合width相當(dāng)于通過起始位置加上偏移量的方法來比較，比較后通過Swap函數(shù)進(jìn)行交換，達(dá)到排序的目的

模擬實(shí)現(xiàn)：

//交換
void Swap(char* buf1, char* buf2, int width)
{
	int i = 0;
	for (i = 0; i < width; i++)
	{
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
        //一趟排序
		int flag = 1;
		int j = 0;
		for (j = 0; j < sz - 1; j++)
		{
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width)>0)
			{
				Swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
				flag = 0;
			}
		}
		if (flag == 1)
			break;
	}
}

int cmp_int(const void* e1, const void* e2)
{
	return (*(int*)e1 - *(int*)e2);
}
void test1()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
struct Stu
{
	char name[20];
	int age;
};

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

void test2()
{
	struct Stu s[] = { {"zhangsan",20},{"lisi",21},"wangwu",19};
	int sz = sizeof(s) / sizeof(s[0]);
	 bubble_sort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	int i = 0;
	for (i = 0; i < 3; i++)
	{
		printf("%s %d ", s[i].name, s[i].age);
	}
}
int main()
{

	test1();
	printf("\n");
	test2();

	return 0;
}