One 、 Description of the problem

         Bubble sort （Bubble Sort）, It's a simpler sort algorithm in the field of computer science .

         It repeatedly visits the element columns to be sorted , Compare two adjacent elements in turn , If the order （ : from large to small 、 First letter from Z To A） Mistakes are exchanged . The job of visiting elements is to do it repeatedly , Until no adjacent elements need to be exchanged , That is to say, the element column has been sorted .

         The name of this algorithm comes from the fact that the smaller the elements, the more slowly “ floating ” Go to the top of the list （ Ascending or descending order ）, Just like the bubbles of carbonated drinks will eventually rise to the top , So the name “ Bubble sort ”.

Two 、 Algorithm principle

1. Compare adjacent elements . If the first one is bigger than the second one , Just swap them . 

2. Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple . At this point , The last element should be the largest number .  

3. Repeat the above steps for all elements , Except for the last one . 

4. Keep repeating the above steps for fewer and fewer elements each time , Until there's no pair of numbers to compare .

3、 ... and 、 Algorithm implementation

#include <stdio.h>

void Bubble_Sort(int arr[], int n) {
	int flag = 1;
	for (int i = 0; i < n - 1; i++) {
		flag = 1;
		for (int j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				flag = 0;
			}
		}
		if (flag == 1) {
			break;
		}
	}
}

int main() {
	int arr[30] = {0};
	int n = 0;
	printf(" Please enter the size of the array ：\n");
	scanf("%d", &n);
	printf(" Enter each element in turn ：\n");
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	printf("\n Original array ：");
	for (int i = 0; i < n; i++) {
		if (i == (n - 1)) {
			printf("%d\n", arr[i]);
			break;
		}
		printf("%d, ", arr[i]);
	}
	Bubble_Sort(arr, n);
	printf("\n Array after sorting ：");
	for (int i = 0; i < n; i++) {
		if (i == (n - 1)) {
			printf("%d\n", arr[i]);
			break;
		}
		printf("%d, ", arr[i]);
	}

	return 0;
}

Four 、 Algorithm testing

5、 ... and 、 Algorithm stability

Bubble sort is to move small elements forward or to move large elements back . Comparison is the comparison of two adjacent elements , The exchange also happens between these two elements . therefore , If two elements are equal , No more exchange ; If two equal elements are not adjacent , So even if we exchange the two in front of each other to make the two adjacent , It won't be exchanged at this time , So the order of the same elements hasn't changed , So bubble sort is a stable sort algorithm .