每日一题——冒泡排序

前言：CSDN的小伙伴们，大家好！今天我来给大家分享一种解题思想——冒泡排序。

冒泡排序

1. 冒泡法的核心思想：两两相邻的元素进行比较
   2.冒泡排序的算法描述如下。

(1)比较相邻的元素。如果第一 个比第二个大，就交换两个元素。
(2)对每一对相邻元素做同样的工作，从开始第一对到结尾的最后 一对。在这一点，最后的元素应该会是最大的数。
(3)针对所有的元素重复以上的步骤，除了最后一个。
(4)持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。以6个数9、8、5、4、2、0为例:

第1趟比较，有6个数未排好序，两两比较5次;
第2趟比较，剩5个数未排好序，两两比较4次;
第3趟比较，剩4个数未排好序，两两比较3次;
第4趟比较，剩3个数未排好序，两两比较2次;
第5趟比较，剩2个数未排好序，两两比较1次;
第6趟比较，全部排好序，两两比较0次。

结论：对于n个数的排序，需进行n-1趟比较，第j次比较，需进行n-j次比较

冒泡排序不单指从小到大，也可以从大到小。对于冒泡排序，或许我们大家都比较熟悉，就比如说，对成绩进行排名，游戏排行榜，等等。这样都可以使用冒泡排序的思想，对数据进行排序。

练习

输人10个数，对10个数排序(由小到大)。

//1
#include<stdio.h>

int main()
{
	int a[10] = { 10 };
	int i = 0;
	int j = 0;
	int t = 0;
	for (i = 0; i < 10; i++)
	{
		scanf("%d", &a[i]);
	}
	for (j = 0; j < 9; j++)
	{
		for (i = 0; i < 9 - j; i++)
		{
			if (a[i] > a[i + 1])
			{
				t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
			}
		}
	}
	for (i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;


//也可以写成
#include<stdio.h>
void bubble_sort(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz -1; i++)
	{
		int j = 0;
		for (j = 0; j < sz -1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
			}
		}
	}
}

void print_arr(int arr[], int sz)
{
	int i = 0;
	
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	print_arr(arr, sz);
	return 0;

}


//优化(因为可能这组数据部分有序，这样写可以优化代码）
#include<stdio.h>
void bubble_sort(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1;//假设已经有序了
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int t = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = t;
				flag = 0;
			}
		}
		if (flag = 1)
		{
			break;
		}
	}
}

void print_arr(int arr[], int sz)
{
	int i = 0;

	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	int arr[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	print_arr(arr, sz);
	return 0;
}

（完）
点个关注再走吧！