【排序】——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;			//不用继续了，已经有序，提前退出}}
}

我给这个案例测试：
1 2 3 4 5 6 7 9 8 就9和8没有升序

普通版本：

优化版本：

显然速度稍微得到提升！

5.时空复杂度