欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++?qsort函數(shù)排序與冒泡模擬實現(xiàn)流程詳解

 更新時間：2022年10月19日 11:35:55   作者：小牛要翻身  
qsort是一個庫函數(shù),基于快速排序算法實現(xiàn)的一個排序的函數(shù),下面這篇文章主要給大家介紹了關于C語言qsort()函數(shù)使用的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下

本章重點：

1.能夠正確的理解qsort函數(shù)各個參數(shù)的含義，并能夠正確的使用qsort函數(shù)進行各類型排序。

2.重點掌握qsort函數(shù)中的參數(shù)cmpar——自定義比較函數(shù)的地址。借此進一步理解回調(diào)函數(shù)。 3.學習以冒泡排序思想模擬實現(xiàn)qsort函數(shù)。

一、qsort排序函數(shù)

1、函數(shù)功能特點

//頭文件:#include<stdlib.h>
void qsort(void* base, size_t num, size_t size,int (*compar)(const void*, const void*));

注：因為qsort可以對任意類型數(shù)據(jù)排序，所以待排數(shù)據(jù)的起始類型可以是任意類型，C語言中可以用void*接收任意類型的地址。

2、函數(shù)參數(shù)

3、比較函數(shù)

qsort之所以可以對任意類型的數(shù)據(jù)排序正是因為傳入的比較函數(shù)是相對自定義的：

對于比較函數(shù) int compar(const void *p1,const void *p2)

（1）比較整數(shù)：

 int compareMyType(const void* p1, const void* p2)
{
	return  *(MyType*)p1 - *(MyType*)p2;
}

1、如果compar返回值小于0（< 0），即*(MyType*)p1 < *(MyType*)p2那么p1所指向元素會被排在p2所指向元素的前面,也就是升序 。

2、如果compar返回值等于0（= 0），即*(MyType*)p1 = *(MyType*)p2那么p1所指向元素與p2所指向元素的順序不確定。

3、如果compar返回值大于0（> 0），即*(MyType*)p1 > *(MyType*)p2那么p1所指向元素會被排在p2所指向元素的后面,也是升序。

所以為了方便理解我們可以簡單這樣認為：對于qsort函數(shù)如果compar函數(shù)的返回值<0(不進行置換)，>0(進行置換)，0(不進行置換)。

即：

return *(MyType*)p1 - *(MyType*)p2;——qsort升序排序

return *(MyType*)p2 - *(MyType*)p1;——qsort降序排序

對于具體qsort函數(shù)內(nèi)部具體是怎么進行置換或排序的我們不必關心。（內(nèi)部實現(xiàn)為快排思想）

（2）比較字符串：

int compareMyType(const void* p1, const void* p2)
{
	return strcmp((MyType *) p1, (MyType *) p2);
}

同理：

return strcmp((MyType*)p1,(MyType*)p2);——qsort升序排序

return strcmp((MyType*)p2,(MyType*)p1);——qsort降序排序

（3）比較結(jié)構(gòu)體

與上述思想類似，比較結(jié)構(gòu)體時需要具體情況具體分析。

4、測試qsort排序

（1）測試qsort函數(shù)排序整形

#include<stdio.h>
#include<stdlib.h>
//輸出函數(shù)
void print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
//比較函數(shù)
int compar(const void* e1, const void* e2)
{
	return *((int*)e1) - *((int*)e2);//升序
	//return *((int*)e2) - *((int*)e1);//降序
}
int main()
{
	int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//arr-數(shù)據(jù)起始地址
	//sz-數(shù)據(jù)元素個數(shù)
	//sizeof(arr[0])-數(shù)據(jù)元素的大小
	//compar-比較函數(shù)指針
	qsort(arr, sz, sizeof(arr[0]), compar);
	print(arr, sz);
	return 0;
}

（2）測試qsort函數(shù)排序結(jié)構(gòu)體

??按年齡排序

#include<stdio.h>
#include<stdlib.h>
//結(jié)構(gòu)體
struct stu
{
	char name[20];
	int age;
};
//(1)按年齡排序
int compar_struct_age(const void* e1, const void* e2)
{
	return ((struct stu*)e1)->age - ((struct stu*)e2)->age;
}
int main()
{
	struct stu s[] = { {"zhangsan",20},{"lisi",55},{"wangwu",40} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), compar_struct_age);
	return 0;
}

??按名字排序

#include<stdio.h>
#include<stdlib.h>
//結(jié)構(gòu)體
struct stu
{
	char name[20];
	int age;
};
//(2)按名字排序
int compar_struct_name(const void* e1, const void* e2)
{
	//使用strcmp比較字符串
	return strcmp(((struct stu*)e1)->name,((struct stu*)e2)->name);
}
int main()
{
	struct stu s[] = { {"zhangsan",20},{"lisi",55},{"wangwu",40} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), compar_struct_name);
	return 0;
}

二、冒泡模擬qusort函數(shù)實現(xiàn)

1、實現(xiàn)思路

理解了庫函數(shù)qsort()的使用后，下面我們來用冒泡排序的思想實現(xiàn)一下qsort函數(shù)，首先我們先回憶一下冒泡排序：

void bubble_sort(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)//冒泡排序趟數(shù)
	{
		int j = 0;
		for (j = 0; j < sz - i - 1; j++)//每趟冒泡排序
		{
			//判斷和交換
			if (arr[j] > arr[j + 1])//升序
			//if (arr[j] < arr[j + 1])降序
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

通過冒泡排序的參數(shù)部分我們就可以看出void bubble_sort(int arr[], int sz)冒泡排序僅支持單一類型的數(shù)據(jù)排序。想要用冒泡排序模擬實現(xiàn)qsort函數(shù)排任意類型數(shù)據(jù)，我們可以仿照qsort函數(shù)參數(shù)對冒泡排序進行改進：

void bubble_sort(void* base, int sz, int width, int (*cmp)(const void*e1, const void*e2))

下面我們只需要將冒泡排序中的判斷和交換部分以qsort思想實現(xiàn)即可。

2、模擬實現(xiàn)

（1）判斷部分

判斷部分我們需要使用傳入的比較函數(shù)指針，利用回調(diào)函數(shù)的機制進行判斷，同時仿照qsort函數(shù)內(nèi)部交換思想即：比較函數(shù)cmp返回值大于零（>0）進行交換：

if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
	{
		//交換
	}

注釋：已知base的類型為void*，這里將void*類型轉(zhuǎn)換為char*類型是一步非常巧妙的過程，因為轉(zhuǎn)換之后我們只需分別加上j*width 和（j+1）*width即可找到相鄰數(shù)據(jù)的起始地址，之后在利用回調(diào)函數(shù)的機制，調(diào)用外部定義的cmp比較函數(shù)，此時cmp實參為（char*)base+ j * width, (char*)base + (j + 1) * width分別為兩相鄰數(shù)據(jù)的起始位置地址，我們已知cmp函數(shù)的形參類型為void*，將得到的起始數(shù)據(jù)位置的指針轉(zhuǎn)換為相應類型的指針再進行比較，即可得到返回值。

（2）交換部分

交換部分我們可以獨立出一個交換函數(shù)-swap()

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++;
	}
}
判斷交換部分
--------------------------------------------------------------------------
if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
	{
		//交換
		swap((char*)base + j * width, (char*)base + (j + 1) * width,width);
	}
--------------------------------------------------------------------------

注釋：對于swap函數(shù)傳入實參，為兩相鄰數(shù)據(jù)的起始地址 與

待排數(shù)據(jù)元素的大小。我們回到qsort函數(shù)的定義：qsort函數(shù)是對數(shù)組元素進行排序。數(shù)組的特點即是，連續(xù)存放的相同類型數(shù)據(jù)。對于相同類型的連續(xù)數(shù)據(jù)也就意味著每個數(shù)據(jù)的大小是相同的，即每個元素占用的字節(jié)大小相同。所以根據(jù)這樣一個特點，我們就可以通過交換相鄰數(shù)據(jù)的每個字節(jié)，以達到交換相鄰數(shù)據(jù)的目的。這樣我們就有了遍歷元素字節(jié)排序的思想：for (i = 0; i < width;i++)

（3）完整代碼與測試

//以冒泡模擬實現(xiàn)qsort
#include<stdio.h>
#include<stdlib.h>
//交換函數(shù)
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++;
	}
}
//冒泡實現(xiàn)
void bubble_qsort_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++)//趟數(shù)
	{
		int j = 0;
		for (j = 0; j < sz - i - 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);
			}
		}
	}
}

這樣我們就完全實現(xiàn)了用冒泡思想模擬實現(xiàn)qsort函數(shù)，并且使用規(guī)則相同，下面我們可以測試一下：

測試整數(shù)

//打印函數(shù)
void print(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}
//比較函數(shù)
int compar(const void* e1, const void* e2)
{
	return *((int*)e1) - *((int*)e2);
}
int main()
{
	int arr[] = { 3,5,2,6,8,1,9,0,4,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_qsort_sort(arr, sz, sizeof(arr[0]), compar);
	print(arr, sz);
	return 0;
}

同樣測試結(jié)構(gòu)體也與庫函數(shù)qsort結(jié)果相同，這里就不在過多測試。

總結(jié)

以上就是對qsort函數(shù)的理解、應用以及模擬實現(xiàn)。相信通過本章對qsort函數(shù)的解剖，你已經(jīng)對qsort函數(shù)有了更深的理解。

到此這篇關于C++ qsort函數(shù)排序與冒泡模擬實現(xiàn)流程詳解的文章就介紹到這了,更多相關C++ qsort函數(shù)排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論