排序算法總結(jié)

1、排序算法總結(jié)導(dǎo)讀：本文 排序算法總結(jié)， 僅供參考， 如果能幫助到您， 歡迎點(diǎn)評和 分享。排序算法是什么 ?有多少種 ?排序算法總結(jié)又是怎樣 ?以下是留學(xué)網(wǎng)為您整理的排序算法總結(jié)，供您參考排序算法總結(jié)】排序算法：一種能將一串?dāng)?shù)據(jù)依照特定的排序方式進(jìn)行排列的一種算法。排序算法性能：取決于時(shí)間和空間復(fù)雜度， 其次還得考慮穩(wěn)定性， 及其適應(yīng)的場景。穩(wěn)定性：讓原本有相等鍵值的記錄維持相對次序。 也就是若一個(gè) 排序算法是穩(wěn)定的，當(dāng)有倆個(gè)相等鍵值的記錄 R和S,且原本的序列中R在S前，那么排序后的列表中R應(yīng)該也在S之前。以下來總結(jié)常用的排序算法，加深對排序的理解。冒泡排序原理倆倆比較相鄰記錄的排序碼，若發(fā)生

2、逆序，則交換 ;有倆種方式進(jìn)行冒泡， 一種是先把小的冒泡到前邊去， 另一種是把大的元素冒泡 到后邊。性能時(shí)間復(fù)雜度為0(N八2)，空間復(fù)雜度為0(1)。排序是穩(wěn)定的, 排序比較次數(shù)與初始序列無關(guān)，但交換次數(shù)與初始序列有關(guān)。優(yōu)化若初始序列就是排序好的，對于冒泡排序仍然還要比較 0(N八2)次，但無交換次數(shù)?？筛鶕?jù)這個(gè)進(jìn)行優(yōu)化，設(shè)置一個(gè) flag ，當(dāng)在一趟序列中沒有發(fā)生交換， 則該序列已排序好， 但優(yōu)化后排序的時(shí)間復(fù)雜度沒有發(fā)生量級的改變。代碼插入排序原理依次選擇一個(gè)待排序的數(shù)據(jù)，插入到前邊已排好序的序列中。性能時(shí)間復(fù)雜度為0(N八2)，空間復(fù)雜度為0(1)。算法是穩(wěn)定的,比較次數(shù)和交換次數(shù)都與

3、初始序列有關(guān)。優(yōu)化直接插入排序每次往前插入時(shí)， 是按順序依次往前找，可在這里進(jìn)行優(yōu)化， 往前找合適的插入位置時(shí)采用二分查找的方式，即折半插入。折半插入排序相對直接插入排序而言： 平均性能更快，時(shí)間復(fù)雜度降至 0(NlogN) ，排序是穩(wěn)定的，但排序的比較次數(shù)與初始序列無關(guān)，總是需要 foor(log(i)+1 次排序比較。使用場景當(dāng)數(shù)據(jù)基本有序時(shí)， 采用插入排序可以明顯減少數(shù)據(jù)交換和數(shù)據(jù)移動(dòng)次數(shù)，進(jìn)而提升排序效率。代碼希爾排序原理插入排序的改進(jìn)版， 是基于插入排序的以下倆點(diǎn)性質(zhì)而提出的改 進(jìn)方法：插入排序?qū)缀跻雅藕眯虻臄?shù)據(jù)操作時(shí)， 效率很高， 可以達(dá)到線 性排序的效率。但插入排序在每次往前插

4、入時(shí)只能將數(shù)據(jù)移動(dòng)一位， 效率比較低。所以希爾排序的思想是：先是取一個(gè)合適的 gap縮小間隔 gap ，例如去 gap=ceil(gap/2) ，重復(fù)上述子序列劃分 和排序直到，最后 gap=1 時(shí)，將所有元素放在同一個(gè)序列中進(jìn)行插入 排序?yàn)橹?。性能開始時(shí)， gap 取值較大，子序列中的元素較少，排序速度快，克 服了直接插入排序的缺點(diǎn) ;其次， gap 值逐漸變小后，雖然子序列的 元素逐漸變多， 但大多元素已基本有序， 所以繼承了直接插入排序的 優(yōu)點(diǎn)，能以近線性的速度排好序。代碼選擇排序原理每次從未排序的序列中找到最小值， 記錄并最后存放到已排序序 列的末尾性能時(shí)間復(fù)雜度為0(N八2)，空間復(fù)

5、雜度為0(1)，排序是不穩(wěn)定的(把 最小值交換到已排序的末尾導(dǎo)致的 ) ，每次都能確定一個(gè)元素所在的 最終位置，比較次數(shù)與初始序列無關(guān)。代碼快速排序原理分而治之思想：Divide ： 找 到 基 準(zhǔn) 元 素 pivot ， 將 數(shù) 組 Ap.r 劃 分 為Ap.pivotpos-1 和Apivotpos+1q，左邊的元素都比基準(zhǔn)小, 右邊的元素都比基準(zhǔn)大 ;Conquer ：對倆個(gè)劃分的數(shù)組進(jìn)行遞歸排序 ;Combine ：因?yàn)榛鶞?zhǔn)的作用，使得倆個(gè)子數(shù)組就地有序，無需 合并操作。性能快排的平均時(shí)間復(fù)雜度為 0(NlogN) ，空間復(fù)雜度為 0(logN) ， 但最壞情況下，時(shí)間復(fù)雜度為 0(N

6、八2)，空間復(fù)雜度為0(N);且排序是不穩(wěn)定的， 但每次都能確定一個(gè)元素所在序列中的最終位置， 復(fù)雜 度與初始序列有關(guān)。優(yōu)化當(dāng)初始序列是非遞減序列時(shí)， 快排性能下降到最壞情況， 主要因 為基準(zhǔn)每次都是從最左邊取得，這時(shí)每次只能排好一個(gè)元素。所以快排的優(yōu)化思路如下：優(yōu)化基準(zhǔn)，不每次都從左邊取，可以進(jìn)行三路劃分，分別取最左 邊，中間和最右邊的中間值，再交換到最左邊進(jìn)行排序 ;或者進(jìn)行隨機(jī)取得待排序數(shù)組中的某一個(gè)元素，再交換到最左邊，進(jìn)行排序。在規(guī)模較小情況下，采用直接插入排序代碼歸并排序原理分而治之思想：Divide ：將 n 個(gè)元素平均劃分為各含 n/2 個(gè)元素的子序列 ;Conquer ：遞歸

7、的解決倆個(gè)規(guī)模為 n/2 的子問題 ;Combine ：合并倆個(gè)已排序的子序列。性能時(shí)間復(fù)雜度總是為 O(NlogN) ，空間復(fù)雜度也總為為 O(N) ，算 法與初始序列無關(guān)，排序是穩(wěn)定的。優(yōu)化優(yōu)化思路：在規(guī)模較小時(shí)，合并排序可采用直接插入在寫法上，可以在生成輔助數(shù)組時(shí)，倆頭小，中間大，這時(shí)不需 要再在后邊加倆個(gè) while 循環(huán)進(jìn)行判斷，只需一次比完。代碼堆排序原理堆的性質(zhì)：是一棵完全二叉樹每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，為最大堆 ;反之為最小堆。堆排序思想：將待排序的序列構(gòu)造成一個(gè)最大堆， 此時(shí)序列的最大值為根節(jié)點(diǎn)依次將根節(jié)點(diǎn)與待排序序列的最后一個(gè)元素交換再維護(hù)從根節(jié)點(diǎn)到該元素的前一

8、個(gè)節(jié)點(diǎn)為最大堆， 如此往復(fù)， 最 終得到一個(gè)遞增序列性能時(shí)間復(fù)雜度為 O(NlogN) ，空間復(fù)雜度為 O(1) ，因?yàn)槔玫呐?序空間仍然是初始的序列，并未開辟新空間。算法是不穩(wěn)定的，與初 始序列無關(guān)。使用場景想知道最大值或最小值時(shí)，比如優(yōu)先級隊(duì)列，作業(yè)調(diào)度等場景。代碼計(jì)數(shù)排序原理先把每個(gè)元素的出現(xiàn)次數(shù)算出來， 然后算出該元素所在最終排好序列中的絕對位置 (最終位置 )，再依次把初始序列中的元素，根據(jù)該元素所在最終的絕對位置移到排序數(shù)組中。性能時(shí)間復(fù)雜度為 O(N+K) ，空間復(fù)雜度為 O(N+K) ，算法是穩(wěn)定的， 與初始序列無關(guān)，不需要進(jìn)行比較就能排好序的算法。使用場景算法只能使用在已知序列中的元素在 0-k 之間，且要求排序的復(fù) 雜度在線性效率上。代碼桶排序原理根據(jù)待排序列元素的大小范圍，均勻獨(dú)立的劃分 M 個(gè)桶將 N 個(gè)輸入元素分布到各個(gè)桶中去再對各個(gè)桶中的元素進(jìn)行排序此時(shí)再按次序把各桶中的元素列出來即是已排序好的。性能時(shí) 間 復(fù) 雜 度 為 O(N+C)，空間復(fù)雜度為O(C)=O(M(N/M)log(N/M)=O(NlogN-NlogM)O(N+M) ，算法是穩(wěn)定的，且與初始序列無關(guān)。使用場景算法思想和散列中的開散列法差不多， 當(dāng)沖突時(shí)放入同一個(gè)桶中 ;可應(yīng)用于數(shù)據(jù)量分布比較均勻，或比較側(cè)重于區(qū)間數(shù)量時(shí)。排序基數(shù)排序原理對于有 d 個(gè)關(guān)鍵