冒泡排序

冒泡排序是一种简单的交换类排序。其基本思路是，从头开始扫描待排序的元素，在扫描过程中依次对相邻元素进行比较，将关键字值大的元素后移。每经过一趟排序后，关键字值最大的元素将移到末尾，此时记下该元素的位置，下一趟排序只需要比较到此位置为止，直到所有元素都已有序排列。

图解冒泡排序

与插入排序一样，需要进行冒泡排序的数组也分为已排序部分和未排序部分。

冒泡排序的规则为：从数组末尾开始依次比较相邻的两个元素，如果大小关系相反则交换位置，直到数组中不再有顺序相反的相邻元素。

我们对数组 a={5,3,2,4,1} 进行从小到大排序，排序过程如下所示。

第一轮排序：

我们将数组末尾的a[4]的值和a[3]的值进行对比，发现a[4]的值比a[3]的值小，则将它们交换，再接着对剩下的相邻的两个元素进行对比和交换，最终得到的结果为a={1,5,3,2,4}，已排序的部分的元素为1。

第二轮排序：

首先对比a[3]和a[4]的值，发现a[3]的值比a[4]的值小，则不需要进行排序。最终得到的结果为a={1,2,5,3,4}，已排序部分的元素为1、2。

第三轮排序：

同上面，经过第三轮排序，已排序部分的元素为1、2、3。

第四轮排序：

经过四轮排序我们最终得到的结果为a={1,2,3,4,5}

实现冒泡排序

实现插入排序时，我们要先定义两个变量，i为循环变量，表示未排序部分的开头元素，从数组开头向末尾移动。j也为循环变量，用于对未排序部分中相邻元素两两比较，从数组的末尾n-1开始减小到 i 结束(i=1)。

代码实现如下：