冒泡排序- 维基百科，自由的百科全书

冒泡排序（英語：Bubble Sort）又稱為泡式排序，是一種簡單的排序算法。

它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。

泡沫排序 語言 監視 編輯 此條目沒有列出任何參考或來源。

(2020年6月13日)維基百科所有的內容都應該可供查證。

請協助補充可靠來源以改善這篇條目。

無法查證的內容可能會因為異議提出而移除。

泡沫排序（英語：BubbleSort）又稱為泡式排序，是一種簡單的排序演算法。

它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。

走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

泡沫排序使用泡沫排序為一列數字進行排序的過程概況類別排序演算法資料結構數組複雜度平均時間複雜度 O ( n 2 ) {\displaystyleO(n^{2})} 最壞時間複雜度 O ( n 2 ) {\displaystyleO(n^{2})} 最佳時間複雜度 O ( n ) {\displaystyleO(n)} 空間複雜度總共 O ( n ) {\displaystyleO(n)} ，需要輔助空間 O ( 1 ) {\displaystyleO(1)} 最佳解No相關變數的定義泡沫排序 泡沫排序對 n {\displaystylen} 個項目需要O( n 2 {\displaystylen^{2}} )的比較次數，且可以原地排序。

儘管這個演算法是最簡單瞭解和實作的排序演算法之一，但它對於包含大量的元素的數列排序是很沒有效率的。

泡沫排序是與插入排序擁有相等的漸近時間複雜度，但是兩種演算法在需要的交換次數卻很大地不同。

在最壞的情況，泡沫排序需要 O ( n 2 ) {\displaystyleO(n^{2})} 次交換，而插入排序只要最多 O ( n ) {\displaystyleO(n)} 交換。

泡沫排序的實現（類似下面）通常會對已經排序好的數列拙劣地執行（ O ( n 2 ) {\displaystyleO(n^{2})} ），而插入排序在這個例子只需要 O ( n ) {\displaystyleO(n)} 個運算。

因此很多現代的演算法教科書避免使用泡沫排序，而用插入排序取代之。

泡沫排序如果能在內部迴圈第一次執行時，使用一個旗標來表示有無需要交換的可能，也可以把最優情況下的複雜度降低到 O ( n ) {\displaystyleO(n)} 。

在這個情況，已經排序好的數列就無交換的需要。

若在每次走訪數列時，把走訪順序反過來，也可以稍微地改進效率。

有時候稱為雞尾酒排序，因為演算法會從數列的一端到另一端之間穿梭往返。

泡沫排序演算法的運作如下： 比較相鄰的元素。

如果第一個比第二個大，就交換它們兩個。

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。

這步做完後，最後的元素會是最大的數。

針對所有的元素重複以上的步驟，除了最後一個。

持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

由於它的簡潔，泡沫排序通常被用來對於程式設計入門的學生介紹演算法的概念。

目次 1虛擬碼 2助記碼 3實作範例 3.1C語言 3.2C++ 3.3C# 3.4JAVA 3.5Ruby 3.6JavaScript 3.7Pascal 3.8Python 3.9VB.NET 3.10PHP 3.11Rust 3.12Go 3.13Objective-C 3.14Swift 3.15Shell 3.16IDL 4外部連結 虛擬碼編輯 functionbubble_sort(array,length){ vari,j; for(ifrom0tolength-1){ for(jfrom0tolength-1-i){ if(array[j]>array[j+1]) swap(array[j],array[j+1]) } } } 函數泡沫排序輸入一個陣列名稱為array其長度為length i從0到(length-1) j從0到(length-1-i) 如果array[j]>array[j+1] 交換array[j]和array[j+1]的值 如果結束 j迴圈結束 i迴圈結束 函數結束 助記碼編輯 i∈[0,N-1)//循环N-1遍 j∈[0,N-1-i)//每遍循环要处理的无序部分 swap(j,j+1)//两两排序（升序/降序）   實作範例編輯 C語言編輯 #include #include #defineARR_LEN255/*數組長度上限*/ #defineelemTypeint/*元素類型*/ /*泡沫排序*/ /*1.從當前元素起，向後依次比較每一對相鄰元素，若逆序則互換*/ /*2.對所有元素均重複以上步驟，直至最後一個元素*/ /*elemTypearr[]:排序目標數組;intlen:元素個數*/ voidbubbleSort(intarr[],intlen) { inti,j,temp; _Boolexchanged=true; for(i=0;exchanged&&iarr[j+1]) {/*相鄰元素比較，若逆序則互換（升序為左大於右，逆序反之）*/ temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; exchanged=true;/*只有數值互換過,exchanged才會從false變成true,否則數列已經排序完成,exchanged值仍然為false,沒必要排序*/ } } } } intmain(void){ intarr[ARR_LEN]={3,5,1,-7,4,9,-6,8,10,4}; intlen=10; inti; bubbleSort(arr,len); for(i=0;i usingnamespacestd; template//整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符 voidbubble_sort(Tarr[],intlen){ inti,j; for(i=0;iarr[j+1]) swap(arr[j],arr[j+1]); } intmain(){ intarr[]={61,17,29,22,34,60,72,21,50,1,62}; intlen=(int)sizeof(arr)/sizeof(*arr); bubble_sort(arr,len); for(inti=0;iarray[j+1]) { temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } returnarray; } JAVA編輯 privateint[]bubbleSort(int[]array){ inttemp; for(inti=0;iarray[j+1]){ temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; Flag=true; } } if(!Flag) { break; } } returnarray; } Ruby編輯 classArray defbubble_sort! foriin0...(size-1) forjin0...(size-i-1) self[j],self[j+1]=self[j+1],self[j]ifself[j]>self[j+1] end end self end end puts[22,34,3,32,82,55,89,50,37,5,64,35,9,70].bubble_sort! JavaScript編輯 Array.prototype.bubble_sort=function(){ vari,j,temp; for(i=0;ithis[j+1]){ temp=this[j]; this[j]=this[j+1]; this[j+1]=temp; } returnthis; }; varnum=[22,34,3,32,82,55,89,50,37,5,64,35,9,70]; num.bubble_sort(); for(vari=0;ia[j+1]then begin swap(j); flag:=false; end; end; ifflagthenexit; end; end; Python編輯 defbubble_sorted(iterable): new_list=list(iterable) list_len=len(new_list) foriinrange(list_len): forjinrange(list_len-i-1): ifnew_list[j]>new_list[j+1]: new_list[j],new_list[j+1]=new_list[j+1],new_list[j] returnnew_list 範例： testlist=[27,33,28,4,2,26,13,35,8,14] print('sorted:',bubble_sorted(testlist)) 輸出： sorted:[2,4,8,13,14,26,27,28,33,35] VB.NET編輯 '泡沫排序由大到小的程式，預先產生一儲存亂數內容的陣列B，使用中斷點check， 'switch為自定兩數交換的sub Dimi,j,countAsInteger Fori=0ToUBound(b)-1 DimcheckAsBoolean=False'進入排序後設定一布林變數令其初值為false Forj=0ToUBound(b)-1-i Ifb(j)b(j+1)Thenswitch(b(j),b(j+1)) count+=1 check=True Next Ifchk=FalseThenExitFor Next MsgBox("共經過了"&count&"次的排序") '兩數值交換程式 PrivateSubswitch(ByRefaasinteger,ByRefbasinteger) DimcAsInteger c=a a=b b=c EndSub PHP編輯 functionswap(&$x,&$y){ $t=$x; $x=$y; $y=$t; } functionbubble_sort(&$arr){//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列 for($i=0;$i$arr[$j+1]) swap($arr[$j],$arr[$j+1]); } $arr=array(21,34,3,32,82,55,89,50,37,5,64,35,9,70); bubble_sort($arr); for($i=0;$ia[j]{ a.swap(i,j); } } } } 呼叫： letmuta=[5,4,7,1,9]; bubble_sort(&muta); println!("{:?}",a); Go編輯 //BubbleSort冒泡排序.data必须实现sort包中的Interface接口 funcBubbleSort(datasort.Interface){ n:=data.Len() fori:=0;i[sortedArray[j+1]integerValue]){ [sortedArrayexchangeObjectAtIndex:jwithObjectAtIndex:j+1]; exchanged=YES; } } if(!exchanged){ break; } } return[sortedArraycopy]; } Swift編輯 funcbubbleSort(unsortedArray:inout[Int]){ guardunsortedArray.count>1else{ return } foriin0..unsortedArray[j+1]{ unsortedArray.swapAt(j,j+1) exchanged=true } } if!exchanged{ break } } } //Test varlist=[2,3,5,7,4,8,6,10,1,9] print(list) bubbleSort(unsortedArray:&list) print(list) Shell編輯 #/bin/bash read-p"Pleaseenterasequence:"-anum for((i=0;i