Teknologian jakaminen

Kuplalajittelu ja sen C-kielen yleinen jatkuvatyyppinen lajittelukoodi

2024-07-12

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

Kuplalajittelu ja sen C-kielen yleinen jatkuvatyyppinen lajittelukoodi

Kuplalajittelu

Kuplalajittelu on eräänlainen vaihtolajittelu:

  1. Perusidea: Ns. vaihto on vaihtaa kahden tietueen paikkaa sarjassa perustuen sekvenssin kahden tietueen avainarvojen vertailutuloksiin.
  2. Vaihtolajittelulle on ominaista, että tietueet, joilla on suurempi avainarvo, siirretään sekvenssin loppuun ja tietueet, joilla on pienempi avainarvo, siirretään sekvenssin etupuolelle.

Ja kuplatyyppiäNousevassa järjestyksessäLajittelematon kokoelma on aina, kun se kuljetetaanSuuremmat arvot siirretään taakse(tai siirrä pienet eteen), kunnes ne on lajiteltu.

Animaationäyttö:

Lisää kuvan kuvaus tähän

Yhteenveto kuplalajittelun ominaisuuksista:

  1. Kuplalajittelu on erittäin helposti ymmärrettävä lajittelu
  2. Aika monimutkaisuus: O(N^2)
  3. Avaruuden monimutkaisuus: O(1)
  4. Vakaus: vakaa

Kuplalajittelun kokonaislukutietojen viitekoodi (VS2022C-kieli):

#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

Kuplalajittelu C-kielen yleinen jatkuva lajittelukoodi

Yllä oleva C-kielen kuplalajittelukoodi tukee vain kokonaislukulajitteluaYleinen peräkkäinen lajittelukoodi.

Katso sisäänrakennettu qsort-lajittelu C-kielellä:
Lisää kuvan kuvaus tähän

Funktio voidaan saada seuraavasti:
Lisää kuvan kuvaus tähän

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

Itse asiassa meidän tarvitsee vainKaksi sen paikkaa on muuttunut merkittävästi, voit saada yleisen lajittelun:

Muutoksia vertailujen tekemiseen:

Vaihda vertailumenetelmäksitoimintoosoitintavalla, jotta käyttäjät voivatKirjoita oma vertailutyyppifunktiosi(Ei vain sisällä sisäänrakennettuja tyyppejä, vaan myös structin määrittelemiä, mutta lähtökohta onjatkuvasti）
Lisää kuvan kuvaus tähän

Lisää kuvan kuvaus tähän
Jos käyttäjä lajittelee kokonaislukuja, hänen kirjoittamansa vertailu on (vain viitteeksi, menetelmä ei ole ainutlaatuinen):

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

Muutoksia tapaan, jolla vaihto tapahtuu:

Tässä sinun tarvitsee vain vaihtaa vaihtotapa tavu kerrallaan.
Lisää kuvan kuvaus tähän
Lisää kuvan kuvaus tähän
Sitten swap tulee vaihtaa muotoon:

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

Tulosten vahvistus:

Sisäänrakennetut tyypit:

Lisää kuvan kuvaus tähän
Lisää kuvan kuvaus tähän

Täydellinen koodi:

#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

Mukautettu tyyppi:

Lisää kuvan kuvaus tähän

Lisää kuvan kuvaus tähän
Täydellinen koodi:

#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

Ilmoitus:

Yllä oleva koodiVirheellinen epäjatkuville tiedoille, kuten linkitetyn luettelon jokainen elementti ontallennettu osoitinyhteydellä, vertaa toimintoa ja vaihtotoimintoa on muutettava ratkaistaksesi.

Henkilökohtainen profiili

Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin alalla Kehittäjän dokumentaatioasema, jossa voit jakaa joitakin teknologian kehittämisen ongelmia myöhempää käyttöä varten

yhteystietoni

Mail