冒泡排序（核心思想和具体代码）

The sky

发布于 2023-04-12 14:16:56

2300

发布于 2023-04-12 14:16:56

文章被收录于专栏：C++的逆袭之路

前言

在排序中，有各种各样的排序方式，今天我们将要来介绍《冒泡排序》。今天会从冒泡排序的具体意义和他的操作来展开。

一、冒泡排序是什么？

从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

二、具体步骤

1.代码解释

代码如下（示例）：

#include<stdio.h>

void bubble(int arr[], int sz)
{
	for (int j = 0; j < sz - 1; j++)           //一趟排n-1次(n为n个数）
									           //n个数的话，就要走n-1趟（每一趟排完以后，都 
                                               //要减去最后一个排好的数）
	{
		int flag = 0;
		for (int i = 0; i < sz-1-j; i++)
		{
			if (arr[i] <arr[i + 1])
			{
				int temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}
int main()
{
	int arr[] = { 要排序的元素 };

	int sz = sizeof(arr) / sizeof(arr[0]);  // sz为数组元素个数。

	bubble(arr,sz);

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

举例详细说明：

同理可得，每一趟以后减去一个元素，则每趟需要减去一次次数。

所以for循环中，需要i<sz-1-j.

当遇到规范的数组元素时（不需要排序），int flag =0初始为零，若需要排序，则进入 if (arr[i] <arr[i + 1])循环中，则flag变为1；若一趟过完之后，发现并未交换元素，则flag=0未变，直接跳出循环，减少了时间复杂度。

2.读入数据

代码如下（示例）：

#include<stdio.h>

void bubble(int arr[], int sz)
{
	for (int j = 0; j < sz - 1; j++)           //一趟排n-1次(n为n个数）
									           //n个数的话，就要走n-1趟（每一趟排完以后，都 
                                               //要减去最后一个排好的数）
	{
		int flag = 0;
		for (int i = 0; i < sz-1-j; i++)
		{
			if (arr[i] <arr[i + 1])
			{
				int temp = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}
int main()
{
	int arr[] = { 1，3，54，76，7，5，45，9 };

	int sz = sizeof(arr) / sizeof(arr[0]);

	bubble(arr,sz);

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

那么可以看出，输出的结果就是 76，54，45，9，7，5，3，1