回顧一下排序算法，老酒裝新瓶，給自己的技能點做個回放。

排序(Sorting) 是計算機程序設計中的一種重要操作，它的功能是將一個數據元素(或記錄)的任意序列，重新排列成一個有序的序列，也可以理解為高矮個站隊。

衡量排序算法的兩個指標，時間復雜度 和 穩定性。

舉個例子，如果我們的數據是：3 5 4 2 2, 穩定的排序最后的倆個2在排好序后他們的原始前后順序是不會變的(第一個2還在第二個2的前面，有點繞，你可以理解為小明和小強一樣高，最開始小明在小強的前面，排完序之后，小明還在小強前面，就屬于穩定的排序），不穩定的排序最后兩個2的順序可能交換（也就是可能小明在前，也可能小強在前）。

時間復雜度先跳過哈，我回頭單獨寫一篇文章介紹，本文主要介紹和實操“冒泡排序”。

介紹

冒泡排序是將比較大的數字移到序列的后面，較小的移到前面。

從第一個開始，第一個和第二個比，誰高（大）誰站后面（兩個人（數）的位置交換，不是最后面），當前第二個再與第三個比，依次進行，一輪下來之后，篩選出來最高個（大）的人（數）。

上面就表示第一輪結束了，第二輪和第一輪一樣，只是最后一個人（數）已經排好了，不用管他了。

經過 N-1 輪之后，排序完成。

N 個人，經過 N-1 輪，相當于 N*(N-1)=N^2-N, 時間復雜度取最大的 O(n^2)

實例

原始數據：

3 5 2 6 2

第一輪

比較 3 和 5，5 大于 3 ，不需交換

3 5 2 6 2

繼續比較 5 和 2，5 大于 2，交換位置

3 2 5 6 2

繼續比較 5 和 6，6 大于 5，不需交換

3 2 5 6 2

繼續比較 6 和 2，6 大于 2，交換位置

3 2 5 2 6

6 移到最后，兩個2都分別向前移動。

第二輪

比較 3 和 2， 3 大于 2，交換位置

2 3 5 2 6

比較 3 和 5， 5 大于 3，不需交換

2 3 5 2 6

比較 5 和 2， 5 大于 2，交換位置

2 3 2 5 6

不需比較 5 和 6

第三輪

比較 2 和 3， 3 大于 2，不需交換

2 3 2 5 6

比較 3 和 2， 3 大于 2，交換位置

2 2 3 5 6

不需比較了

第四輪

比較 2 和 2，不需交換

2 2 3 5 6

四輪結束，最終的結果：

2 2 3 5 6

Java 實現

public?class?Bubble?{/***?冒泡排序*/public?static?int[]?sort(int[]?array)?{int?temp;//?第一層循環表明比較的輪數,?比如?length?個元素,比較輪數為?length-1?次（不需和自己比）for?(int?i?=?0;?i?<?array.length?-?1;?i++)?{System.out.println("第"?+?(i?+?1)?+?"輪開始");//?第二層循環，每相鄰的兩個比較一次，次數隨著輪數的增加不斷減少，每輪確定一個最大的，不需比較那個最大的for?(int?j?=?0;?j?<?array.length?-?1?-?i;?j++)?{System.out.println("第"?+?(i?+?1)?+?"輪，第"?+?(j?+?1)?+?"次比較：");if?(array[j?+?1]?<?array[j])?{temp?=?array[j];array[j]?=?array[j?+?1];array[j?+?1]?=?temp;}for?(int?k?:?array)?{System.out.print(k?+?"?");}System.out.println();}System.out.println("結果：");for?(int?k?:?array)?{System.out.print(k?+?"?");}System.out.println();}return?array;}public?static?void?main(String[]?args)?{int[]?array?=?{3,?5,?2,?6,?2};int[]?sorted?=?sort(array);System.out.println("最終結果");for?(int?i?:?sorted)?{System.out.print(i?+?"?");}}}

輸出結果：

第1輪開始
第1輪，第1次比較：
3?5?2?6?2?
第1輪，第2次比較：
3?2?5?6?2?
第1輪，第3次比較：
3?2?5?6?2?
第1輪，第4次比較：
3?2?5?2?6?
結果：
3?2?5?2?6?
第2輪開始
第2輪，第1次比較：
2?3?5?2?6?
第2輪，第2次比較：
2?3?5?2?6?
第2輪，第3次比較：
2?3?2?5?6?
結果：
2?3?2?5?6?
第3輪開始
第3輪，第1次比較：
2?3?2?5?6?
第3輪，第2次比較：
2?2?3?5?6?
結果：
2?2?3?5?6?
第4輪開始
第4輪，第1次比較：
2?2?3?5?6?
結果：
2?2?3?5?6?
最終結果
2?2?3?5?6?

優化改進

對冒泡排序常見的改進方法是加入一標志性變量 pos ，用于標志某一趟排序過程中是否有數據交換，如果進行某一趟排序時并沒有進行數據交換（都不需要交換，肯定排好了），則說明數據已經按要求排列好，可立即結束排序，避免不必要的比較過程。

設置一標志性變量 pos,用于記錄每趟排序中最后一次進行交換的位置（后面有多個沒有發生交換，說明后面已經排好了）。由于 pos 位置之后的記錄均已交換到位，故在進行下一趟排序時只要排到 pos 位置即可。

怎么理解呢？

以 3 2 4 5 6 為例

第一輪排序，發生交換的位置僅僅是 3 和 2， 則 pos 是 0（索引位置從0開始）

直接一輪就結束了，而不用傻傻的再跑4輪。

代碼實現：

public?class?Bubble?{/***?冒泡排序（優化改進版）*/public?static?int[]?sort(int[]?array)?{int?temp;int?time?=?1;for?(int?i?=?array.length?-?1;?i?>?0;?)?{System.out.println("第"?+?time?+?"輪開始");int?pos?=?0;//?第二層循環，每相鄰的兩個比較一次，次數隨著輪數的增加不斷減少，每輪確定一個最大的，不需比較那個最大的for?(int?j?=?0;?j?<?i;?j++)?{System.out.println("第"?+?time?+?"輪，第"?+?(j?+?1)?+?"次比較：");if?(array[j?+?1]?<?array[j])?{//?記錄最后一次交換位置的索引，下一輪只需排序到?pos?位置pos?=?j;temp?=?array[j];array[j]?=?array[j?+?1];array[j?+?1]?=?temp;}for?(int?k?:?array)?{System.out.print(k?+?"?");}System.out.println();}//?之前是?i--,?優化后直接跳到最后交換位置的索引i?=?pos;time++;System.out.println("結果：");for?(int?k?:?array)?{System.out.print(k?+?"?");}System.out.println();}return?array;}public?static?void?main(String[]?args)?{int[]?array?=?{3,?2,?4,?5,?6};int[]?sorted?=?sort(array);System.out.println("最終結果");for?(int?i?:?sorted)?{System.out.print(i?+?"?");}}}

結果輸出：

第1輪開始
第1輪，第1次比較：
2?3?4?5?6?
第1輪，第2次比較：
2?3?4?5?6?
第1輪，第3次比較：
2?3?4?5?6?
第1輪，第4次比較：
2?3?4?5?6?
結果：
2?3?4?5?6?
最終結果
2?3?4?5?6?

總結

好了，今天的分享就這些，關于冒泡排序，你學會了嘛？如果學會了，看懂了，請留下你的點贊，收藏，分享，關注。

有任何問題可以公作號：新質程序猿，可以找到我。