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

按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。一、定义冒泡排序是最基础的排序算法。
冒泡排序的英文是bubble sort，它是一种基础的交换排序。
冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。

二、思路按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

文章插图
经过第一轮后：元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧。

文章插图
每一轮结束都会有一个元素被移到最右侧。

文章插图
三、实现1、冒泡算法

public static void main(String[] args) {int[] array = {1,6,2,5,3,0,3,5,4};array = bubbleSortBySortedExchanged(array);for(int i =0 ; i < array.length; i++){System.out.println(array[i]);}}public static int[] bubbleSort(int[] array){//有array.length-1个数字需要交换for(int i = 0; i < array.length - 1; i++){//每个数字比较的次数是array.length-1-ifor(int j = 0; j < array.length - 1 - i; j++){//如果当前值大于后一个值，则将更大的值移到后一位if(array[j] > array[j+1]){swap(array[j],array[j+1]);}}}return array;}//互相交换值public static void swap(int a,int b){int temp = a;a= b;b= temp;}

2、冒泡算法优化
（1）外层优化

文章插图
【数据结构与算法：冒泡排序】第6轮已经可以结束了，也就是如果不需要交换了，则说明已经排好序了
思路：在外层循环处，设置标志isSort，默认为排好，如果不交换则跳出本次循环
（2）内部优化
已经被移到右侧的元素不用再参与比较了
思路：设置lastExchangeIndex标志单轮比较中最后一次比较的数值下标，下一轮比较就以lastExchangeIndex结束。

private staticint[] bubbleSortBySortedExchanged(int[] array){if(array == null || array.length < 2){return array;}//单轮比较中最后一次交换的数值下标int lastExchangeIndex = 0;int sortBorder = array.length - 1;//不交换则表示已排好boolean isSorted = true;for(int i = 0 ;i < array.length - 1; i++){for(int j = 0; j < sortBorder ; j++){if(array[j] > array[j+1]){isSorted = false;int temp = array[j+1];array[j+1] = array[j];array[j] = temp;lastExchangeIndex = j;}}sortBorder = lastExchangeIndex;if(isSorted){break;}}return array;}

四、复杂度时间复杂度：O( n的2次方 )
空间复杂度：O(1)，也就是原地排序
稳定性:相等元素之间原有的先后顺序不变，也就是稳定排序