一、冒泡排序（BubbleSort）

• 基本思想：從左到右使用相鄰兩個元素進行比較，如果第一個比第二個大，則交換兩個元素。這樣會使較大數下沉到數組的尾端，即較小數像泡泡一樣冒到數組首端。
• 排序過程：

比較相鄰兩個元素，如果第一個比第二個大，則交換兩個元素；

從左到右依次比較，直到最大數位于數組尾端；

重復N-1次1、2步驟，(除去已經排序的最大數)依次將第二，第三。。。第N-1大的數排好位置。

原序列39658274

第1趟	3	6	5	8	2	7	4	9
第2趟	3	5	6	2	7	4	8	9
第3趟	3	5	2	6	4	7	8	9
第4趟	3	2	5	4	6	7	8	9
第5趟	2	3	4	5	6	7	8	9
第6趟	2	3	4	5	6	7	8	9
第7趟	2	3	4	5	6	7	8	9

如表格所示，每一趟都將當前亂序序列中最大的數移到尾端。【小伙伴們從表格中看出基本冒泡排序可以優化的地方了嗎？】下面先來基本實現代碼。

• java實現冒泡排序：

  private?static?<T?extends?Comparable<??super?T>>?void?bubbleSort(T[]?nums)?{
  ??????if?(null?==?nums?||?nums.length?==?0)?{
  ??????????throw?new?RuntimeException("數組為null或長度為0");
  ??????}
  ??????T?temp?=?null;
  ??????int?length?=?nums.length;
  ??????//外循環是趟數，每一趟都會將未排序中最大的數放到尾端
  ??????for?(int?i?=?0;?i?<?length?-?1;?i++)?{
  ??????????//內循環是從第一個元素開始，依次比較相鄰元素，
  ??????????//?比較次數隨著趟數減少，因為每一趟都排好了一個元素
  ??????????for?(int?j?=?0;?j?<?length?-?1?-?i;?j++)?{
  ??????????????if?(nums[j].compareTo(nums[j?+?1])?>?0)?{
  ??????????????????temp?=?nums[j];
  ??????????????????nums[j]?=?nums[j?+?1];
  ??????????????????nums[j?+?1]?=?temp;
  ??????????????}
  ??????????}
  ??????}
  ??}
  

從表格中，相信小伙伴已經看出，在第5趟其實已經排好序了，但基本的冒泡排序算法還會進行第7趟比較，這其實只是進行沒必要的比較，而不會進行元素的交換。（第6趟還是必須要走的，下面會說明）

• 時間、空間復雜度及穩定性分析：

時間復雜度：由于內外循環都發生N次迭代，所以時間復雜度為O(n^2)。并且這個界是精確的。思考最壞的情況，輸入一個逆序的數組，則比較次數為：

(N-1)+(N-2)+(N-3)+..+2+1 = n*(n-1)/2 = O(n^2)

空間復雜度：只使用了一個臨時變量，所以為O(1)；

是否穩定：穩定排序

二、優化冒泡排序

? 我們換個角度看待這個問題。基本冒泡算法之所以進行了無用的多余掃描，是因為不知道已經排好了序；所以只要我們在第 i 趟（i小于N-1）就知道序列已經排好序，我們就不用進行之后的掃描了。

綜上所述，我們可以增加一個boolean變量，來標識是否已經排好序。優化代碼如下：

冒泡排序優化普通版：

????private?static?<T?extends?Comparable<??super?T>>?void?bubbleSort(T[]?nums)?{
????????if?(null?==?nums?||?nums.length?==?0)?{
????????????throw?new?RuntimeException("數組為null或長度為0");
????????}

????????T?temp?=?null;
????????int?length?=?nums.length;
????????//用于標識是否已經將序列排好序
????????boolean?isOrdered?=?false;
????????for?(int?i?=?0;?i?<?length?-?1;?i++)?{
????????????//每一趟開始前都假設已經有序
????????????isOrdered?=?true;
????????????for?(int?j?=?0;?j?<?length?-?1?-?i;?j++)?{
????????????????if?(nums[j].compareTo(nums[j?+?1])?>?0)?{
????????????????????temp?=?nums[j];
????????????????????nums[j]?=?nums[j?+?1];
????????????????????nums[j?+?1]?=?temp;
????????????????????//如果出現有元素交換，則表明此躺可能沒有完成排序
????????????????????isOrdered?=?false;
????????????????}
????????????}
????????????//如果當前趟都沒有進行元素的交換，證明前面一趟比較已經排好序
????????????//直接跳出循環
????????????if?(isOrdered)?{
????????????????break;
????????????}
????????}
????}

注意：雖然第5趟已經排好序，但對于程序來說，它并不知道此趟已經排好序，需要進行下一趟掃描來確定上一趟是否已經將原序列排好序。所以第6趟是必須要去掃描的。

你以為結束了嗎？還沒有，這只是第一版優化。

讓我們想一想這樣的情況。對于下列序列，前半部分亂序，后半部分有序。

原序列45326789

第一趟	4	3	2	5	6	7	8	9
第二趟	3	2	4	5	6	7	8	9
第三趟	2	3	4	5	6	7	8	9

簡述排序過程：

第一趟：發生交換的是5和3，接著是5和2；隨后5與6比較，不需要換位置，相同地，6與7、7與8、8與9都不需要更換位置。所以第一趟結果為：[4,3,2,5,6,7,8,9]。

第二趟：發生交換的是4與3，接著4與2；隨后4與5、5與6，6與7、7與8都不需要更換位置。【8不需要與9比較，因為第一趟已經將最大的數下沉到尾端】。所以第二趟結果為：[3,2,4,5,6,7,8,9]。

第三趟：發生交換的是3與2；隨后3與4，4與5，5與6，6與7都不需要更換位置。所以第三趟結果為：[2,3,4,5,6,7,8,9]。

大家看出什么了嗎？其實進行了很多無意義的比較，因為這些都不需要更換位置，而很多趟都會重復比較。根據冒泡排序思想，我們知道，有序序列長度，其實跟排序趟數相等，每一趟就是將當前亂序中的最大值下沉到數組尾端。但其實序列真正有序的序列長度是大于當前排序趟數的。也就是說，只要我們找到了原序列中無序與有序的邊界，就可以避免再去比較有序序列。

其實最后一次交換的位置，就是無序序列與有序序列的邊界。

從例子中看：

第一趟最后一次交換的位置是元素5與2交換的位置，即數組下標2的位置；

第二趟最后一次交換的位置是元素4與2交換的位置，即數組下標1的位置；

第三趟最后一次交換的位置是元素3與2交換的位置，即數組下標0的位置；

所以，只要我們記錄下當前趟最后一次交換的位置，在下一趟只比較到這個位置即可。

冒泡排序優化加強版：

????private?static?<T?extends?Comparable<??super?T>>?void?bubbleSort(T[]?nums)?{
????????if?(null?==?nums?||?nums.length?==?0)?{
????????????throw?new?RuntimeException("數組為null或長度為0");
????????}

????????T?temp?=?null;
????????int?length?=?nums.length;
????????boolean?isOrdered?=?false;
????????int?lastExchangeIndex?=?0;
????????//當前趟無序的邊界
????????int?unorderedBorder?=?length?-?1;
????????for?(int?i?=?0;?i?<?length?-?1;?i++)?{
????????????//每一趟開始前都假設已經有序
????????????isOrdered?=?true;
????????????for?(int?j?=?0;?j?<?unorderedBorder;?j++)?{
????????????????if?(nums[j].compareTo(nums[j?+?1])?>?0)?{
????????????????????temp?=?nums[j];
????????????????????nums[j]?=?nums[j?+?1];
????????????????????nums[j?+?1]?=?temp;
????????????????????//如果出現有元素交換，則表明此躺沒有完成排序
????????????????????isOrdered?=?false;
????????????????????//記錄下最后一次交換元素的位置
????????????????????lastExchangeIndex?=?j;
????????????????}
????????????}
????????????unorderedBorder?=?lastExchangeIndex;
????????????if?(isOrdered)?{
????????????????break;
????????????}
????????}
????}

其實，還可以進一步優化， 有興趣的可以去看看雞尾酒排序，我們已經很接近了。

三、總結

? 冒泡排序可以通過增加boolean標識是否已經排好序來進行優化；還可以記錄下最后一次交換元素的位置來進行優化，防止無意義的比較。冒泡排序是穩定排序，時間復雜度為O(n^2)，空間復雜度為O(1)。

轉載于:https://www.cnblogs.com/hhthtt/p/10707521.html

總結

以上是生活随笔為你收集整理的如何优化冒泡排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。