Κοινή χρήση τεχνολογίας

Ταξινόμηση με φυσαλίδες και ο γενικός κώδικας ταξινόμησης συνεχούς τύπου της γλώσσας C

2024-07-12

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

Ταξινόμηση με φυσαλίδες και ο γενικός κώδικας ταξινόμησης συνεχούς τύπου της γλώσσας C

Ταξινόμηση με φυσαλίδες

Η ταξινόμηση με φυσαλίδες είναι ένας τύπος ταξινόμησης ανταλλαγής:

  1. Βασική ιδέα: Η λεγόμενη ανταλλαγή είναι η ανταλλαγή των θέσεων των δύο εγγραφών στην ακολουθία με βάση τα αποτελέσματα σύγκρισης των βασικών τιμών των δύο εγγραφών στην ακολουθία.
  2. Το χαρακτηριστικό της ταξινόμησης ανταλλαγής είναι ότι οι εγγραφές με μεγαλύτερες τιμές κλειδιών μετακινούνται στο τέλος της ακολουθίας και οι εγγραφές με μικρότερες τιμές κλειδιών μετακινούνται στο μπροστινό μέρος της ακολουθίας.

Και είδος φούσκαςΜε αύξουσα σειράΚάθε φορά που διασχίζεται, θα είναι η μη ταξινομημένη συλλογήΟι μεγαλύτερες τιμές μετακινούνται προς τα πίσω(ή μετακινήστε τα μικρά στο μπροστινό μέρος) μέχρι να ταξινομηθούν.

Εμφάνιση κινούμενων σχεδίων:

Εισαγάγετε την περιγραφή της εικόνας εδώ

Σύνοψη χαρακτηριστικών της ταξινόμησης με φυσαλίδες:

  1. Η ταξινόμηση με φυσαλίδες είναι μια πολύ εύκολα κατανοητή ταξινόμηση
  2. Χρονική πολυπλοκότητα: O(N^2)
  3. Πολυπλοκότητα χώρου: O(1)
  4. Σταθερότητα: σταθερό

Κωδικός αναφοράς ακέραιων δεδομένων ταξινόμησης με φούσκα (τοπικές ρυθμίσεις 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 υποστηρίζει μόνο ταξινόμηση ακεραίων αριθμών Εδώ επεκτείνεταιΓενική διαδοχική ταξινόμησηκώδικας.

Ανατρέξτε στην ενσωματωμένη ταξινόμηση qsort στη γλώσσα C:
Εισαγάγετε την περιγραφή της εικόνας εδώ

Η συνάρτηση μπορεί να ληφθεί ως εξής:
Εισαγάγετε την περιγραφή της εικόνας εδώ

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

Στην πραγματικότητα, το μόνο που χρειάζεται είναιΔύο από τις θέσεις του έχουν αλλάξει σημαντικά, μπορείτε να πάρετε μια γενική ταξινόμηση:

Αλλαγές στον τρόπο με τον οποίο γίνονται συγκρίσεις:

Αλλάξτε τη μέθοδο σύγκρισης σεδείκτη λειτουργίαςτρόπο, ώστε οι χρήστες να μπορούνΓράψτε τη δική σας συνάρτηση τύπου σύγκρισης(Δεν περιλαμβάνει μόνο ενσωματωμένους τύπους, αλλά και αυτούς που ορίζονται από τη δομή, αλλά η προϋπόθεση είναισυνεχώς）
Εισαγάγετε την περιγραφή της εικόνας εδώ

Εισαγάγετε την περιγραφή της εικόνας εδώ
Εάν ο χρήστης ταξινομεί ακέραιους αριθμούς, η σύγκριση που γράφτηκε από τον ίδιο είναι (μόνο για αναφορά, η μέθοδος δεν είναι μοναδική):

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

Αλλαγές στον τρόπο με τον οποίο γίνονται οι ανταλλαγές:

Εδώ χρειάζεται μόνο να αλλάξετε τη μέθοδο ανταλλαγής σε ανταλλαγή byte-by-byte.
Εισαγάγετε την περιγραφή της εικόνας εδώ
Εισαγάγετε την περιγραφή της εικόνας εδώ
Στη συνέχεια, η ανταλλαγή πρέπει να αλλάξει σε:

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

Επαλήθευση αποτελεσμάτων:

Ενσωματωμένοι τύποι:

Εισαγάγετε την περιγραφή της εικόνας εδώ
Εισαγάγετε την περιγραφή της εικόνας εδώ

Πλήρης κωδικός:

#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

Προσαρμοσμένος τύπος:

Εισαγάγετε την περιγραφή της εικόνας εδώ

Εισαγάγετε την περιγραφή της εικόνας εδώ
Πλήρης κωδικός:

#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

Ειδοποίηση:

Ο παραπάνω κωδικόςΜη έγκυρο για ασυνεχή δεδομένα, όπως είναι κάθε στοιχείο της συνδεδεμένης λίσταςαποθηκεύεται μέσω σύνδεσης δείκτη, η συνάρτηση σύγκρισης και η συνάρτηση ανταλλαγής πρέπει να αλλάξουν για επίλυση.

Προσωπικό προφίλ

Έχει αφοσιωθεί στην έρευνα της τεχνολογίας για περισσότερα από 30 χρόνια και είναι ικανός σε διάφορες γλώσσες όπως java, linux, javascript, php, css κ.λπ. Έχει κάνει πολλές συνεισφορές στον τομέα του ανοιχτού κώδικα σταθμός τεκμηρίωσης προγραμματιστή για να μοιραστείτε ορισμένα ζητήματα στην ανάπτυξη τεχνολογίας για μελλοντική αναφορά

τα στοιχεία επικοινωνίας μου

Ταχυδρομείο