?成長路上不孤單😊😊😊😊😊😊

【😊///計算機愛好者😊///持續(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ù)集。?