網(wǎng)站備案密碼忘做seo需要哪些知識
?成長路上不孤單😊😊😊😊😊😊
【😊///計算機愛好者😊///持續(xù)分享所學😊///如有需要歡迎收藏轉(zhuǎn)發(fā)///😊】
今日分享關(guān)于C++中常用的排序方法之——冒泡排序的相關(guān)內(nèi)容!
關(guān)于【C++中常用的排序方法之——冒泡排序】
目錄:
- 一、?冒泡排序的定義
- 二、冒泡排序的算法原理
- 三、冒泡排序的算法示例
- 四、冒泡排序的算法分析
- 五、冒泡排序的特點
- 六、冒泡排序的優(yōu)點
- 七、冒泡排序的缺點
冒泡排序(Bubble Sort)?
一、冒泡排序的定義
冒泡排序的英文Bubble Sort,是一種最基礎(chǔ)的交換排序。
大家一定都喝過汽水,汽水中常常有許多小小的氣泡,嘩啦嘩啦飄到上面來。這是因為組成小氣泡的二氧化碳比水要輕,所以小氣泡可以一點一點向上浮動。而我們的冒泡排序之所以叫做冒泡排序,正是因為這種排序算法的每一個元素都可以像小氣泡一樣,根據(jù)自身大小,一點一點向著數(shù)組的一側(cè)移動。
??
二、冒泡排序的算法原理
假定序列中有n個數(shù),要進行從小到大的排序。若參與排序的數(shù)組元素共有n個,則需要n-1輪排序。在第í輪排序中,從左端開始,相鄰兩數(shù)比較大小,若反序則將兩者交換位置,直到比較第n+1-i個數(shù)為止。第1個數(shù)與第2個數(shù)比較,第2個數(shù)和第3個數(shù)比較,一直到第n-i個數(shù)與第n+1-i個數(shù)比較,一共處理 n-i次。此時,第n+1-i個位置上的數(shù)已經(jīng)有序,后續(xù)就不需要參加以后的排序。?
(1)第1輪冒泡排序先從第1個數(shù)和第2個數(shù)開始比較,若第1個數(shù)大于第2個數(shù),則需要交換兩者的位置;否則保持不變。重復(fù)這一過程,直到處理完本輪數(shù)列中最后兩個數(shù)。?
(2)第2輪冒泡排序與第1輪冒泡排序進行相同的排序,使大的數(shù)交換到n-2的位置上。?
(3)重復(fù)以上過程,共需經(jīng)過n-1輪冒泡排序后,數(shù)據(jù)實現(xiàn)升序排序。
三、冒泡排序的算法示例
對于序列[26,28,24,11],采用非遞減規(guī)則進行排序,排序過程如下所示。?
??
(1) 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。?
(2) 對每一對相鄰元素做同樣的工作,從開始第一對到結(jié)尾的最后一對。在這一點,最后的元素應(yīng)該會是最大的數(shù)。?
(3) 針對所有的元素重復(fù)以上的步驟,除了最后一個。?
(4) 持續(xù)每次對越來越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對數(shù)字需要比較。
四、冒泡排序的算法分析
1、時間復(fù)雜度
若文件的初始狀態(tài)是正序的,一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)
??
????
若初始文件是反序的,需要進行n-1趟排序。每趟排序要進行n-i?次,關(guān)鍵字的比較(1≤i≤n-1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下,比較和移動次數(shù)均達到最大值:
??
??
2、算法穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較,交換也發(fā)生在這兩個元素之間。所以,如果兩個元素相等,是不會再交換的;如果兩個相等的元素沒有相鄰,那么即使通過前面的兩兩交換把兩個相鄰起來,這時候也不會交換,所以相同元素的前后順序并沒有改變,所以冒泡排序是一種穩(wěn)定排序算法。
五、冒泡排序的特點
??時間復(fù)雜度?:冒泡排序的時間復(fù)雜度為O(n^2)。在最壞的情況下(即初始序列完全逆序),需要進行n(n-1)/2次比較和3n(n-1)/2次移動,時間復(fù)雜度為O(n^2)。在最好的情況下(即初始序列已經(jīng)有序),時間復(fù)雜度為O(n),但這種情況較為罕見。
?空間復(fù)雜度?:冒泡排序是一種就地排序算法,不需要額外的存儲空間,因此空間復(fù)雜度為O(1)。
?穩(wěn)定性?:冒泡排序是一種穩(wěn)定的排序算法,即相同元素的相對位置不會改變。
?適用場景?:由于冒泡排序的時間復(fù)雜度較高,它適用于數(shù)據(jù)量較小的情況。對于大量數(shù)據(jù)的排序,效率較低。
?算法原理?:冒泡排序通過重復(fù)遍歷待排序的數(shù)列,比較兩個相鄰的元素,如果它們的順序錯誤就交換過來。遍歷工作是重復(fù)進行的,直到?jīng)]有再需要交換的元素為止。
?優(yōu)化方法?:可以通過設(shè)置一個標志位來優(yōu)化冒泡排序。如果在一次完整的遍歷中沒有發(fā)生交換,說明數(shù)組已經(jīng)有序,可以直接結(jié)束排序過程。這種方法可以在某些情況下將時間復(fù)雜度降低到O(n)。
六、冒泡排序優(yōu)點
1?、?實現(xiàn)簡單?:冒泡排序的算法邏輯非常簡單,容易理解和實現(xiàn)。它只需要通過重復(fù)遍歷要排序的數(shù)列,比較相鄰元素的值,并在必要時交換它們的位置。
?2、代碼簡潔?:冒泡排序的代碼非常簡潔,不需要復(fù)雜的操作和額外的存儲空間。
3?、原地排序?:冒泡排序是一種原地排序算法,不需要額外的內(nèi)存空間來存儲排序結(jié)果。它直接在原始數(shù)組上進行元素的比較和交換操作。
4?、穩(wěn)定性?:冒泡排序是一種穩(wěn)定的排序算法,即相等元素的相對順序在排序前后保持不變。只有當兩個相鄰元素進行交換時才會改變它們的相對順序。
5?、適用于小規(guī)模數(shù)據(jù)?:在數(shù)據(jù)規(guī)模較小的情況下,冒泡排序的性能還是可以接受的。對于小規(guī)模的數(shù)據(jù)集,冒泡排序可能比其他復(fù)雜的排序算法更快。
七、冒泡排序的缺點?
?1、時間復(fù)雜度高?:冒泡排序的時間復(fù)雜度為O(n^2),在數(shù)據(jù)量較大時效率較低,尤其是當數(shù)據(jù)完全逆序時,時間復(fù)雜度達到O(n^2)。
?2?、不適合大規(guī)模數(shù)據(jù)?:由于其較高的時間復(fù)雜度,冒泡排序不適合處理大規(guī)模數(shù)據(jù)集。?