Compartilhamento de tecnologia

Classificação por bolha e seu código de classificação de tipo contínuo universal em linguagem C

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Classificação por bolha e seu código de classificação de tipo contínuo universal em linguagem C

Tipo de bolha

A classificação por bolha é um tipo de classificação por troca:

  1. Ideia básica: A chamada troca é trocar as posições dos dois registros na sequência com base nos resultados da comparação dos valores-chave dos dois registros na sequência.
  2. A característica da classificação por troca é que os registros com valores-chave maiores são movidos para o final da sequência e os registros com valores-chave menores são movidos para o início da sequência.

E tipo de bolhaEm ordem ascendenteCada vez que for percorrido, a coleção não classificada seráValores maiores são movidos para trás(ou mova os pequenos para a frente) até classificar.

Exibição de animação:

Insira a descrição da imagem aqui

Resumo dos recursos da classificação por bolha:

  1. A classificação por bolha é uma classificação muito fácil de entender
  2. Complexidade de tempo: O(N^2)
  3. Complexidade do espaço: O(1)
  4. Estabilidade: estável

Código de referência de dados inteiros de classificação de bolhas (localidade VS2022C):

#include <stdio.h>
#include <stdbool.h>

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//			要排序的数组	 数组大小
int bubbleSort(int* arr, int sz)
{
	// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
	for (int i = 0; i < sz - 1; ++i)
	{
		bool flag = true;						// 3.检查是否有序

		// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
		for (int j = 0; j < sz - 1 - i; ++j)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = false;					// 3.表示无序
				swap(&arr[j], &arr[j + 1]);
			}
		}

		if (flag == true)						// 3.有序直接退出循环
		{
			break;
		}
	}
}

int main()
{
	int arr[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };
	int sz = 10;

	bubbleSort(arr, sz);
	for (int i = 0; i < sz; ++i)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

Código de classificação geral de tipo contínuo em linguagem C de classificação por bolha

O código de classificação por bolha da linguagem C acima suporta apenas classificação de números inteiros. Aqui ele é estendido para.Classificação sequencial genéricacódigo.

Consulte a classificação qsort integrada na linguagem C:
Insira a descrição da imagem aqui

A função pode ser obtida como:
Insira a descrição da imagem aqui

void swap(char* a, char* b, size_t width)
{
	for (int i = 0; i < width; ++i)
	{
		char temp = *(a + i);
		*(a + i) = *(b + i);
		*(b + i) = temp;
	}
}

//			要排序的数组	   数组大小	   每个元素宽度		比较的函数指针
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{
	// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
	for (int i = 0; i < sz - 1; ++i)
	{
		bool flag = true;						// 3.检查是否有序

		// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
		for (int j = 0; j < sz - 1 - i; ++j)
		{
			if (compare((char*)base + j * width, (char*)base + j * width + width) > 0)
			{
				flag = false;					// 3.表示无序
				swap((char*)base + j * width, (char*)base + j * width + width, width);
			}
		}

		if (flag == true)						// 3.有序直接退出循环
		{
			break;
		}
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

Na verdade, só precisamosDois de seus locais foram significativamente alterados, você pode obter uma classificação geral:

Mudanças na forma como as comparações são feitas:

Altere o método de comparação paraponteiro de funçãomaneira, para que os usuários possamEscreva sua própria função de tipo de comparação(Não inclui apenas tipos integrados, mas também aqueles definidos por struct, mas a premissa écontinuamente）
Insira a descrição da imagem aqui

Insira a descrição da imagem aqui
Se o usuário classificar inteiros, a comparação escrita por ele mesmo será (apenas para referência, o método não é único):

int cmp(const void* e1, const void* e2)
{
	// (int*)e1 表示将泛型指针转为整型指针
	// *((int*)e1) 表示对整型指针解引用从而得到整型的数 
	// 两整型的数相减，为正则e1大，为负则e2大，为0则相等
	return *((int*)e1) - *((int*)e2);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

Mudanças na forma como as trocas são feitas:

Aqui você só precisa alterar o método de troca para uma troca byte por byte.
Insira a descrição da imagem aqui
Insira a descrição da imagem aqui
Então swap deve ser alterado para:

void swap(char* a, char* b, size_t width)
{
	// a 和 b 表示两个数开始的地址
	// a + i 表示 a 元素第 i 块字节的地址，同理于b
	// *(a + i) 表示 a 元素第 i 块字节的内容，同理于b
	// 通过一个字节一个字节的交换，确保内容不会丢失
	for (int i = 0; i < width; ++i)
	{
		char temp = *(a + i);
		*(a + i) = *(b + i);
		*(b + i) = temp;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

Verificação do resultado:

Tipos integrados:

Insira a descrição da imagem aqui
Insira a descrição da imagem aqui

Código completo:

#include <stdio.h>
#include <stdbool.h>

void swap(char* a, char* b, size_t width)
{
	for (int i = 0; i < width; ++i)
	{
		char temp = *(a + i);
		*(a + i) = *(b + i);
		*(b + i) = temp;
	}
}

//			要排序的数组	   数组大小	   每个元素宽度		比较的函数指针
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{
	// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
	for (int i = 0; i < sz - 1; ++i)
	{
		bool flag = true;						// 3.检查是否有序

		// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
		for (int j = 0; j < sz - 1 - i; ++j)
		{
			if (compare((char*)base + j * width, (char*)base + j * width + width) > 0)
			{
				flag = false;					// 3.表示无序
				swap((char*)base + j * width, (char*)base + j * width + width, width);
			}
		}

		if (flag == true)						// 3.有序直接退出循环
		{
			break;
		}
	}
}

int cmp(const void* e1, const void* e2)			// 对整形
{
	return *((int*)e1) - *((int*)e2);
}

int cmp1(const void* e1, const void* e2)		// 对字符
{
	return *((char*)e1) - *((char*)e2);
}

int cmp2(const void* e1, const void* e2)		// 对浮点
{
	double num1 = *(double*)e1;
	double num2 = *(double*)e2;

	// double 返回与 int 冲突会影响，只需更改一下返回逻辑
	return num1 > num2 ? 1 : -1;
}

int main()
{
	int arr[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };
	int sz = 10;

	bubbleSort(arr, sz, sizeof(int), cmp);
	for (int i = 0; i < sz; ++i)
	{
		printf("%d ", arr[i]);
	}
	printf("n");

	char arr1[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };

	double arr2[10] = { 3.1, 9.4, 2.9, 7.8, 8.8, 5.1, 6.2, 1.0, 10.1, 4.4 };

	bubbleSort(arr1, sz, sizeof(char), cmp1);

	bubbleSort(arr2, sz, sizeof(double), cmp2);

	for (int i = 0; i < sz; ++i)
	{
		printf("%d ", arr1[i]);
	}
	printf("n");

	for (int i = 0; i < sz; ++i)
	{
		printf("%.2lf ", arr2[i]);
	}
	printf("n");

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91

Tipo personalizado:

Insira a descrição da imagem aqui

Insira a descrição da imagem aqui
Código completo:

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

void swap(char* a, char* b, size_t width)
{
	for (int i = 0; i < width; ++i)
	{
		char temp = *(a + i);
		*(a + i) = *(b + i);
		*(b + i) = temp;
	}
}

//			要排序的数组	   数组大小	   每个元素宽度		比较的函数指针
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{
	// 1.n个数中，每次交换前需要比较两个数字，则比较次数为n - 1
	for (int i = 0; i < sz - 1; ++i)
	{
		bool flag = true;						// 3.检查是否有序

		// 2.在 “1.” 的基础之上，i每循环一次，必定有一个数排好到后面，则 “- i" 来优化
		for (int j = 0; j < sz - 1 - i; ++j)
		{
			if (compare((char*)base + j * width, (char*)base + j * width + width) > 0)
			{
				flag = false;					// 3.表示无序
				swap((char*)base + j * width, (char*)base + j * width + width, width);
			}
		}

		if (flag == true)						// 3.有序直接退出循环
		{
			break;
		}
	}
}

typedef struct Student
{
	char name[20];
	int age;
	char id[10];
} Student;

int cmpAge(const void* e1, const void* e2)
{
	return ((Student*)e1)->age - ((Student*)e2)->age;
}

int cmpId(const void* e1, const void* e2)
{
	return strcmp(((Student*)e1)->id, ((Student*)e2)->id);
}

int main()
{
	Student arr[5] = {
		{.name = "张三", .age = 20, .id = "1" },
		{.name = "李四", .age = 21, .id = "2" },
		{.name = "王二", .age = 18, .id = "3" },
		{.name = "麻子", .age = 30, .id = "4" } };
	
	int sz = 4;

	bubbleSort(arr, sz, sizeof(Student), cmpAge);

	printf("以年龄排序：n");
	for (int i = 0; i < sz; ++i)
	{
		printf("%s ", arr[i].name);
		printf("%d ", arr[i].age);
		printf("%sn", arr[i].id);
	}
	printf("n");

	bubbleSort(arr, sz, sizeof(Student), cmpId);

	printf("以ID排序：n");
	for (int i = 0; i < sz; ++i)
	{
		printf("%s ", arr[i].name);
		printf("%d ", arr[i].age);
		printf("%sn", arr[i].id);
	}
	printf("n");

	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

Perceber:

O código acimaInválido para dados descontínuos, como cada elemento da lista vinculada éarmazenado por conexão de ponteiro, a função de comparação e a função de troca precisam ser alteradas para resolver.

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência