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

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

冒泡排序 维基百科，自由的百科全书 跳到导航 跳到搜索 此条目没有列出任何参考或来源。

(2020年6月13日)维基百科所有的内容都应该可供查证。

请协助补充可靠来源以改善这篇条目。

无法查证的内容可能会因为异议提出而移除。

冒泡排序使用冒泡排序为一列数字进行排序的过程概况类别排序算法数据结构数组复杂度平均时间复杂度 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相关变量的定义 冒泡排序 冒泡排序（英语：BubbleSort）又称为泡式排序，是一种简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对 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