C语言——冒泡排序

一、冒泡排序是什么

冒泡排序：

冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序。升序时：它会遍历若干次需要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！降序反之。

二、图文解释

冒泡排序的核心就是要知道他是两两比较的，还有他需要完成几趟，每趟需要两两比较多少次？

由图可知：

当我们升序排列时，如果我们有sz个元素，每完成一趟，最大的元素就会排列在最后。当我们完成最后一趟的时候，前面两个元素会同时完成排列。由此可知，在最坏的情况下，我们需完成sz-1趟所有的元素都会完成排列。

那每趟需要两两比较几次呢？

第一趟的时候：需要sz-1次

第二趟的时候：因为最后一个元素已经不需要参加比较了，所有只有sz-1个元素参拍，那么就需要sz-1-1次

第三趟的时候：因为最后两个元素已经不需要参加比较了，所有只有sz-2个元素参拍，那么就需要sz-2-1次

所以我们得出：

for (int i = 0; i < sz - 1; i++)//确定趟数
{
	for(int j=0;j<sz-1-i;j++)//确定每趟需要两两比较的次数
}

三、代码演示

现在我们原理以及搞清楚了，接下来看代码展示：

#include<stdio.h>
void Bubble_sort(int arr[], int size)
{
	int j, i, tem;
	for (i = 0; i < size - 1; i++)//size-1是因为不用与自己比较，所以比的数就少一个
	{
		for (j = 0; j < size - 1 - i; j++)	//size-1-i是因为每一趟就会少一个数比较
		{
			if (arr[j] > arr[j + 1])//这是升序排法，前一个数和后一个数比较，如果前数大则与后一个数换位置
			{
				tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
			}
		}
	}

}
int main()
{
	int arr[10];
	int i;

	printf("请输入10个数\n");
	for (i = 0; i < 10; i++)		//接收用户的数值
	{
		scanf("%d", &arr[i]);
	}
	printf("排序前的数组>");
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n排序后的数组>");
	Bubble_sort(arr, 10);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

但是我们这个代码有个缺陷，就是如果某一趟以及完成了所有排列，但是程序还是会继续执行，完成所有趟数，这就显得有些浪费时间了。

所以我们可以添加一句赋值语句，如果某趟执行完之后，发现这个赋值语句的变量没有发生改变，我们则认为这个排序以及完成了，就可以退出循环。

代码展示如下：

#include<stdio.h>
void Bubble_sort(int arr[], int size)
{
	int j, i, tem;
	for (i = 0; i < size - 1; i++)//size-1是因为不用与自己比较，所以比的数就少一个
	{
		int flag = 1;//我们假设这个数组已经有序
		for (j = 0; j < size - 1 - i; j++)	//size-1-i是因为每一趟就会少一个数比较
		{
			if (arr[j] > arr[j + 1])//这是升序排法，前一个数和后一个数比较，如果前数大则与后一个数换位置
			{
				tem = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tem;
				flag = 0;//发生排序，改变flag的值，说明还没有拍好序
			}
		}
		if (flag == 1)			//如果某一趟没有交换位置，则说明已经排好序，直接退出循环
			break;
	}

}
int main()
{
	int arr[10];
	int i;

	printf("请输入10个数\n");
	for (i = 0; i < 10; i++)		//接收用户的数值
	{
		scanf("%d", &arr[i]);
	}
	printf("排序前的数组>");
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n排序后的数组>");
	Bubble_sort(arr, 10);
	for (i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}

添加一条flag语句来判断数组是否有序，就会为我们节省很多时间。