冒泡排序法
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(n?)表示當n很大的時候,複雜度約等於Cn?,C是某個常數,簡單說就是當n夠大的時候,隨著n的線性增長複雜度將沿平方增長。
O(n)表示,n很大的時候複雜度約等於Cn,C是某個常數。簡言之:隨著n的線性增長,複雜度沿著線性等級增長。
O(1)表示,n很大的時候,複雜度基本上就不成長了。簡言之:隨著n的線性增長,複雜度不受n的影響,沿常數級別增長(此處的常數為1)。
Tips:圖中O(1)緊貼X軸,並看不太清楚。
Tips:此圖來自「Stack Overflow」網站。
相關文章連結
選擇排序法
開開心心每一天
生活艱辛,程式碼不易,但,不要忘記微笑!
以上是冒泡排序法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

Python和JavaScript在性能和效率方面的差異主要體現在:1)Python作為解釋型語言,運行速度較慢,但開發效率高,適合快速原型開發;2)JavaScript在瀏覽器中受限於單線程,但在Node.js中可利用多線程和異步I/O提升性能,兩者在實際項目中各有優勢。

JavaScript起源於1995年,由布蘭登·艾克創造,實現語言為C語言。 1.C語言為JavaScript提供了高性能和系統級編程能力。 2.JavaScript的內存管理和性能優化依賴於C語言。 3.C語言的跨平台特性幫助JavaScript在不同操作系統上高效運行。

JavaScript在瀏覽器和Node.js環境中運行,依賴JavaScript引擎解析和執行代碼。 1)解析階段生成抽象語法樹(AST);2)編譯階段將AST轉換為字節碼或機器碼;3)執行階段執行編譯後的代碼。

Python和JavaScript的未來趨勢包括:1.Python將鞏固在科學計算和AI領域的地位,2.JavaScript將推動Web技術發展,3.跨平台開發將成為熱門,4.性能優化將是重點。兩者都將繼續在各自領域擴展應用場景,並在性能上有更多突破。

Python和JavaScript在開發環境上的選擇都很重要。 1)Python的開發環境包括PyCharm、JupyterNotebook和Anaconda,適合數據科學和快速原型開發。 2)JavaScript的開發環境包括Node.js、VSCode和Webpack,適用於前端和後端開發。根據項目需求選擇合適的工具可以提高開發效率和項目成功率。

是的,JavaScript的引擎核心是用C語言編寫的。 1)C語言提供了高效性能和底層控制,適合JavaScript引擎的開發。 2)以V8引擎為例,其核心用C 編寫,結合了C的效率和麵向對象特性。 3)JavaScript引擎的工作原理包括解析、編譯和執行,C語言在這些過程中發揮關鍵作用。

JavaScript是現代網站的核心,因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容,2)通過DOMAPI操作網頁,3)支持複雜的交互效果如動畫和拖放,4)優化性能和最佳實踐提高用戶體驗。

C 和JavaScript通過WebAssembly實現互操作性。 1)C 代碼編譯成WebAssembly模塊,引入到JavaScript環境中,增強計算能力。 2)在遊戲開發中,C 處理物理引擎和圖形渲染,JavaScript負責遊戲邏輯和用戶界面。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

SAP NetWeaver Server Adapter for Eclipse
將Eclipse與SAP NetWeaver應用伺服器整合。

Atom編輯器mac版下載
最受歡迎的的開源編輯器

SecLists
SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

禪工作室 13.0.1
強大的PHP整合開發環境

EditPlus 中文破解版
體積小,語法高亮,不支援程式碼提示功能