기술나눔

버블 정렬 및 해당 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 언어 일반 연속형 정렬 코드

위의 C 언어 버블 정렬 코드는 정수 정렬만 지원합니다.일반 순차 정렬암호.

C 언어에 내장된 qsort 정렬을 참조하세요.
여기에 이미지 설명을 삽입하세요.

함수는 다음과 같이 얻을 수 있습니다.
여기에 이미지 설명을 삽입하세요.

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

교환 방식 변경:

여기서는 교환 방법을 바이트별 교환으로 변경하기만 하면 됩니다.
여기에 이미지 설명을 삽입하세요.
여기에 이미지 설명을 삽입하세요.
그런 다음 스왑을 다음과 같이 변경해야 합니다.

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 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편