【排序】冒泡排序

在我们的生活中，到处都离不开排序的作用，考试分数要排序，商场购物要排序，可以说排序对我们来说处处存在，那么从本章开始，我将要依次分享一些排序方法，从易到难，包括冒泡，插入，快速，希尔，选择等排序方法，希望大家能够支持。

目录

排序的相关概念

常见的排序方法

冒泡排序

1.逻辑：

2.优化：

3.代码实现：

4.动态图像：

小结

排序的相关概念

我们先来简单认识一下，什么是排序

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
 

内部排序：数据元素全部放在内存中的排序。
 

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排

常见的排序方法

看一下常见的排序方法

冒泡排序

今天我们要介绍的最基本的排序——冒泡排序

冒泡排序（Bubble Sort），由于其排序方法中，数据像气泡一样，根据自身的大小，一点一点的像数组另一端移动，就像是气泡从水底向水面冒出的效果，因此称为冒泡排序

冒泡排序（以排升序为例）

1.逻辑：

单趟排序：让前数与后面的数进行比较，若后面的数小于前面的数就交换位置，再继续向后遍历

 通过上面的逻辑图，我们可以看出来，单趟冒泡排序的逻辑，很显然，他会将最大的数找出来放到最后

我们需要嵌套两层循环，内层控制单趟排序的逻辑，外层控制整个排序的次数

内层循环：即单趟排序的逻辑，假设我们有n个未排序的数据，我们从0下标依次进行比较，若前者大于后者，就交换二者的位置

注意：一共有n个数据，那么只需要排n-1次

而每次内层循环会将最大的数放到数组最后，因此每进行依次内层循环，未排序的数据就 -1，这个我们就可以在外层循环来记录这个数据，假设这是第i次排序，那么就一共需要比较 n - i - 1次。

外层循环：外层排序，即多次实现内层排序，然后使数据达到有序的过程，一共有n个数据，就需要执行n-1次，最后一个数据的位置就是合适的位置，因此他不需要再进行排序，那么总共需要n-1次外层循环

2.优化：

当在一次大循环中，没有数据进行交换，说明数组中的数据已经排序完成，不需要继续执行之后的循环次数，所以我们可以用一个flag变量初始化为1，若在大循环中交换数据，就将其置为0，每次在内层循环结束后进行判断，若flag == 1说明没有数据进行交换，已排序完成，就break跳出循环

3.代码实现：

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{ 
		int flag = 1;
		for (int j = i; j < n-1-i ;j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 0;
			}
		}
		if (flag)
		{
			break;
		}
	}
}

4.动态图像：

如下：

小结

由代码我们可以发现，冒泡排序的时间复杂度为O（n^2），这相比于其他更为高级的排序，效率过低，因此冒泡排序的实践意义，几乎为0，大多用来进行教学，冒泡排序是最为基础的一个排序，重在理解排序的过程和逻辑