【 pointeur avancé Ⅲ】 mise en œuvre de la fonction de tri rapide qsort＆ fonction de rappel en langage C

0. Algorithme classique de tri rapide-Quick_sort

Commencez par la mise en œuvre manuelleQuick_sort Trier les fonctions

#include<stdio.h>
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	int meeti = left;
	Swap(&arr[keyi], &arr[meeti]);

	Quick_sort(arr, begin, meeti-1);
	Quick_sort(arr, meeti+1, end);
	
}

void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", arr[i]);
	}
}

int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Quick_sort(arr, 0,sz-1);
	Print(arr, sz);
	return 0;
}

Trier les résultats：

 

 

Mais il y a un problème.: Si la prochaine fois je veux trier une structure , Mes modifications à cet algorithme de tri seront très importantes （ Il y a des changements presque partout ）, Ci - dessous, je donne également l'implémentation du code correspondant à la structure de tri , Je vais vous montrer .

#include<stdio.h>
#include<string.h>
typedef struct stu
{
	char name[20];
	int age;
}stu;

void Swap(stu* a,stu* b)
{
	stu temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(stu* ps, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && strcmp(ps[right].name, ps[keyi].name) >= 0)
		{
			right--;
		}
		while (left < right && strcmp(ps[left].name, ps[keyi].name) <= 0)
		{
			left++;
		}
		Swap(&ps[left], &ps[right]);
	}
	int meeti = left;
	Swap(&ps[keyi], &ps[meeti]);

	Quick_sort(ps, begin, meeti - 1);
	Quick_sort(ps, meeti+1, end);
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}

int main()
{
	stu s[3] = { {"Zhang San",18},{"Li - si.",20},{"Wang Wu",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	Quick_sort(s,0,sz-1);
	Print(s, sz);
	return 0;
}

Trier les résultats：

 

  C'est pourquoi nous avons pensé ： Peut - on concevoir une fonction permettant d'ajouter une fonction de tri lors du tri d'éléments de différents types de données Quick_sortRéutilisation du Code,Donc,,Fonctions de bibliothèqueqsortC'est arrivé. , À quoi ressemble cette fonction ？

1. qsort Introduction de base aux fonctions de tri

qsort La fonction de tri est C Fonctions dans la Bibliothèque des normes linguistiques , Le principe de réalisation est un algorithme de tri rapide ,Le prototype de fonction est le suivant:

 qsort Introduction et signification des paramètres pertinents de la fonction :

• Fichier d 'en - tête: #include<stdlib.h>
• Valeur de retour: Aucune
• void  base: Adresse de départ de l'élément de données à trier
• size_t num:  Nombre d'éléments de données à trier
• size_t width: Taille des éléments de données à trier ,En octets
• int( * cmp)(const void*,const void*): Pointeur de fonction- Fonction pour comparer la taille des éléments de données ,Trier par

Par exemple,: 

#include<stdio.h>
#include<stdlib.h>
//Parqsort Par exemple, la fonction bibliothèque implémente le tri de tableau entier 
int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp);
	//arr:Nom du tableau,C'est aussi l'adresse du premier élément du tableau, Numériquement égal à 4 L'adresse de l'octet avec l'adresse la plus basse parmi les octets 
	//sz:TableauarrNombre d'éléments pour
	//sizeof(arr[0]): Nombre d'octets par élément de tableau 
	//cmp_int:Fonction de rappel- Comparer les fonctions des éléments du tableau , Auto - implémenter selon les besoins de l'appelant 
	Print(arr, sz);
	return 0;
}

Laisse tomber. qsort La mise en œuvre concrète de la fonction n'est pas ,Regarde ça.,Tu le savais.qsort La flexibilité de la fonction réside dans le quatrième paramètre （Fonction de comparaison） Peut être conçu en fonction des exigences de tri spécifiques de l'utilisateur .

2. Fonction de comparaison

Exemple de conception d'une fonction de comparaison ：Tableau entier, Tableau des structures, etc

Tri des tableaux entiers：（Tous les codes）

S'inquiéter de voir les relations d'appel entre les fonctions ： Je vais vous donner une image pour comprendre

 

#include<stdio.h>
#include<stdlib.h>

int cmp_int(const void* e1, const void* e2)
{
    // Comparer deux éléments entiers 
	//void*Est un pointeur sans type spécifique
	//void* Le pointeur peut recevoir n'importe quel type d'adresse , Comme une poubelle 
	//void* Le pointeur pour n'a pas de type spécifique ,Je ne peux pas+1-1( Parce que je ne sais pas combien )

	//Ordre croissant:
	return *(int*)e1 - *(int*)e2;

	//Ordre décroissant:
	//return *(int*)e2 - *(int*)e1;
}


void Print(int* arr, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%d\t", arr[i]);
	}
}

void test1()
{
	int arr[6] = { 14,35,4,42,6,12 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(&arr[0], sz, sizeof(arr[0]), cmp_int);
	Print(arr, sz);
}


int main()
{
	test1();

	return 0;
}

Parce quevoidPointeur de type vide：

• Peut recevoir n'importe quel type de pointeur
• Impossible d'ajouter ou de soustraire des entiers directement , Un virage fort est nécessaire avant utilisation  

Parce quecmp La fonction de comparaison doit être conçue par l'utilisateur , Donc pour les différents utilisateurs qsort La fonction passe à cmp Le type d'argument d'une fonction peut être n'importe quel type de pointeur ,Donc, danscmp Pour comparer les fonctions void*Pointeur de type pour recevoir,Il suffit devoid* Le pointeur de type fait un virage fort correspondant .

Trier les résultats：

 

 

Tri des tableaux de structure：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct stu
{
	char name[20];
	int age;
}stu;

int cmp_struct_by_name(const void* e1, const void* e2)
{
	return strcmp(((stu*)e1)->name, ((stu*)e2)->name);// C'est merveilleux 
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}


void test2()
{
	stu s[3] = { {"zhangsan",18},{"lisi",20},{"wangwu",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s,sz,sizeof(s[0]),cmp_struct_by_name);
	Print(s, sz);
}

int main()
{
	test2();

	return 0;
}

Trier les résultats：

Pour comparer les chaînesstrcmpFonctions,Fichier d 'en - tête#include<string.h> 

• C'est merveilleux ：strcmp Comparer les fonctions avec les cmp La valeur de retour de la fonction de comparaison a le même sens
• Valeur de retour>0             elem1>elem2
• Valeur de retour==0           elem1==elem2
• Valeur de retour<0             elem1<elem2

 2. qsortMise en œuvre concrète de la fonction

ApprendreqsortMise en œuvre concrète de la fonction, Vous apprendrez ceci C Un autre excellent endroit pour les fonctions de bibliothèque de langues .

void Swap(char* buff1,char* buff2,int width)
{
	if (buff1 != buff2)
	{
		//way1
		//while (width--)
		//{
		//	char temp = *buff1;
		//	*buff1 = *buff2;
		//	*buff2 = temp;
		//	buff1++;
		//	buff2++;
		
		//way2
		for (int i = 0; i < width; i++)
		{
			char temp = *(buff1+i);
	        *(buff1+i) = *(buff2+i);
	        *(buff2+i) = temp;
		}
	}
}

void bubble_sort(void* base, int sz, int width, int(*cmp)(const void*, const void*))
{
	int flag = 1;
	//Nombre de voyages
	for (int i = 0; i < sz-1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (cmp_struct_by_name((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;
	}
}

L'astuce est de mettre les paramètres réels void* TypebasePointeur fort àchar*Type.

Analogiesint arr[5]={34,5,35,62,1};
Print(arr,5),Ici.arr En fait, c'est l'adresse du premier élément , Numériquement et en premier élément 4 L'adresse de l'octet le plus bas des octets est la même ,Alors...cmp Les arguments de la fonction sont même char* Une adresse octet ,Incmp La fonction peut également être forcée au type désiré ,Faire une référence, Obtenez le nombre d'octets correspondant pour la comparaison , C'est comme ça que bubble_sort On obtient l'unité dans la fonction , Donc, peu importe le type de données que nous devons trier ,Peut être appelé directementbubble_sortFonctions,Il suffit de changercmpFonction,Ça augmente.bubble_sort Réutilisabilité du Code de fonction .