java冒泡排序_冒泡排序(java)

0. 說明

最近工作中遇到了排序的需要，其實很簡單，就是兩個PO按照時間的字段排序後将結果傳回前端，很簡單的一個需求，但是卻讓我感覺應該将排序算法，整理一下。

今天在本文中，我們就先整理下冒泡排序的算法，在着重分析下怎麼交換兩個資料。

1. 冒泡排序

冒泡排序算法，理論很簡單，就是通過周遊，每次周遊将最小(最大)值放在為排序數組中最前面的位置。畫個圖下看下大概的流程。圖中的測試資料數組為[6,4,2,8,3,5]。

冒泡排序

可見，第一次周遊的時候，将最小值放在了數組的首位，也就是2放在了首位。第二次周遊的時候，将次小值放在了數組的次位，也就是3放在了數組的第二位。

理論上應該周遊的是n-1次，上面的示例，應該周遊的是5次，但是我們的圖中周遊4次就結束了，是因為，周遊四次後，後面未排序的數組正好已經有序了，是以在實際開發中，結束周遊的條件，可以稍作修改，這樣就可以提前結束周遊，節省計算資源。

新增一個标記位，每次周遊的時候，如果有資料交換，則将标記位标記是true，否則為false。在新一輪的周遊開始的時候，如果标記位為false,則直接結束周遊。可以提前結束周遊，節省不必要的周遊開銷，但是增加了一個編輯位的存儲，以及每次周遊的判斷，但是當資料量大的時候，判斷周遊是否進行的判斷，比判斷周遊内資料的對比少的多。另外存儲标記位，是一種空間換時間的操作。

2. java實作。

筆者的主語言是Java，是以就用Java做一個簡單的示例：

public class BubbleSort { public static int[] sort(int[] arr) throws Exception { if (arr == null) { throw new Exception("參數異常"); } if (arr.length == 0 || arr.length == 1) { return arr; } for (int i = 0; i < arr.length - 1; i++) { for (int j = arr.length; j > i; j--) { if (arr[j] < arr[j - 1]) { int tmp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = tmp; } } } return arr; }}
           

測試代碼：

@Testpublic void test_bubble_sort() throws Exception { int[] arr = {6,4,2,8,3,5}; arr = BubbleSort.sort(arr); System.out.println(Arrays.toString(arr)); int[] arr2 = new int[100]; Random random = new Random(10000); for (int i = 0 ; i < 100; i++) { arr2[i] = random.nextInt(10000); } System.out.println(Arrays.toString(arr2)); arr2 = BubbleSort.sort(arr2); System.out.println(Arrays.toString(arr2));}
           

運作結果：

[2, 3, 4, 5, 6, 8][2208, 572, 9116, 3475, 4500, 9574, 5641, 9166, 9727, 7670, 3030, 6816, 2621, 2172, 8074, 7634, 7455, 3468, 5423, 4888, 3594, 3684, 5136, 363, 4111, 6762, 4480, 4705, 3924, 4626, 72, 6234, 9073, 2345, 6824, 9818, 616, 5521, 4831, 30, 1515, 6297, 3430, 7197, 5985, 8791, 9926, 9276, 2467, 165, 8650, 9054, 8881, 326, 479, 1079, 7714, 5235, 2119, 9051, 456, 6343, 1629, 2903, 4130, 1667, 1219, 4171, 2075, 3998, 1896, 8627, 2752, 205, 565, 9185, 718, 9435, 8710, 25, 473, 1909, 9798, 8473, 7050, 4229, 9859, 8290, 4896, 3176, 1808, 6647, 4743, 2942, 2249, 4657, 2598, 3790, 9841, 5276][25, 30, 72, 165, 205, 326, 363, 456, 473, 479, 565, 572, 616, 718, 1079, 1219, 1515, 1629, 1667, 1808, 1896, 1909, 2075, 2119, 2172, 2208, 2249, 2345, 2467, 2598, 2621, 2752, 2903, 2942, 3030, 3176, 3430, 3468, 3475, 3594, 3684, 3790, 3924, 3998, 4111, 4130, 4171, 4229, 4480, 4500, 4626, 4657, 4705, 4743, 4831, 4888, 4896, 5136, 5235, 5276, 5423, 5521, 5641, 5985, 6234, 6297, 6343, 6647, 6762, 6816, 6824, 7050, 7197, 7455, 7634, 7670, 7714, 8074, 8290, 8473, 8627, 8650, 8710, 8791, 8881, 9051, 9054, 9073, 9116, 9166, 9185, 9276, 9435, 9574, 9727, 9798, 9818, 9841, 9859, 9926]
           

3. 總結

冒泡算法是最簡單的排序算法之一，它需要由于又嵌套周遊，外部周遊次數為n-1，内部周遊次數平均為(n-1)/2，是以它的時間複雜度是O(n^2), 空間複雜度是O(1)，基本上隻占有一個臨時空間，但也可以做到不占用額外的空間，這個留作下一篇文章詳細說明，如有興趣可關注本公衆号。該算法還是穩定的排序算法，因為兩個相等的資料在周遊的時候，不會交換位置，而且所有的交換都是相鄰兩個資料的交換，是以該排序算法是穩定的排序算法。

希望本文對各位看官了解排序算法有所幫助。

求**評論、點贊、關注+轉發**

限于筆者知識有限，如果不足之處請幫忙指正，不喜勿噴！

您的支援是我不懈努力的動力，請讀者多支援下！

更多文章，請關注微信公衆号 CS_Toper之路，或者頭條号 CSToper。