【排序】——1.冒泡排序法（含优化）

在这里插入图片描述

冒泡排序

在这里插入图片描述

1.原理

左边大于右边交换一趟排下来最大的交换到右边来(接下来所以文章用升序举例)

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

在这里插入图片描述

2.图解

在这里插入图片描述

3.代码

代码如下：

//普通版本
void Bubble_sort1(int* arr, int size)
{for (int i = 0; i < size; i++){//开始:i=0      j<size-1(j+1才size-1，符合下标)//size-1-i是因为每一趟就会少一个数比较for (int j = 0; j < size - i - 1; j++)	//{if (arr[j] > arr[j + 1])			//前面大于后面，把大的交换到右边{int tem = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tem;}}}
}

4.优化

设置flag，如果有序了，就不用往下循环了，提前退出

//优化版本
void Bubble_sort2(int* arr, int size)
{for (int i = 0; i < size; i++){int flag = 0;							//默认有序for (int j = 0; j < size - i - 1; j++)	size-1-i是因为每一趟就会少一个数比较{if (arr[j] > arr[j + 1])			//前面大于后面，把大的交换到右边{int tem = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tem;//发生交换，说明无序flag = 1;}}//如果前面都没有发生交换，说明已经有序了if (flag == 0){break;			//不用继续了，已经有序，提前退出}}
}