一、定義
冒泡排序是最基礎的排序算法。
冒泡排序的英文是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-i
for(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 static int[] 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)，也就是原地排序
穩定性:相等元素之間原有的先后順序不變，也就是穩定排序
