目錄

一.qsort函數(shù)是什么

?二.使用qsort排序-以升序?yàn)槔?/a>

? ? ??關(guān)于void*型指針：

1.整形數(shù)組排序

2.字符數(shù)組排序

3.字符指針數(shù)組排序

4.結(jié)構(gòu)體數(shù)組排序

5.浮點(diǎn)型數(shù)組排序

三.使用冒泡排序思想模擬實(shí)現(xiàn)qsort函數(shù)

1.什么是冒泡排序：

?2.冒泡排序代碼

3.?使用冒泡排序思想模擬實(shí)現(xiàn)qsort函數(shù)

一.qsort函數(shù)是什么

我們可以使用??搜索庫(kù)函數(shù)網(wǎng)址或者M(jìn)SDN軟件進(jìn)行查找。

qsort()函數(shù)：快速排序的函數(shù) ?-引用stdlib.h頭文件

參數(shù)說(shuō)明：
void qsort (?

? ? void* base, //要排序的目標(biāo)數(shù)組
?? ?size_t num,?? ??//待排序的元素個(gè)數(shù)
?? ?size_t width,?? ?//一個(gè)元素的大小，單位是字節(jié)
?? ?int(*cmp)(const void* e1, const void* e2)

);?? ??? ?

其中cmp是函數(shù)指針，cmp指向的是：排序時(shí)，用來(lái)比較兩個(gè)元素的函數(shù)。需要自己編寫(xiě)。

返回值：

????????

?二.使用qsort排序-以升序?yàn)槔?/h2>

---

關(guān)于void*型指針：

??void*：無(wú)具體類(lèi)型的指針???能夠接收任意類(lèi)型的地址
?缺點(diǎn)：不能進(jìn)行運(yùn)算。不能+-整數(shù)，不能解引用

int a  = 0;float f = 5.5f;void* p1 = &a;void* p2 = &f;p1 = p1+1;    //err

1.整形數(shù)組排序

注意：

1.比較函數(shù)的參數(shù)類(lèi)型為void* ，我們要進(jìn)行強(qiáng)制類(lèi)型轉(zhuǎn)換！且要解引用才能得到對(duì)應(yīng)的值！?

2.若我們想排成降序，只需要寫(xiě)成e2-e1即可

void Print(int* arr, int sz){	int i = 0;	for (i = 0; i < sz; i++)	{		printf("%d ", *(arr + i));	}	printf("/n");}//比較整形//注意類(lèi)型時(shí)void* 所以要強(qiáng)制類(lèi)型轉(zhuǎn)化，還要解引用才是對(duì)應(yīng)的值！?。nt cmp_int(const void* e1, const void* e2){	return *(int*)e1 - *(int*)e2;}void test1(){	int arr[] = { 9,8,7,6,7,5,4,8 };	int sz = sizeof(arr) / sizeof(arr[0]);	qsort(arr, sz, sizeof(arr[0]), cmp_int);	Print(arr, sz);}

2.字符數(shù)組排序

注意使用sizeof()操作符和strlen()函數(shù)的區(qū)別

//注意要要強(qiáng)制類(lèi)型轉(zhuǎn)換??！ 要解引用?。?！  本質(zhì)上是比較Ascii值int cmp_char(const void* e1, const void* e2){    return *(char*)e1 - *(char*)e2;}void test4(){	char arr[] ="mango";    //若使用sizeof計(jì)算長(zhǎng)度：	//int sz = sizeof(arr) / sizeof(arr[0]);	//6	//qsort(arr, sz-1, sizeof(arr[0]), cmp_float);    //因?yàn)閟izeof把/0也算進(jìn)去了，所以計(jì)算出來(lái)的值比字符串本身長(zhǎng)度多1        int sz = strlen(arr);	//5    qsort(arr, sz, sizeof(arr[0]), cmp_char);	printf("%s/n",arr);}

3.字符指針數(shù)組排序

先看看下面這段程序有沒(méi)有問(wèn)題？

int cmp_chars(const void* e1, const void* e2){	return strcmp((char*)e1, *(char*)e2);}void test2(){	 char* arr1 = "abc";	 char* arr2 = "wcad";	 char* arr3 = "cab";	 char* p[3] = { arr1,arr2,arr3 };	int sz = sizeof(p) / sizeof(p[0]);	qsort(p, sz, sizeof(p[0]), cmp_chars);	int i = 0;	for (i = 0; i < sz; i++)	{		printf("%s/n", p[i]);	}}

?打印出來(lái)發(fā)現(xiàn)：結(jié)果是錯(cuò)誤的！

?->調(diào)試后發(fā)現(xiàn)：e2存放的是p的地址（char**類(lèi)型），e1存放的是p指向的下一個(gè)元素的地址（char**類(lèi)型）????????

對(duì)于這種寫(xiě)法，傳進(jìn)去的是p的地址，strcmp()會(huì)將p地址對(duì)應(yīng)的內(nèi)容轉(zhuǎn)化成字符串，也就是將p中arr1，arr2，arr3的地址轉(zhuǎn)化成字符串

實(shí)際上應(yīng)該傳p地址空間中arr1，arr2的地址，這樣strcmp()才能找到arr1和arr2對(duì)應(yīng)的字符串，因此得先把e1，e2轉(zhuǎn)化成char**，這樣解引用以后才是一個(gè)char*的地址

原因：把p傳給qsort，p是數(shù)組名->首元素地址，元素類(lèi)型為char*>，所以p的類(lèi)型為：char**類(lèi)型。? 所以e1 和e2也要強(qiáng)制類(lèi)型轉(zhuǎn)化為char**，解引用e1，e2才是對(duì)應(yīng)字符串的地址！

正解：?

int cmp_chars(const void* e1, const void* e2){	return strcmp(*(char**)e1, *(char**)e2);}void test2(){	 char* arr1 = "abc";	 char* arr2 = "wcad";	 char* arr3 = "cab";	 char* p[3] = { arr1,arr2,arr3 };	int sz = sizeof(p) / sizeof(p[0]);	qsort(p, sz, sizeof(p[0]), cmp_chars);	int i = 0;	for (i = 0; i < sz; i++)	{		printf("%s/n", p[i]);	}

4.結(jié)構(gòu)體數(shù)組排序

比較年齡->實(shí)際比較的是整形

比較名字->實(shí)際比較的是字符串->使用strcmp函數(shù)，不能使用 == 判斷

struct Stu{	int age;	char name[20];};//比較結(jié)構(gòu)體中元素的年齡int cmp_age(const void* e1, const void* e2){	//本質(zhì)是比較整形	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;}//比較名字int cmp_name(const void* e1, const void* e2){	//本質(zhì)是字符串比較->使用strcmp函數(shù)	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);}void test2(){	//創(chuàng)建結(jié)構(gòu)體數(shù)組，用大括號(hào)初始化	struct Stu s[3] = { {19,"Mango"},{18,"Lemon"},{20,"Hello"} };	int sz = sizeof(s) / sizeof(s[0]);	//以年齡排	qsort(s, sz, sizeof(s[0]), cmp_age);	printf("%s %d ",s[0].name,s[0].age);	printf("%s %d ", s[1].name, s[1].age);	printf("%s %d ", s[2].name, s[2].age);	printf("/n");	//以姓名排	qsort(s, sz, sizeof(s[0]), cmp_name);	printf("%s %d ", s[0].name, s[0].age);	printf("%s %d ", s[1].name, s[1].age);	printf("%s %d ", s[2].name, s[2].age);	printf("/n");}

5.浮點(diǎn)型數(shù)組排序

注意：比較函數(shù)中，返回類(lèi)型是int，最后相減的值要強(qiáng)制類(lèi)型轉(zhuǎn)化為int ，但這也會(huì)造成錯(cuò)誤，建議使用方法2.

//寫(xiě)法1：可能會(huì)出錯(cuò)// 原因： 0.2 -0.1 = 0.1 強(qiáng)制類(lèi)型轉(zhuǎn)化為int后 結(jié)果為0//int cmp_float(const void* e1, const void* e2)//{//	//返回類(lèi)型是int  所以相減后的結(jié)果要強(qiáng)制類(lèi)型轉(zhuǎn)化//	return (int)(*(float*)e1 - *(float*)e2);//}//寫(xiě)法2：對(duì)應(yīng)上qsort的返回值int cmp_float(const void* e1, const void* e2){	if ((*(float*)e1 - *(float*)e2) > 0.00000)		return 1;	else if ((*(float*)e1 - *(float*)e2) == 0.000000)		return 0;	else		return -1;}void test3(){	float arr[5] = { 5.01f,5.01f,0.02f,0.01f,5.001f };	int sz = sizeof(arr) / sizeof(arr[0]);	qsort(arr, sz, sizeof(arr[0]), cmp_float);	int i = 0;	for (i = 0; i < sz; i++)	{		printf("%f ", arr[i]);	}}

三.使用冒泡排序思想模擬實(shí)現(xiàn)qsort函數(shù)

1.什么是冒泡排序：

主要思想：相鄰的兩個(gè)元素進(jìn)行比較?

?

?對(duì)于冒泡排序：?n個(gè)元素 共進(jìn)行n-1趟冒泡排序。一趟可以使一個(gè)元素在特定位置上，每趟排序可以少比較一個(gè)元素

但是冒泡排序只能排序整形

?2.冒泡排序代碼

void BubbleSort(int* arr, int sz){	int i = 0;	int j = 0;	int flag = 1;//假設(shè)一開(kāi)始有序	//共進(jìn)行sz-1趟	for (i = 0; i < sz-1; i++)	{		// 每一趟		for (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;				flag = 0;			}		}		if (flag == 1)		{			break;		}	}}int main(){	int arr[10] = { 2,3,6,7,9,0,0,3,2,10 };	int sz = sizeof(arr) / sizeof(arr[0]);	BubbleSort(arr, sz);	return 0;}

3.?使用冒泡排序思想模擬實(shí)現(xiàn)qsort函數(shù)

qsort庫(kù)函數(shù)使用的是什么參數(shù)，我們?cè)O(shè)計(jì)的函數(shù)就使用什么參數(shù)！

??

1.為何將base強(qiáng)制類(lèi)型轉(zhuǎn)化為char*型指針：

原因：char* 指針+1跳過(guò)一個(gè)字節(jié)，+width：跳過(guò)width個(gè)字節(jié)，指向下一個(gè)元素。轉(zhuǎn)化為其他類(lèi)型不合適

2.?交換函數(shù)：還要把寬度（每個(gè)元素所占字節(jié)數(shù)）傳過(guò)去
因?yàn)榻粨Q的時(shí)候是傳地址，所以要知道元素的寬度，一個(gè)字節(jié)一個(gè)字節(jié)的交換 ，這樣也證明了使用char*指針的好處！

3.(char*)base + j * width, (char*)base + (j + 1) * width,

? 當(dāng)j = 0時(shí)：比較的是第一個(gè)元素和第二個(gè)元素
? ?j = 1時(shí)，比較的是第二個(gè)元素和第三個(gè)元素
? ? .... ?很妙的寫(xiě)法

//交換 --一個(gè)字節(jié)一個(gè)字節(jié)的交換，共交換width次void Swap(char* buf1, char* buf2, size_t width){	size_t i = 0;	for (i = 0; i < width; i++)	{		char tmp = *buf1;		*buf1 = *buf2;		*buf2 = tmp;		buf1++;		buf2++;	}}void my_BubbleSort(void* base, size_t num,size_t width, int(*cmp)(const void* e1, const void* e2)){	//冒泡排序	//若要排序n個(gè)元素，只需要進(jìn)行n-1趟	//每一趟可以少比較一個(gè)元素，每一趟可以使一個(gè)元素在確定的位置上	//num：要排序元素的個(gè)數(shù) 類(lèi)型是size_t     //num是無(wú)符號(hào)數(shù) 防止產(chǎn)生警告 所以i和j也定義為size_t    // size_t == unsigned int 	size_t i = 0;	size_t j = 0;	//共進(jìn)行num-1趟	for (i = 0; i < num; i++)	{		//每一趟		for (j = 0; j < num - 1 - i; j++)		{			//比較			//傳地址   			//相鄰兩個(gè)元素比較   width:寬度，每個(gè)元素所占字節(jié)			//排成升序			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)			{				//交換兩數(shù)				Swap( (char*)base + j * width, (char*)base + (j + 1) * width, width );			}		}	}}

當(dāng)然 ，交換也可以使用庫(kù)函數(shù)memcpy

dest：目標(biāo)空間?

?src：要拷貝到目標(biāo)空間的字符 -因?yàn)椴蛔餍薷模钥梢杂胏onst修飾

count：字節(jié)數(shù)

char tmp [30];    //防止結(jié)構(gòu)體類(lèi)型之類(lèi)的類(lèi)型    臨時(shí)空間memcpy(tmp, (char*)base + j * size, size); memcpy( (char*)base + j * size,  (char*)base + (j + 1) * size, size);memcpy( (char*)base + (j + 1) * size, tmp, size);

?如果文章對(duì)你有幫助的，歡迎大佬們點(diǎn)個(gè)贊留言呀！如果有錯(cuò)誤的話，請(qǐng)?jiān)u論告知！