国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

算法之旅 | 冒泡排序法

qujian / 3515人閱讀

摘要:學堂碼匠本期繼續走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優化假如序列的數據為使用上面的冒泡排序法進行排序,得到的結果肯定沒有問題,但是,待排序的序列是有序的,理論上是無需遍歷排序。

HTML5學堂-碼匠:本期繼續走入算法 —— 冒泡排序法。冒泡排序算法相對簡單,容易上手,穩定性也比較高,
算是一種較好理解的算法,也是面試官高頻提問的算法之一。

Tips:關于“算法”及“排序”的基礎知識,在此前“選擇排序法”中已詳細講解,可點擊文后的相關文章鏈接查看,在此不再贅述。

冒泡排序法的原理 基本原理

從序列頭部開始遍歷,兩兩比較,如果前者比后者大,則交換位置,直到最后將最大的數(本次排序最大的數)交換到無序序列的尾部,從而成為有序序列的一部分;
下次遍歷時,此前每次遍歷后的最大數不再參與排序;
多次重復此操作,直到序列排序完成。
由于在排序的過程中總是小數往前放,大數往后放,類似于氣泡逐漸向上漂浮,所以稱作冒泡排序。

原理圖解

Tips:藍色代表在一輪排序中等待交換,黑色代表在該輪排序中已交換完成,紅色代表已排序完成

實現冒泡的步驟分解 使用for循環確定排序次數

由于待排序的序列只剩下一個數時已經能夠確定順序,則無需進行排序,因此,排序次數為序列長度 – 1。

每次排序的比較次數控制

每次排序,序列中的多個數字要分別進行兩兩比較,多次的比較需要利用for語句來進行實現。該for循環嵌套于排序次數的for循環當中(形成雙for的嵌套)。

Tips:j 需要設置為小于 len - i - 1,減i的原因是已經排序完成的數不再參與比較,減1的原因是數組下標索引值從0開始。

核心功能 — 兩兩比較并根據情況交換位置

比較兩數大小,如果前者比后者大,則進行數值的交換,也就是交換位置。

冒泡排序法完整代碼

冒泡排序法的優化

假如序列的數據為:[0, 1, 2, 3, 4, 5];
使用上面的冒泡排序法進行排序,得到的結果肯定沒有問題,但是,待排序的序列是有序的,理論上是無需遍歷排序。
當前的算法不管初始的序列是否有序,都會進行遍歷排序,效率會比較低,因此需要優化當前的排序算法。
在如下的算法中,引入一個swap變量,每一次排序之前初始化為false;若發生兩數交換位置,則將其設置為true。
在每次排序結束時候判斷swap是否為false,如果是,則說明序列已排序完成或者序列本身是有序序列,就不再進行下一次排序。
通過此方法,減少不必要的比較和位置交換,進一步提高算法的性能。

冒泡排序法的效率 時間復雜度

最佳狀態:待排序的序列本身是有序序列,排序次數根據優化后的代碼,可以得出是n-1次,時間復雜度為O(n);
最壞的情況:待排序的序列是逆序的,此時需要排序1 + 2 +3 ……(n - 1) = n(n – 1 )/2次,
時間復雜度為O(n^2)。

空間復雜度

冒泡排序法需要一個額外空間(temp變量)來交換元素的位置,所以空間復雜度為O(1)。

算法的穩定性

當相鄰元素相等時,并不需要交換位置,也就不會出現相同元素的前后順序發生改變,所以,是穩定性排序。

O是個啥?!

時間復雜度,更準確的說該是描述一個算法在問題規模不斷增大時對應的時間增長曲線。所以,這些增長數量級并不是一個準確的性能評價,可以理解為一個近似值。(空間復雜度同理)
O(n2)表示當n很大的時候,復雜度約等于Cn2,C是某個常數,簡單說就是當n足夠大的時候,隨著n的線性增長復雜度將沿平方增長。
O(n)表示,n很大的時候復雜度約等于Cn,C是某個常數。簡言之:隨著n的線性增長,復雜度沿線性級別增長。
O(1)表示,n很大的時候,復雜度基本就不增長了。簡言之:隨著n的線性增長,復雜度不受n的影響,沿常數級別增長(此處的常數是1)。

Tips:圖中O(1)緊貼著X軸,并看不太清楚。
Tips:該圖來源于“Stack Overflow”網站。

相關文章鏈接

算法之旅 | 選擇排序法

開開心心每一天

生活艱辛,代碼不易,但,不要忘記微笑!

版權聲明:該圖來自“【美】莉茲·克里莫 (author)”的書籍《你今天真好看》

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/85116.html

相關文章

  • 之旅 | 快速排序

    摘要:今天跟大家分享多種排序算法里使用較廣泛,速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序,它采用分治的策略,通常稱其為分治法。 HTML5學堂-碼匠:前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法,它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛,速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...

    AlanKeene 評論0 收藏0
  • 之旅 | 選擇排序

    摘要:由于排序的算法有很多,在本次算法系列的分享當中,我們先從簡單易上手的選擇排序法開始,其它的排序算法會隨后陸續跟大家一起分享。 HTML5學堂-碼匠:數據快速的計算與排序,與前端頁面性能有直接的關系。由于排序的算法有很多,在本次算法系列的分享當中,我們先從簡單易上手的選擇排序法開始,其它的排序算法會隨后陸續跟大家一起分享。 算法的基本概念 算法是什么,它有何作用 為解決一個問題而采取的方...

    liaorio 評論0 收藏0

發表評論

0條評論

qujian

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<