Compartir tecnología

Clasificación de burbujas y su código de clasificación de tipo continuo universal en lenguaje C

2024-07-12

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

Clasificación de burbujas y su código de clasificación de tipo continuo universal en lenguaje C

Ordenamiento de burbuja

La clasificación de burbujas es un tipo de clasificación de intercambio:

  1. Idea básica: el llamado intercambio consiste en intercambiar las posiciones de dos registros en la secuencia en función de los resultados de la comparación de los valores clave de los dos registros en la secuencia.
  2. La característica de la clasificación de intercambio es que los registros con valores clave más grandes se mueven al final de la secuencia y los registros con valores clave más pequeños se mueven al principio de la secuencia.

Y ordenar burbujasEn orden ascendenteCada vez que se recorre, la colección sin clasificar seráLos valores más grandes se mueven hacia atrás.(o mueva los pequeños al frente) hasta que estén ordenados.

Visualización de animación:

Insertar descripción de la imagen aquí

Resumen de características del tipo de burbuja:

  1. La clasificación de burbujas es una clasificación muy fácil de entender.
  2. Complejidad del tiempo: O (N ^ 2)
  3. Complejidad espacial: O (1)
  4. Estabilidad: estable

Código de referencia de datos enteros de clasificación de burbujas (configuración regional 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

Clasificación de burbujas Código de clasificación de tipo continuo general en lenguaje C

El código de clasificación de burbujas en lenguaje C anterior solo admite la clasificación de números enteros. Aquí se extiende a.Clasificación secuencial genéricacódigo.

Consulte la clasificación qsort incorporada en lenguaje C:
Insertar descripción de la imagen aquí

La función se puede obtener como:
Insertar descripción de la imagen aquí

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

De hecho, sólo necesitamosDos de sus lugares han sido modificados significativamente., puede obtener una clasificación general:

Cambios en la forma en que se realizan las comparaciones:

Cambie el método de comparación apuntero de funciónmanera, para que los usuarios puedanEscribe tu propia función de tipo de comparación(No solo incluye los tipos integrados, sino también los definidos por estructura, pero la premisa escontinuamente）
Insertar descripción de la imagen aquí

Insertar descripción de la imagen aquí
Si el usuario clasifica números enteros, la comparación escrita por él mismo es (solo como referencia, el método no es ú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

Cambios en la forma en que se realizan los intercambios:

Aquí solo necesita cambiar el método de intercambio a un intercambio byte por byte.
Insertar descripción de la imagen aquí
Insertar descripción de la imagen aquí
Entonces el intercambio debería cambiarse a:

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

Verificación de resultados:

Tipos incorporados:

Insertar descripción de la imagen aquí
Insertar descripción de la imagen aquí

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:

Insertar descripción de la imagen aquí

Insertar descripción de la imagen aquí
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

Aviso:

El código anteriorNo válido para datos discontinuos, como por ejemplo cada elemento de la lista enlazada esalmacenado por conexión de puntero, la función de comparación y la función de intercambio deben cambiarse para resolverlo.

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi informacion de contacto

Correo