排序算法總結(jié)-各種排序算法總結(jié)含代碼

1、排序算法總結(jié) | 各種排序算法總結(jié)含代碼【匯總】排序算法總結(jié) " />插入排序原理依次選擇一個待排序的數(shù)據(jù)，插入到前邊已排好序的序列中。性能時間復(fù)雜度為 O(N )，空間復(fù)雜度為 O(1) 。算法是穩(wěn)定的，比 較次數(shù)和交換次數(shù)都與初始序列有關(guān)。優(yōu)化直接插入排序每次往前插入時，是按順序依次往前找，可在這 里進行優(yōu)化， 往前找合適的插入位置時采用二分查找的方式， 即折半 插入。折半插入排序相對直接插入排序而言：平均性能更快，時間復(fù) 雜度降至 O(NlogN) ，排序是穩(wěn)定的， 但排序的比較次數(shù)與初始序列 無關(guān)，總是需要 foor(log(i)+1 次排序比較。使用場景當數(shù)據(jù)基本有序

2、時，采用插入排序可以明顯減少數(shù)據(jù)交換和數(shù) 據(jù)移動次數(shù)，進而提升排序效率。代碼希爾排序原理插入排序的改進版，是基于插入排序的以下倆點性質(zhì)而提出的改進方法：插入排序?qū)缀跻雅藕眯虻臄?shù)據(jù)操作時，效率很高，可以達到 線性排序的效率。但插入排序在每次往前插入時只能將數(shù)據(jù)移動一位，效率比較所以希爾排序的思想是：先是取一個合適的 gap縮小間隔 gap ，例如去 gap=ceil(gap/2) ，重復(fù)上述子序列劃分和排序直到，最后 gap=1 時，將所有元素放在同一個序列中進行插入 排序為止。性能開始時， gap 取值較大，子序列中的元素較少，排序速度快， 克服了直接插入排序的缺點 ;其次， gap 值逐漸

3、變小后，雖然子序列 的元素逐漸變多， 但大多元素已基本有序， 所以繼承了直接插入排序的優(yōu)點，能以近線性的速度排好序。代碼選擇排序原理每次從未排序的序列中找到最小值，記錄并最后存放到已排序序列的末尾性能時間復(fù)雜度為 O(N )，空間復(fù)雜度為 O(1) ，排序是不穩(wěn)定的 (把最小值交換到已排序的末尾導(dǎo)致的 )，每次都能確定一個元素所在的 最終位置，比較次數(shù)與初始序列無關(guān)。代碼快速排序原理分而治之思想：Divide ： 找 到 基 準 元 素 pivot ， 將 數(shù) 組 Ap.r 劃 分 為Ap.pivotpos-1 和 Apivotpos+1 q ，左邊的元素都比基準小，右邊的元素都比基準大 ;C

4、onquer ：對倆個劃分的數(shù)組進行遞歸排序 ;Combine ：因為基準的作用，使得倆個子數(shù)組就地有序，無需 合并操作。性能快排的平均時間復(fù)雜度為 O(NlogN) ，空間復(fù)雜度為 O(logN) ， 但最壞情況下，時間復(fù)雜度為 O(N )，空間復(fù)雜度為 O(N); 且排序是 不穩(wěn)定的， 但每次都能確定一個元素所在序列中的最終位置， 復(fù)雜度 與初始序列有關(guān)。優(yōu)化當初始序列是非遞減序列時，快排性能下降到最壞情況，主要因為基準每次都是從最左邊取得，這時每次只能排好一個元素。所以快排的優(yōu)化思路如下： 優(yōu)化基準，不每次都從左邊取，可以進行三路劃分，分別取最左邊，中間和最右邊的中間值，再交換到最左邊進

5、行排序 ;或者進行隨機取得待排序數(shù)組中的某一個元素，再交換到最左邊，進行排序。在規(guī)模較小情況下，采用直接插入排序代碼歸并排序原理分而治之思想：Divide ：將 n 個元素平均劃分為各含 n/2 個元素的子序列 ;Conquer ：遞歸的解決倆個規(guī)模為 n/2 的子問題 ;Combine ：合并倆個已排序的子序列性能時間復(fù)雜度總是為 O(NlogN) ，空間復(fù)雜度也總為為 O(N) ，算 法與初始序列無關(guān)，排序是穩(wěn)定的。優(yōu)化優(yōu)化思路：在規(guī)模較小時，合并排序可采用直接插入 ;在寫法上，可以在生成輔助數(shù)組時，倆頭小，中間大，這時不 需要再在后邊加倆個 while 循環(huán)進行判斷，只需一次比完。代碼1

6、0堆排序原理堆的性質(zhì)：是一棵完全二叉樹;反之為最每個節(jié)點的值都大于或等于其子節(jié)點的值，為最大堆 小堆。11堆排序思想：將待排序的序列構(gòu)造成一個最大堆，此時序列的最大值為根節(jié)點依次將根節(jié)點與待排序序列的最后一個元素交換再維護從根節(jié)點到該元素的前一個節(jié)點為最大堆，如此往復(fù)，最終得到一個遞增序列性能時間復(fù)雜度為 O(NlogN) ，空間復(fù)雜度為 O(1) ，因為利用的排序空間仍然是初始的序列，并未開辟新空間。算法是不穩(wěn)定的，與初始序列無關(guān)。12使用場景想知道最大值或最小值時， 比如優(yōu)先級隊列， 作業(yè)調(diào)度等場景代碼計數(shù)排序原理先把每個元素的出現(xiàn)次數(shù)算出來，然后算出該元素所在最終排 好序列中的絕對位置

7、（最終位置 ），再依次把初始序列中的元素，根據(jù) 該元素所在最終的絕對位置移到排序數(shù)組中。13性能時間復(fù)雜度為 O(N+K) ，空間復(fù)雜度為 O(N+K) ，算法是穩(wěn)定 的，與初始序列無關(guān)，不需要進行比較就能排好序的算法。使用場景算法只能使用在已知序列中的元素在 0-k 之間，且要求排序的 復(fù)雜度在線性效率上。代碼桶排序14原理根據(jù)待排序列元素的大小范圍，均勻獨立的劃分 M 個桶將N 個輸入元素分布到各個桶中去再對各個桶中的元素進行排序此時再按次序把各桶中的元素列出來即是已排序好的性能15時 間 復(fù) 雜 度 為 O(N+C)O(C)=O(M(N/M)log(N/M)=O(NlogN-NlogM) ，空間復(fù)雜度為O(N+M) ，算法是穩(wěn)定的，且與初始序列無關(guān)。使用場景算法思想和散列中的開散列法差不多，當沖突時放入同一個桶 中;可應(yīng)用于數(shù)據(jù)量分布比較均勻，或比較側(cè)重于區(qū)間數(shù)量時。基數(shù)排序原理對于有 d 個關(guān)鍵字時，可以分別按關(guān)鍵字進行排序。有倆種方法：16MSD ：