1. 排序演算法總結
排序演算法是什麼?有多少種?排序演算法總結又是怎樣?以下是為您整理的排序演算法總結,供您參考!
排序演算法:一種能將一串數據依照特定的排序方式進行排列的一種演算法。
排序演算法性能:取決於時間和空間復雜度,其次還得考慮穩定性,及其適應的場景。
穩定性:讓原本有相等鍵值的記錄維持相對次序。也就是若一個排序演算法是穩定的,當有倆個相等鍵值的記錄R和S,且原本的序列中R在S前,那麼排序後的列表中R應該也在S之前。
以下來總結常用的排序演算法,加深對排序的理解。
冒泡排序
原理
倆倆比較相鄰記錄的排序碼,若發生逆序,則交旅派配換;有倆種方式進行冒泡,一種是先把小的冒泡到前邊去,另一種是把大的元素冒泡到後邊。
性能
時間復雜度為O(N^2),空間復雜度為O(1)。排序是穩定的,排序比較次數與初始序列無關,但交換次數與初始序列有關。
優化
若初始序列就是排序好的,對於冒泡排序仍然還要比較O(N^2)次,但無交換次數。可根據這個進行優化,設置一個flag,當在一趟序列中沒有發生交換,則該序列已排序好,但優化後排序的時間復雜度沒有發生量級的改變。
代碼
插入排序
原理
依次選擇一個待排序的數據,插入到前邊已排好序的序列中。
性能
時間復雜度為O(N^2),空間復雜度為O(1)。演算法是穩定的,比較次數和交換次數都與初始序列有關。
優化
直接插入排序每次往前插入時,是按順序依次往前找,可在這里進行優化,往前找合適的插入位置時採用二分查找的方式,即折半插入。
折半插入排序相對直接插入排序而言:平均性能更快,時間復雜度降至O(NlogN),排序是穩定的,但排序的比較次數與初始序列無關,總是需要foor(log(i))+1次排序比較。
使用場景
當數據基本有序時,採用插入排序可以明顯減少數據交換和數據移動次數,進而提升排序效率。
代碼
希爾排拆指序
原理
插入排序的改進版,是基於插入排序的以下倆點性質而提出的改進方法:
插入排序對幾乎已排好序的數據操作時,效率很高,可以達到線性排序的效率。
但插入排序在每次往前插入時只能將數據移動一位,效率比較低。
所以希爾排序的思想是:
先是取一個合適的gap
縮小間隔gap,例如去gap=ceil(gap/2),重復上述子序列劃分和排序
直到,最後gap=1時,將所有元素放在同一個序列中進行插入排序為止。
性能
開始時,gap取值較大,子序列中的元素較少,排序速度快,克服了直接插入排序的缺點;其次,gap值逐漸變小後,雖然子序列的元素逐漸變多,但大多元素已基本有序,所以繼承了直接插入排序的優點,能以近線性的速度排好序。
代碼
選擇排序
原理
每次從未排序的序列中找到最小值,記錄並最後存放到已排序序羨碰列的末尾
性能
時間復雜度為O(N^2),空間復雜度為O(1),排序是不穩定的(把最小值交換到已排序的末尾導致的),每次都能確定一個元素所在的最終位置,比較次數與初始序列無關。
代碼
快速排序
原理
分而治之思想:
Divide:找到基準元素pivot,將數組A[p..r]劃分為A[p..pivotpos-1]和A[pivotpos+1…q],左邊的元素都比基準小,右邊的元素都比基準大;
Conquer:對倆個劃分的數組進行遞歸排序;
Combine:因為基準的作用,使得倆個子數組就地有序,無需合並操作。
性能
快排的平均時間復雜度為O(NlogN),空間復雜度為O(logN),但最壞情況下,時間復雜度為O(N^2),空間復雜度為O(N);且排序是不穩定的,但每次都能確定一個元素所在序列中的最終位置,復雜度與初始序列有關。
優化
當初始序列是非遞減序列時,快排性能下降到最壞情況,主要因為基準每次都是從最左邊取得,這時每次只能排好一個元素。
所以快排的優化思路如下:
優化基準,不每次都從左邊取,可以進行三路劃分,分別取最左邊,中間和最右邊的中間值,再交換到最左邊進行排序;或者進行隨機取得待排序數組中的某一個元素,再交換到最左邊,進行排序。
在規模較小情況下,採用直接插入排序
代碼
歸並排序
原理
分而治之思想:
Divide:將n個元素平均劃分為各含n/2個元素的子序列;
Conquer:遞歸的解決倆個規模為n/2的子問題;
Combine:合並倆個已排序的子序列。
性能
時間復雜度總是為O(NlogN),空間復雜度也總為為O(N),演算法與初始序列無關,排序是穩定的。
優化
優化思路:
在規模較小時,合並排序可採用直接插入;
在寫法上,可以在生成輔助數組時,倆頭小,中間大,這時不需要再在後邊加倆個while循環進行判斷,只需一次比完。
代碼
堆排序
原理
堆的性質:
是一棵完全二叉樹
每個節點的值都大於或等於其子節點的值,為最大堆;反之為最小堆。
堆排序思想:
將待排序的序列構造成一個最大堆,此時序列的最大值為根節點
依次將根節點與待排序序列的最後一個元素交換
再維護從根節點到該元素的前一個節點為最大堆,如此往復,最終得到一個遞增序列
性能
時間復雜度為O(NlogN),空間復雜度為O(1),因為利用的排序空間仍然是初始的序列,並未開辟新空間。演算法是不穩定的,與初始序列無關。
使用場景
想知道最大值或最小值時,比如優先順序隊列,作業調度等場景。
代碼
計數排序
原理
先把每個元素的出現次數算出來,然後算出該元素所在最終排好序列中的絕對位置(最終位置),再依次把初始序列中的元素,根據該元素所在最終的絕對位置移到排序數組中。
性能
時間復雜度為O(N+K),空間復雜度為O(N+K),演算法是穩定的,與初始序列無關,不需要進行比較就能排好序的演算法。
使用場景
演算法只能使用在已知序列中的元素在0-k之間,且要求排序的復雜度在線性效率上。
代碼
桶排序
原理
根據待排序列元素的大小范圍,均勻獨立的劃分M個桶
將N個輸入元素分布到各個桶中去
再對各個桶中的元素進行排序
此時再按次序把各桶中的元素列出來即是已排序好的。
性能
時間復雜度為O(N+C),O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM),空間復雜度為O(N+M),演算法是穩定的,且與初始序列無關。
使用場景
演算法思想和散列中的開散列法差不多,當沖突時放入同一個桶中;可應用於數據量分布比較均勻,或比較側重於區間數量時。
基數排序
原理
對於有d個關鍵字時,可以分別按關鍵字進行排序。有倆種方法:
MSD:先從高位開始進行排序,在每個關鍵字上,可採用計數排序
LSD:先從低位開始進行排序,在每個關鍵字上,可採用桶排序
性能
時間復雜度為O(d*(N+K)),空間復雜度為O(N+K)。
總結
以上排序演算法的時間、空間與穩定性的總結如下:
2. cpu調度演算法決定了進程執行的順序.若有n個進程需要調度,有多少種可能的調度順
前兩天做操作系統作業的時候學習了一下幾種進程調度演算法,在思考和討論後,有了一些自己的想法,現在就寫出來,跟大家討論下。,或者說只有有限的CPU資源,當系統中有多個進程處於就緒狀態,要競爭CPU資源時,操作系統就要負責完成如何分配資源的任務。在操作系統中,由調度程序來完成這一選擇分配的工作,調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性;按照一定策略強制執行演算法調度;平衡整個計算機系統,盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求,調度演算法又有一些側重點和目標不同,因此,演算法按照系統差異主要分為三大類:批處理系統中的調度演算法,代表調度演算法有:先來先服務、最短作業優先、最短剩餘時間優先。互動式系統中的調度演算法,代表調度演算法有:輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。實時系統中的調度演算法,代表調度演算法有:速率單調調度、最早最終時限優先調度。下面就上述提到的調度演算法中挑出幾個進行重點分析:保證調度保證調度是指利用演算法向用戶做出明確的性能保證,然後盡力按照此保證實現CPU的資源分配。利用這種演算法,就是定一個進程佔用CPU的時間的標准,然後按照這個標准去比較實際佔用CPU的時間,調度進程每次使離此標准最遠的進程得到資源,不斷滿足離所保證的標准最遠的進程,從而平衡資源分配滿足這個標準的要求。保證調度演算法的優點是:能很好的保證進程公平的CPU份額,當系統的特點是:進程的優先順序沒有太大懸殊,所制定的保證標准差異不大,各個進程對CPU的要求較為接近時,比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源,利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是,這種情況太過理想,當系統的各個進程對CPU要求的緊急程度不同,所制定的保證較為復雜的時候,這個演算法實現起來比較困難。彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票,當系統需要做出調度決策時,隨機抽出一張彩票,由此彩票的擁有者獲得資源。在彩票調度系統中,如果有一個新的進程出現並得到一些彩票,那麼在下一次的抽獎中,該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多,則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。彩票調度有很多優點:首先,它很靈活,系統增加分給某個進程的彩票數量,就會大大增加它佔用資源的可能性,可以說,彩票調度的反應是迅速的,而快速響應需求正是互動式系統的一個重要要求。其次,彩票調度演算法中,進程可以交換彩票,這個特點可以更好的保證系統的平衡性,使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題,例如可以根據特定的需要大致成比例的劃分CPU的使用。速率單調調度速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足:每個周期性進程必須在其周期內完成,且進程之間沒有相互依賴的關系,每個進程在一次突發中需要相同的CPU時間量,非周期的進程都沒有最終時限四個條件時,並且為了建模方便,我們假設進程搶占即刻發生沒有系統開銷,可以考慮利用速率單調演算法。速率單調調度演算法是將進程的速率(按照進程周期所算出的每秒響應的次數)賦為優先順序,則保證了優先順序與進程速率成線性關系,這即是我們所說的速率單調。調度程序每次運行優先順序最高的,只要優先順序較高的程序需要運行,則立即搶占優先順序低的進程,而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度,但是缺點是其作為一種靜態演算法,靈活性不夠好,當進程數變多,系統調度變得復雜時,可能不能較好的保證進程在周期內運行。最早最終時限優先調度最早最終時限優先調度演算法是一個動態演算法,不要求進程是周期性的,只要一個進程需要CPU時間,它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表,按最終時限排序,每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時,系統檢查其最終時限是否在當前運行的進程結束之前,如果是,則搶占當前進程。由於是動態演算法,最早最終優先調度的優點就是靈活,當進程數不超過負載時,資源分配更優,但也同樣由於它的動態屬性,進程的優先順序都是在不斷變化中的,所以也沒有哪個進程是一定可以保證滿足調度的,當進程數超過負載時,資源分配合理度會急速下降,所以不太穩定。