泡泡排序(Bubble Sort) - 寫點科普Kopuchat

泡泡排序(Bubble Sort) 的原理、虛擬碼、程式碼與時間複雜度分析。

跳至內容 程式教學>演算法筆記 內容目錄 虛擬碼 程式碼 時間複雜度 空間複雜度:O(1) 穩定性:Stable 程式教學>演算法筆記 內容目錄 虛擬碼 程式碼 時間複雜度 空間複雜度:O(1) 穩定性:Stable 由左而右、兩兩比較相鄰資料，若前者大於後者，則將兩者交換來完成排序。

當資料個數為n時，比較過程將分成n-1回合。

第i回合會將第i大的資料像泡泡一樣浮現在由右數回來的第i個位置。

比如A[4]={2,4,7,3}，第1回合要把第1大的數字7排序： Pass1:4,2,7,3 Pass2:2,4,7,3 Pass3:2,4,7,3 Pass4:2,4,3,7 如果某回合過程中完全沒有發生交換，則代表排序完成，後面回合也無須再進行。

虛擬碼 BubbleSort(A,n)//排序A[1]到A[n] fori=1to(n-1)do flag=0//表示有無交換發生 forj=1to(n-i)do ifA[j]>A[j+1]then swapA[j]andA[j+1] flag=1 endif if(flag==0)thenExit; endfor endfor   程式碼 #include voidswap(int*a,int*b){ inttemp; temp=*a; *a=*b; *b=temp; } intbubble_sort(intA[],intn){ inti,j,flag; for(i=0;iA[j+1]){ swap(&A[j],&A[j+1]); flag=1; } } if(flag==0)break;//此回合沒有發生交換 } } intmain(){ intcount,i; scanf("%d",&count); intlist[count]; printf("Numberstobesorted:"); for(i=0;iO(n)   2.WorstCase:O(n2) inputdata反序由大到小呈現。

input:n,n-1,n-2,...,2,1交換次數 ------------------------------------------------------ Pass1:(n-1),(n),n-2,...,1,nn-1次 Pass2:(n-2),(n-3),...,1,n-1,nn-2次 Pass3:(n-3),(n-4),...,1,n-2,n-1,nn-3次 ... Pass(n-1):1,2,...,n-1,n1次 Total=(n-1)+(n-2)+...+1 =n(n-1)/2次 =>O(n^2) 改用RecursiveTimeFunction來解： T(n)=(n-1)+T(n-1),T(1)=0//O(n)為Pass1之平均交換時間 =T(n-2)+(n-2)+(n-1) =T(n-2)+c*((n-1)+n) =... =T(1)+1+2+...+(n-1) =n(n-1)/2 =>O(n^2)   3.AverageCase:O(n2) T(n)=O(n)+T(n-1),T(1)=0//O(n)為Pass1之平均交換時間 T(n) =T(n-1)+c*n,c為正常數 =T(n-2)+c*((n-1)+n) =... =T(1)+c*(2+...+n) =c*(n+2)(n-1)/2 =>O(n^2)   空間複雜度:O(1) 需要一個額外的空間儲存temp變數來做交換。

  穩定性:Stable inputdata:...,5,5*,... Pass1:...,5,5*,... 由於5並不大於5*，交換不發生、仍維持原順序，故為StableSorting。

文章導覽 ←上一篇文章下一篇文章→ 上一頁上一集 下一集下一篇 本系列完整集數 第一集：簡單的演算法筆記第二集：二元樹(BinaryTree)基礎第三集：搜尋與排序(Search&Sort)第四集：選擇排序(SelectionSort)第五集：泡泡排序(BubbleSort)第六集：合併排序(MergeSort)第七集：希爾排序(ShellSort)第八集：插入排序(InsertionSort)第九集：實作Graph與DFS、BFS圖形走訪演算法第十集：快速排序(QuickSort)第十一集：遞迴(Recursive)介紹與經典題型 專筆於科技史。

瞭解產業的運行規則，保有好奇、推理與觀察力的敏銳。

關於我們 創站目標 深度分析 熱門產業 半導體 通訊 雲端運算 美股SaaS 金融 遊戲 聯絡我們 Email Facebook Instagram 訂閱免費通知 Leavethisfieldemptyifyou'rehuman: Copyright©2021寫點科普Kopuchat 常見問題 服務條款 隱私政策 理念 產業研究樹選單收合 軟體資訊選單收合 雲端運算 美股SaaS 行動App 數位行銷 硬體製造選單收合 半導體 記憶體 通訊 電腦科學選單收合 電腦起源 IC原理 人工智慧 程式教學 其他產業選單收合 金融 遊戲 精品時尚 會員限定分析選單收合 訂閱寫點週報 往期寫點週報 我的帳號 會員登入會員登入 立即訂閱立即訂閱 搜尋了： 本網站使用Cookie及其他相關技術分析以確保使用者獲得最佳體驗，通過我們的網站，您確認並同意本網站的隱私權政策更新。

了解最新隱私權政策。

我知道了Manageconsent Close PrivacyOverview Thiswebsiteusescookiestoimproveyourexperiencewhileyounavigatethroughthewebsite.Outofthese,thecookiesthatarecategorizedasnecessaryarestoredonyourbrowserastheyareessentialfortheworkingofbasicfunctionalitiesofthewebsite.Wealsousethird-partycookiesthathelpusanalyzeandunderstandhowyouusethiswebsite.Thesecookieswillbestoredinyourbrowseronlywithyourconsent.Youalsohavetheoptiontoopt-outofthesecookies.Butoptingoutofsomeofthesecookiesmayaffectyourbrowsingexperience. Necessary Necessary AlwaysEnabled Necessarycookiesareabsolutelyessentialforthewebsitetofunctionproperly.Thesecookiesensurebasicfunctionalitiesandsecurityfeaturesofthewebsite,anonymously. CookieDurationDescriptioncookielawinfo-checkbox-analytics11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookieisusedtostoretheuserconsentforthecookiesinthecategory"Analytics".cookielawinfo-checkbox-functional11monthsThecookieissetbyGDPRcookieconsenttorecordtheuserconsentforthecookiesinthecategory"Functional".cookielawinfo-checkbox-necessary11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookiesisusedtostoretheuserconsentforthecookiesinthecategory"Necessary".cookielawinfo-checkbox-others11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookieisusedtostoretheuserconsentforthecookiesinthecategory"Other.cookielawinfo-checkbox-performance11monthsThiscookieissetbyGDPRCookieConsentplugin.Thecookieisusedtostoretheuserconsentforthecookiesinthecategory"Performance".viewed_cookie_policy11monthsThecookieissetbytheGDPRCookieConsentpluginandisusedtostorewhetherornotuserhasconsentedtotheuseofcookies.Itdoesnotstoreanypersonaldata. Functional Functional Functionalcookieshelptoperformcertainfunctionalitieslikesharingthecontentofthewebsiteonsocialmediaplatforms,collectfeedbacks,andotherthird-partyfeatures. Performance Performance Performancecookiesareusedtounderstandandanalyzethekeyperformanceindexesofthewebsitewhichhelpsindeliveringabetteruserexperienceforthevisitors. Analytics Analytics Analyticalcookiesareusedtounderstandhowvisitorsinteractwiththewebsite.Thesecookieshelpprovideinformationonmetricsthenumberofvisitors,bouncerate,trafficsource,etc. Advertisement Advertisement Advertisementcookiesareusedtoprovidevisitorswithrelevantadsandmarketingcampaigns.Thesecookiestrackvisitorsacrosswebsitesandcollectinformationtoprovidecustomizedads. Others Others Otheruncategorizedcookiesarethosethatarebeinganalyzedandhavenotbeenclassifiedintoacategoryasyet. SAVE&ACCEPT