C-冒泡排序的循环条件应该怎么写

一、冒泡排序的原理

二、代码实现

三、代码解读

1. 第一层循环条件怎么来的

2.第二层循环条件怎么来的

四、优化代码

我发现，好像还是有一部分同志，没有很清楚冒泡排序的两层循环条件为什么这么写？

感到有些模糊，但又可以写得出来，那么下面我用画图的形式来给大家讲解一下

一、冒泡排序的原理

简单的来说，就是相邻两个元素比较

升序就是，左边元素比右边元素大，就交换位置 arr[j] > arr[j+1]
降序就是, 左边元素比右边元素小，就交换位置 arr[j+1] > arr[j]

有这么一个数组，用升序：

二、代码实现

#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 - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
	int arr[] = { 3,1,7,5,8,9,0,2,4,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

三、代码解读

步入主题

1. 第一层循环条件怎么来的

我们可以看到，有10个元素，但比较只需要9次，比元素小一次。

所以我们得到：元素个数 - 1 sz - 1

2.第二层循环条件怎么来的

因此，为了避免浪费时间，我们没有必要再对，这一轮最大的数进行比较排序。

但每次都在 sz - 1 的基础上减少一次排序次数，所以我们得出：

j < sz - 1 - i

可能会有同志想说，其实也并没有减少多少时间，不减也罢，就是硬算！

那是因为，我们采用的是10个元素的数组，那如果是100个元素，1000、10000个呢……

四、优化代码

虽然我们尽可能的优化了代码，避免重复排序，但还是会出现一些特殊情况。

比如：
int arr[] = {10，1，2，3，4，5，6，7，8，9}；
我们可以很容易的看出，只需要一次就可以，排序完成了，但是我们上述写的代码还要哐呲哐呲的跑。

我们可以定义一个全局变量，去记录循环的次数：
#include <stdio.h>
int count = 0;
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 - i - 1; j++)
		{
			count++;
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}
int main()
{
	int arr[] = { 10,1,2,3,4,5,6,7,8,9};
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\ncount = %d", count);
	return 0;
}
结果：

所以我们想这样写：

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 - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				count++;
				flag = 0;//发⽣交换就说明，⽆序
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
		if (flag == 1)//这⼀趟没交换就说明已经有序，后续⽆序排序了
			break;
	}
}

结果：