数据结构与算法：冒泡排序

冒泡排序是最基础的排序算法。,冒泡排序的英文是bubble sort，它是一种基础的交换排序。,冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。,按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位 置；当一个元素小于或等于右侧相邻元素时，位置不变。,,经过第一轮后： 元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧。,,每一轮结束都会有一个元素被移到最右侧。,,1、冒泡算法,2、冒泡算法优化,（1）外层优化,,第6轮已经可以结束了，也就是如果不需要交换了，则说明已经排好序了,思路：在外层循环处，设置标志isSort，默认为排好，如果不交换则跳出本次循环,（2）内部优化,已经被移到右侧的元素不用再参与比较了,思路：设置lastExchangeIndex标志单轮比较中最后一次比较的数值下标，下一轮比较就以lastExchangeIndex结束。,时间复杂度：O( n的2次方 ),空间复杂度：O(1)，也就是原地排序,稳定性:相等元素之间原有的先后顺序不变，也就是稳定排序