數據結構與演算法系列十一（冒泡排序）
- 2020 年 3 月 10 日
- 筆記
有人說，數據結構與演算法，電腦網路，與作業系統都一樣，脫離日常開發，除了面試這輩子可能都用不到呀！
有人說，我是做業務開發的，只要熟練API，熟練框架，熟練各種中間件，寫的程式碼不也能“飛”起來嗎？
於是問題來了：為什麼還要學習數據結構與演算法呢？
#理由一： 面試的時候，千萬不要被數據結構與演算法拖了後腿 #理由二： 你真的願意做一輩子CRUD Boy嗎 #理由三： 不想寫出開源框架，中間件的工程師，不是好廚子
我想好了，還是需要學習數據結構與演算法。但是我有兩個困惑：
1.如何著手學習呢？
2.有哪些內容要學習呢？
學習方法推薦：
#學習方法 1.從基礎開始，系統化學習 2.多動手，每一種數據結構與演算法，都自己用程式碼實現出來 3.思路更重要：理解實現思想，不要背程式碼 4.與日常開發結合，對應應用場景
學習內容推薦：
數據結構與演算法內容比較多，我們本著實用原則，學習經典的、常用的數據結構、與常用演算法
#學習內容： 1.數據結構的定義 2.演算法的定義 3.複雜度分析 4.常用數據結構 數組、鏈表、棧、隊列 散列表、二叉樹、堆 跳錶、圖 5.常用演算法 遞歸、排序、二分查找 搜索、哈希、貪心、分治 動態規劃、字元串匹配
在上一篇：數據結構與演算法系列十（排序概述）中，我們列舉了常用的排序演算法，以及分析了如何綜合衡量排序演算法的優劣。如果你還沒有看上一篇的內容，可以去看一看，應該會有所收穫。
從這一篇開始，我們把每一種排序演算法，從演算法的思想，到程式碼實現都做一個分享。那麼你準備好了嗎？
我們這一篇的主角是：冒泡排序
#考考你： 1.你知道冒泡排序的核心思想嗎？ 2.你能用java實現冒泡排序嗎？ 3.你能寫出更優秀的冒泡排序程式碼嗎？
假設有一個待排序序列：[4, 5, 6, 3, 2, 1]。我們需要按照升序進行排序，排序後的序列是這樣的：[1, 2, 3, 4, 5, 6]。
如何通過冒泡排序實現呢？
這裡我們先來理解冒泡排序中的冒泡兩個字。所謂冒泡就像平靜的水面，魚兒從水底吹氣一樣，一個一個的水泡向上冒，很詩情畫意，我們都嚮往這樣的生活環境對吧。
那麼請保持這個美好的姿勢，我們一起來理解冒泡排序的思想，先看一個圖：
冒泡排序核心思想：
1.n個元素，n次冒泡 2.比較交換相鄰元素
/** * 冒泡排序：普通實現版本 * @param array：待排序數組 * @param n：待排序數組大小 */ public static void sort_1(Integer [] array,int n){ // 如果排序數組規模小於等於1，直接返回 if(n <= 1){ return; } // 有n個元素，進行n次冒泡 for(int i = 0; i < n; i++){ // 每一次冒泡，比較交換相鄰兩個元素 for(int j = 0; j < n-i-1; j++){ if(array[j] > array[j+1]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } }
public static void main(String[] args) { // 初始化測試數組 Integer[] array = {4,5,6,3,2,1}; // 排序前 System.out.println("1.排序前數組：" + Arrays.deepToString(array)); // 排序後 sort_1(array,array.length); // 排序後 System.out.println("2.排序後數組：" + Arrays.deepToString(array)); }
測試結果：
D: 2teach 1softjdk8binjava com.anan.algorithm.sort.BubbleSort 1.排序前數組：[4, 5, 6, 3, 2, 1] 2.排序後數組：[1, 2, 3, 4, 5, 6] Process finished with exit code 0
在這裡，請你先簡單思考一下：有沒有更優化的實現方式呢？
我們先來分析一下冒泡排序演算法的時間複雜度，結合程式碼我們發現冒泡排序的時間複雜度是：O(n^2)，有兩次for循環，這不是一個高效的演算法對吧。如果說我們能夠減少冒泡的次數，則可以極大提升演算法的執行效率。
問題來了：什麼情況下可以減少冒泡次數呢？
其實我們只要結合冒泡排序演算法的核心思想後半部分：比較交換相鄰的元素。如果說在一次冒泡中，沒有發生相鄰元素的交換，那說明待排序序列已經有序了，不管後面還剩下多少次冒泡，我們都不需要再進行冒泡下去了。這樣是不是就減少冒泡的次數了呢
關於減少冒泡次數的分析，如果你暫時沒有理解過來的話，沒有關係。請看我們下面的程式碼實現，相信結合程式碼你會恍然大悟。
/** * 冒泡排序：優化實現版本 * @param array：待排序數組 * @param n：待排序數組大小 */ public static void sort_2(Integer [] array,int n){ // 如果排序數組規模小於等於1，直接返回 if(n <= 1){ return; } // 優化標識 // 如果某一次冒泡過程中，沒有發生數據交換 // 則說明已經排好了序，不需要在繼續冒泡 boolean flag = false; // n個元素，n次冒泡 for(int i = 0; i < n; i++){ // 重置是否發生交換標識 flag = false; // 每一次冒泡中，比較交換相鄰元素 for(int j = 0; j < n-i-1; j++){ if(array[j] > array[j+1]){ int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; // 發生了數據交換 flag = true; } } // 一次冒泡結束,檢查是否發生了數據交換 // 如果沒有發生數據交換，說明序列已經有序，不需要再繼續冒泡了 System.out.println("第【" + (i+1) + "】次冒泡."); if( !flag){ break; } } }
public static void main(String[] args) { // 初始化測試數組 Integer[] array = {4,5,6,3,2,1}; // 排序前 System.out.println("1.排序前數組：" + Arrays.deepToString(array)); // 第一次排序 System.out.println("2.第一次排序-------------------------------start"); sort_2(array,array.length); System.out.println("3.第一次排序後數組：" + Arrays.deepToString(array)); // 第二次排序 System.out.println("4.第二次排序-------------------------------start"); sort_2(array,array.length); System.out.println("5.第二次排序後數組：" + Arrays.deepToString(array)); }
測試結果：
#考考你答案： 1.你知道冒泡排序的核心思想嗎？ 1.1.假設待排序序列有n個元素 1.2.整個排序過程中，需要n次冒泡 1.3.每一次冒泡過程中，依次比較交換相鄰兩個元素 1.4.一次冒泡結束，都會有一個元素到達指定的位置 2.你能用java實現冒泡排序嗎？ 2.1.參考【3.2】節案例實現 3.你能寫出更優秀的冒泡排序程式碼嗎？ 3.1.結合冒泡排序演算法的核心思想：n個元素、n次冒泡，每一次冒泡依次比較交換相鄰的兩個元素 3.2.如果在某一次冒泡中，沒有發生元素交換 3.3.說明待排序序列已經有序，不需要再進行冒泡下去
