冒泡排序以及改進方案

介紹：

冒泡排序?qū)儆谝环N典型的交換排序（兩兩比較）。冒泡排序就像是把一杯子里的氣泡一個個往上冒一樣。它不斷比較相鄰的元素，如果順序不對就像水泡一樣交換它們的位置，直到整個序列像水泡一樣，按照大小順序排列好。當它發(fā)現(xiàn)一輪遍歷中沒有發(fā)生交換，就像是水泡都冒完了一樣，就知道排序完成了。

圖示：

冒泡排序性能

算法	最好時間	最壞時間	平均時間	額外空間	穩(wěn)定性
冒泡	O(n）	O(n2)	O(n2)	1	穩(wěn)定

普通版本的冒泡排序

通過簡單的兩層遍歷，就可以實現(xiàn)了：

for (int i = 0; i < array.length; i++) {for (int j = 0; j < array.length -i -1; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}
}

第一次改進：

當一個數(shù)組大小不是很混亂的時候，我們沒必要每次都去交換：

例如：2,1,3,4,6 這樣的數(shù)組，我們在第一次交換的時候就已經(jīng)排好序了（1,2,3,4,6）,我們無需再基于1,2,3,4,6排序，改進如下：

for (int i = 0; i < array.length; i++) {int flag = false; // 是否發(fā)生交換for (int j = 0; j < array.length -i -1; j++) {if (array[j] > array[j + 1]) { // 順序不對，需要交換// 以下三行交換操作int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true; // 發(fā)生了交換}if(!flag) { // 如果沒有發(fā)生交換，跳出循環(huán),無需比對后面的break;}}}

第二次改進：

最后一次交換位置將整個數(shù)組分為了兩部分：之前是未排序部分，之后是已排序部分。如此一來，下一次冒泡排序就只需在未排序部分進行冒泡排序即可。 根據(jù)這個思路再進行代碼改進：

public class BubbleSort {// 冒泡排序算法實現(xiàn)public static void bubbleSort(int[] array) {if (array == null || array.length < 0) {return;}int sortIndex = array.length - 1; // 初始排序邊界為數(shù)組末尾int lastChange = 0; // 記錄最后一次交換的位置for (int i = 0; i < array.length; i++) {boolean flag = false; // 標記是否發(fā)生交換for (int j = 0; j < sortIndex; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true;lastChange = j; // 更新最后一次交換的位置}}sortIndex = lastChange; // 更新排序邊界if (!flag) { // 若未發(fā)生交換，說明數(shù)組已排序，結(jié)束排序break;}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("排序后的數(shù)組:");for (int i : arr) {System.out.print(i + " ");}}
}