導航:首頁 > 源碼編譯 > 排序演算法掌握幾個

排序演算法掌握幾個

發布時間:2025-06-18 16:46:12

1. 線性時間復雜度(O(n))的排序演算法小結

目前我掌握的線性時間復雜度(O(n))的排序演算法有三個: 計數排序, 基數排序, 桶排序.

計數排序, 適用於小范圍的整數型元素的數組排序, 其原理是對各個元素值統計頻次, 然後從小到大掃描, 將各個元素值重復若干次. 比如對序列進行排序, 可以得到最終的排序結果: 0, 1,1,1,2,2,3,3,3,3,3,4. 計數排序的優點是非常簡單, O(n)中的常數項會非常小, 但缺點是如果元素值范圍非常大, 那麼幾乎不會出現重復的元素, 造成效率低下, 且也開不了這么大(10^16)的數組用於計數, 如果元素值是浮點數的話, 也幾乎不會出現兩個相等的元素.

基數排序的原理非常類似於人類對數字大小的理解, 即依次觀察每一位. 以數組為例, 先按照個位數, 分別將那些數字安放在10個桶裡面, 然後從左到右, 將那些數字拿出來, 接下里, 基於十位數(如果數字小於10, 那麼補零), 做類似的事情, 因為最大數字最多隻有2位數字, 因此, 排序結束了. 思考一下這個過程的原理, 最高位對數字大小的影響最大, 因此, 必須放在最後一步, 位越高, 對數字大小的影響越大, 因此, 演算法的順序必須是從低位到高位.

分桶排序類似於直方圖, 直方圖裡面的一個方塊是一個"桶". 比如數值范圍在0到10, 如果均勻分成10個桶的話, 每個桶的區間為[0, 1), [1, 2), [2, 3),....,[9, 10), 如果元素為0.5, 那麼將0.5放在區間[0, 1). 很明顯, 落在右邊桶的元素要比落在左邊桶的元素更大. 而落在同一個桶裡面的元素, 相互之間無法比較大小. 如果桶的個數足夠多, 那麼每個桶裡面的元素個數就比較少了, 桶內元素使用基於比較的排序演算法進行排序(時間復雜度為N*log(N)). 最後從左到右, 從桶里取出元素, 完成了排序.

總結: 計數排序適用於小范圍的整數型元素的數組排序, 基數排序適用於整數型元素, 不怕數值范圍太大, 這點要比計數排序強, 分桶排序可以用在浮點型元素(當然, 也可以用於整數型元素).

2. 大學里程序員必須掌握的核心演算法

程序員必須掌握的核心演算法

十大排序演算法

簡單排序插入排序、

選擇排序、冒泡排序(必學)

分治排序:快速排序、歸並排序(必學,快速排序還要關注中軸的選取方式)

分配排序桶排序、基數排序

樹狀排序:堆排序(必學)

其他:計數排序(必學)、希爾排序

圖論演算法

圖的表示:鄰接矩陣和鄰接表

遍歷演算法:深度搜索和廣度搜索(必學)

最短路徑演算法:FLOYD,DIJKSTRA(必學)

最小生成樹演算法:PRIM,KRUSKAL(必學)

實際演算法:關鍵路徑、拓抖排序(原理與應用)

二分圖匹配:配對、匈牙利演算法(原理與應用)

拓展:中心性演算法、社區發現演算法(原理與應用)

搜索與回溯演算法

貪心演算法(必學)

信發式搜索演算法:A*尋路演算法(了解)

地圖著色演算法、N皇後問題、最優加工順序旅行商問題

動態規劃

樹形DP:01背包問題

線性DP:最長公共千序列、最長公共子串

區間DP:矩陣最大值(和以及積)

數位DP:數字游戲

狀態壓縮DP:旅行商

字元匹配演算法

正則表達式

模式匹配:KMP、BOYER-MOORE

流相關演算法

最大流:最短增廣路、DINIC演算法

最大流最小割:最大收盆問題、方格取數問題

最小費用最大流:最小費用路、消遣

3. 程序員必須掌握的核心演算法

程序員掌握核心演算法,還不收錄

1、十大排序演算法

(1)簡單排序:插入排序、選擇排序、冒泡排序(必學)。

(2)分治排序:快速排序、歸並排序(必學,快速排序還要關注中軸的選取方式)。

(3)分配排序:桶排序、基數排序。

(4)樹狀排序:堆排序(必學)。

(5)其他:計數排序(必學)、希爾排序。

對干十大演算法的學習,假如你不大懂的話,那麼推薦你去看書,因為看了書,你可能不僅僅知道這個演算法怎麼寫,還能知道他是怎麼來的。推薦書籍是《演算法第四版》,這本書講的很詳細,而且配了很多圖演示,還是挺好懂的。

2、搜索與回溯演算法

(1)貪心演算法(必學);

(2)啟發式搜索演算法:A*尋路演算法(了解);

(3)地圖著色演算法、N 皇後問題、最優加工順序;

(4)旅行商問題。

這方便的只是都是一些演算法相關的,像貪心演算法的思想,就必須學的了。建議通過刷題來學習,leetcode 直接專題刷。

3、動態規劃

(1)樹形DP:01背包問題;

(2)線性DP:最長公共子序列、最長公共子串;

(3)區間DP:矩陣最大值(和以及積);

(4)數位DP:數字游戲;

(5)狀態壓縮DP:旅行商。

這里建議先了解動態規劃是什麼,之後 leetcode專題刷,反正就一般上面這幾種題型。

4、字元匹配演算法

(1)正則表達式;

(2)模式匹配:KMP、Boyer-Moore。

5、流相關演算法

(1)最大流:最短增廣路、Dinic 演算法。

(2)最大流最小割:最大收益問題、方格取數問題。

(3)最小費用最大流:最小費用路、消遣。

4. 10種排序演算法

排序演算法是《數據結構與演算法》中最基本的演算法之一。

排序演算法可以分為內部排序和外部排序,內部排序是數據記錄在內存中進行排序,而外部排序是因排序的數據很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序演算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。用一張圖概括:

點擊以下圖片查看大圖:

關於時間復雜度

平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸並排序;

O(n1+§)) 排序,§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序,此外還有桶、箱排序。

關於穩定性

穩定的排序演算法:冒泡排序、插入排序、歸並排序和基數排序。

不是穩定的排序演算法:選擇排序、快速排序、希爾排序、堆排序。

名詞解釋:

n:數據規模 k:"桶"的個數 In-place:佔用常數內存,不佔用額外內存 Out-place:佔用額外內存 穩定性:排序後 2 個相等鍵值的順序和排序之前它們的順序相同

包含以下內容:

1、冒泡排序 2、選擇排序 3、插入排序數搭 4、希爾排序 5、歸並排序 6、快速排序 7、堆排序 8、計數排序 9、桶排序 10、基數排序

排序演算法包含的相關內容具體如下:

冒泡排序演算法

冒泡排序(Bubble Sort)也是一種簡單直觀的排序演算法。它重復地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該薯畝拿數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢"浮"到數列的頂端。

選擇排序演算法

選擇排序是一種簡單直觀的排序演算法,耐差無論什麼數據進去都是 O(n?) 的時間復雜度。所以用到它的時候,數據規模越小越好。唯一的好處可能就是不佔用額外的內存空間。

插入排序演算法

插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴,但它的原理應該是最容易理解的了,因為只要打過撲克牌的人都應該能夠秒懂。插入排序是一種最簡單直觀的排序演算法,它的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。

希爾排序演算法

希爾排序,也稱遞減增量排序演算法,是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序演算法。

歸並排序演算法

歸並排序(Merge sort)是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。

快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下,排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他 Ο(nlogn) 演算法更快,因為它的內部循環(inner loop)可以在大部分的架構上很有效率地被實現出來。

堆排序演算法

堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或者大於)它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。

計數排序演算法

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序,計數排序要求輸入的數據必須是有確定范圍的整數。

桶排序演算法

桶排序是計數排序的升級版。它利用了函數的映射關系,高效與否的關鍵就在於這個映射函數的確定。

基數排序演算法

基數排序是一種非比較型整數排序演算法,其原理是將整數按位數切割成不同的數字,然後按每個位數分別比較。由於整數也可以表達字元串(比如名字或日期)和特定格式的浮點數,所以基數排序也不是只能使用於整數。

5. 大學要學會這8種演算法程序員

程序員8條程序演算法必須掌握

演算法一: 快速排序演算法

快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下,排序n個項目要O(nlogn)次比較。在最壞狀況下則需要O(n2)次比較,但這種狀況並不常見。事實上,快速排序通常明顯比其他O(nlogn)演算法更快,因為它的內部循環 (innerloop)可以在大部分的架構上很有效率地被實現出來。快速排序使用分治法(Divideandconquer)策略來把一個串列(list)分為兩個子串列(sub-lists)。

演算法二: 堆排序演算法

堆排序(Heapsort)是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小干(或者大幹)它的父節點。堆排序的平均時間復雜度為O(nlogn)。

演算法步驟:

1.創建一個堆H[0.n-1]

2.把堆首(最大值)和堆尾互換

3.把堆的尺寸縮小1,並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置4.重復步驟2,直到堆的尺寸為1

演算法三: 歸並排序

歸並排序(Mergesort,台灣譯作: 合並排序)是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法(DivideandConquer)的一個非常典型的應用。

演算法步驟:

1.申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合並後的序列

2.設定兩個指針,最初位置分別為兩個已經排序序列的起始位置

3.比較兩個指針所指向的元素,選擇相對小的元素放入到合並空間,並移動指針到下一位置4.重復步驟3直到某一指針達到序列尾5.將另一序列剩下的所有元素直接復制到合並序列尾

演算法四: 二分查找演算法二分查找演算法

是一種在有序數組中查找某一特定元素的搜索演算法。

搜素過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜素過程結束:如果某一特定元素大幹或者小干中間元素,則在數組大於或小千中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空,則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半,時間復雜度為O(logn)

如果在某一步驟數組為空,則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半,時間復雜度為O(logn) 。

演算法五: BFPRT(線性查找演算法)

BFPRT演算法解決的問題十分經典,即從某n個元素的序列中選出第k大(第k小)的元素,通過巧妙的分析BFPRT可以保證在最壞情況下仍為線性時間復雜度該演算法的思想與快速排序思想相似,當然,為使得演算法在最壞情況下,依然能達到o(n)的時間復雜度,五位演算法作者做了精妙的處理。

演算法六: DFS(深度優先搜索)

深度優先搜索演算法(Depth-First-Search),是搜索演算法的一種。它沿著樹的深度遍歷樹的節點,盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過,搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。

如果還存在未被發現的節點,則選擇其中一個作為源節點並重復以上過程,整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。深度優先搜索是圖論中的經典演算法,利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表,利用拓撲排序表可以方便的解決很多相關的圖論問題,如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。

演算法七: BFS廣度優先搜索演算法

(Breadth-First-Search),是一種圖形搜索演算法。簡單的說,BFS是從根節點開始,沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問,則演算法中止BFS同樣屬干盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。

演算法步驟:

1.首先將根節點放入隊列中。

2.從隊列中取出第一個節點,並檢驗它是否為目標。如果找到目標,則結束搜尋並回傳結果。否則將它所有尚未檢驗過的直接子節點加入隊列中。

3.若隊列為空,表示整張圖都檢查過了一一亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」4.重復步驟2。

演算法八: 動態規劃演算法

動態規劃(Dynamicprogramming)是一種在數學、計算機科學和經濟學中使用的,通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。動態規劃常常適用干有重疊子問題和最優子結構性質的問題,動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上,若要解一個給定問題,我們需要解其不同部分(即子問題),再合並子問題的解以得出原問題的解。通常許多子問題非常相似,為此動態規劃法試圖僅僅解決每個子問題一次,從而減少計算量:一旦某個給定子問題的解已經算出,則將其記憶化存儲,以便下次需要同一個子問題解之時直接查表。



閱讀全文

與排序演算法掌握幾個相關的資料

熱點內容
郵政app怎麼查詢轉賬憑證 瀏覽:836
程序員語言閱讀 瀏覽:867
程序員考哪些證可以拿錢 瀏覽:867
發貨商庫存清點編程 瀏覽:718
app圖標名字變了怎麼回事 瀏覽:719
如何搭建流媒體伺服器 瀏覽:277
360照片加密軟體 瀏覽:640
電腦c語言編譯器正版 瀏覽:551
安卓手機屏幕亂彈怎麼回事 瀏覽:989
app怎麼自動關注 瀏覽:662
西門子st編程 瀏覽:550
java實現圖像分割演算法 瀏覽:12
寧波海曙四軸編程培訓先學什麼 瀏覽:116
jacob源碼 瀏覽:237
安卓手機屏幕壞了如何修 瀏覽:394
10匹三洋壓縮機 瀏覽:718
管車寶app怎麼樣 瀏覽:255
劍橋雅思全解pdf 瀏覽:510
酷狗音樂bmp解壓 瀏覽:467
程序員哪有那麼可愛漫畫觀看 瀏覽:605