### **冒泡排序算法思想** 两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位。 > 依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。 > > 第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较； > > 第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较； > > 依次类推，每一趟比较次数-1； > > …… 冒泡排序算法的运作过程：（从小到大排序） 设数组a\[0..n-1\]长度为n, * 1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。 * 2．这样对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第n-1个位置。 * 3．n=n-1，如果n不为0就重复前面二步，否则排序完成。 * * * 例子为从小到大排序,原始待排序数组| 7 | 2 | 4 | 1 | 5 | 第一趟排序(外循环) 第一次两两比较7 > 2交换(内循环) 交换前状态| 7 | 2 | 4 | 1 | 5 | 交换后状态| 2 | 7 | 4 | 1 | 5 | 第二次两两比较,7 > 4交换 交换前状态| 2 | 7 | 4 | 1 | 5 | 交换后状态| 2 | 4 | 7 | 1 | 5 | 第三次两两比较,7 > 1交换 交换前状态| 2 | 4 | 7 | 1 | 5 | 交换后状态| 2 | 4 | 1 | 7 | 5 | 第四次两两比较,7 > 5交换 交换前状态| 2 | 4 | 1 | 7 | 5 | 交换后状态| 2 | 4 | 1 | 5 | 7 | 第二趟排序(外循环) 第一次两两比较2 < 4不交换 交换前状态| 2 | 4 | 1 | 5 | 7 | 交换后状态| 2 | 4 | 1 | 5 | 7 | 第二次两两比较,4 > 1交换 交换前状态| 2 | 4 | 1 | 5 | 7 | 交换后状态| 2 | 1 | 4 | 5 | 7 | 第三趟排序(外循环) 第一次两两比较2 > 1交换 交换后状态| 2 | 1 | 4 | 5 | 7 | 交换后状态| 1 | 2 | 4 | 5 | 7 | 第二次两两比较,2 < 4不交换 交换后状态| 1 | 2 | 4 | 5 | 7 | 交换后状态| 1 | 2 | 4 | 5 | 7 | 排序完毕,输出最终结果1 2 4 5 7 * * * 冒泡排序时间复杂度，最好情况：数组已有序O(n)；最坏情况:数组反序O(n^2)，平均时间复杂度：O(n^2)。空间复杂度，冒泡排序是原地排序，空间复杂度为O(1)。冒泡排序算法是稳定的排序算法。 （1）时间复杂度 冒泡排序算法的最坏情况、最优情况、平均情况下的时间复杂度都是O（n^2） （2）空间复杂度 空间复杂度就是在交换元素时那个临时变量所占的内存空间；最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：O(1)；最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)；平均的空间复杂度为：O(1)；