冒泡排序

• 1.前言
• 2.实现步骤
• • 优化
• 3.总结
• 4.更新日志

1.前言

冒泡排序算法(Bubble Sort)是一种简单直观的排序算法。基本是最简单的排序算法之一。
算法名字的由来：越小的元素在经过交换后逐渐向前移动，就像气泡“上浮”到最顶端一样，同时，越大的元素则会“沉底”。

2.实现步骤

每次从 第一个元素 开始比较  相邻的元素 ，将较大的元素向 后 移动（交换）。
第一次比较完成后，最大的元素将在最后。
下一次使用同样的方法进行比较，但是不包括最后一个元素（此时最后一个元素已经为最大元素，不需要参与比较）
重复上述步骤，直至没有需要比较的两个数字

#include <stdio.h>
void Swap(int* a, int* b)   //交换
{
	int t = *a;
	*a = *b;
	*b = t;
}
void BubbleSort(int* arr, int sz)  //冒泡排序
{
	int i, j;  //定义
	for (i = 0; i < sz - 1; i++)   //共进行 sz-1趟
	{
		for (j = 0; j < sz - i - 1; j++) //每一趟比较 sz-i-1 次，交换过后最大的在最后
		{
			if (arr[j] > arr[j + 1])       //如果前一个比后一个大，则交换
				Swap(&arr[j], &arr[j + 1]);    
		}
	}
}
int main()
{
	int i;
	int arr[] = { 1,5,6,3,9,12,7,4 };  //初始化数组
	int sz = sizeof(arr) / sizeof(arr[0]);  //计算数组长度大小
	BubbleSort(arr, sz);   //传参
	for (i = 0; i < sz; i++)  //打印排序后的数组
		printf("%d ", arr[i]);   
	return 0;
}

优化

立flag:在遍历一趟元素比较时，并未发生交换，则说明已经排好序，则不需要进行下次比较。

void Swap(int* a, int* b)   //交换
{
	int t = *a;
	*a = *b;
	*b = t;
}
void BubbleSort(int* arr, int sz)  //冒泡排序
{
	int i, j, flag;  //定义
	for (i = 0; i < sz - 1; i++)   //共进行 sz-1趟
	{
		flag = 0;      //令flag初始化为0
		for (j = 0; j < sz - i - 1; j++) //每一趟比较 sz-i-1 次，交换过后最大的在最后
		{
			if (arr[j] > arr[j + 1])       //如果前一个比后一个大，则交换  同时更新flag
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0)    //当flag进行一趟比较且并未变化时，则结束比较
			return;     //或者 break;
	}
}
int main()
{
	int i;
	int arr[] = { 1,3,5,4,9,11,8,25 };  //初始化数组
	int sz = sizeof(arr) / sizeof(arr[0]);  //计算数组长度大小
	BubbleSort(arr, sz);   //传参
	for (i = 0; i < sz; i++)  //打印排序后的数组
		printf("%d ", arr[i]);
	return 0;
}

3.总结

性能不高，会有大量重复的比较
建议使用其他排序算法进行比较

4.更新日志

2022.2.20 整理上传（C）

欢迎交流、补充、指正~~