各类排序算法总结（作者：__Boost）
各類排序算法總結(jié)
一.?排序的基本概念
排序(Sorting)是計算機(jī)程序設(shè)計中的一種重要操作，其功能是對一個數(shù)據(jù)元素集合或序列重新排列成一個按數(shù)據(jù)元素某個項值有序的序列。
有?n?個記錄的序列{R1，R2，…，Rn}，其相應(yīng)關(guān)鍵字的序列是{K1，K2，…，Kn}，相應(yīng)的下標(biāo)序列為1，2，…，n。通過排序，要求找出當(dāng)前下標(biāo)序列1，2，…，?n?的一種排列p1，p2，?…，pn，使得相應(yīng)關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系，即：Kp1≤Kp2≤…≤Kpn，這樣就得到一個按關(guān)鍵字有序的記錄序列{Rp1，Rp2，…，Rpn}。
作為排序依據(jù)的數(shù)據(jù)項稱為“排序碼”，也即數(shù)據(jù)元素的關(guān)鍵碼。若關(guān)鍵碼是主關(guān)鍵碼，則對于任意待排序序列，經(jīng)排序后得到的結(jié)果是唯一的；若關(guān)鍵碼是次關(guān)鍵碼，排序結(jié)果可能不唯一。
實現(xiàn)排序的基本操作有兩個：
（1）“比較”序列中兩個關(guān)鍵字的大小；
（2）“移動”記錄。
若對任意的數(shù)據(jù)元素序列，使用某個排序方法，對它按關(guān)鍵碼進(jìn)行排序：若相同關(guān)鍵碼元素間的位置關(guān)系，排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；而不能保持一致的排序方法則稱為不穩(wěn)定的。
?
二.插入類排序
1.直接插入排序
直接插入排序是最簡單的插入類排序。僅有一個記錄的表總是有序的，因此，對?n?個記錄的表，可從第二個記錄開始直到第?n?個記錄，逐個向有序表中進(jìn)行插入操作，從而得到n個記錄按關(guān)鍵碼有序的表。
它是利用順序查找實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”的插入排序。
?
注意直接插入排序算法的三個要點：
（1）從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0];
[cpp]?view plaincopy
（2）對于在查找過程中找到的那些關(guān)鍵字不小于R[i].key?的記錄，可以在查找的同時實現(xiàn)向后移動,即:查找與移動同時進(jìn)行.
[cpp]?view plaincopy
（3）i?=?2，3，…,?n,?實現(xiàn)整個序列的排序(從i?=?2開始).
?
【算法如下】
[cpp]?view plaincopy【性能分析】
（1）空間效率：僅用了一個輔助單元，空間復(fù)雜度為O(1)。只需R[0]做輔助.
（2）時間效率：向有序表中逐個插入記錄的操作，進(jìn)行了n-1?趟，每趟操作分為比較關(guān)鍵碼和移動記錄，而比較的次數(shù)和移動記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列。
直接插入排序的最好情況的時間復(fù)雜度為O(n)，平均時間復(fù)雜度為O(n^2)。
（3）穩(wěn)定性：直接插入排序是一個穩(wěn)定的排序方法。
?
總體來說:直接插入排序比較適用于帶排序數(shù)目少,且基本有序的情況下.
?
?
2.折半插入排序
直接插入排序的基本操作是向有序表中插入一個記錄，插入位置的確定通過對有序表中記錄按關(guān)鍵碼逐個比較得到的。平均情況下總比較次數(shù)約為(n^2)/4。既然是在有序表中確定插入位置，可以不斷二分有序表來確定插入位置，即一次比較，通過待插入記錄與有序表居中的記錄按關(guān)鍵碼比較，將有序表一分為二，下次比較在其中一個有序子表中進(jìn)行，將子表又一分為二。這樣繼續(xù)下去，直到要比較的子表中只有一個記錄時，比較一次便確定了插入位置。
折半插入排序是利用折半查找實現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”。
綜上:折半插入排序只是減少了比較的次數(shù),因此折半插入排序總的時間復(fù)雜度仍是O(n^2).
?
3.希爾排序
希爾排序又稱縮小增量排序，較直接插入排序和折半插入排序方法有較大的改進(jìn)。直接插入排序算法簡單，在?n?值較小時，效率比較高，在?n?值很大時，若序列按關(guān)鍵碼基本有序,效率依然較高，其時間效率可提高到O(n)。希爾排序即是從這兩點出發(fā)，給出插入排序的改進(jìn)方法。
希爾排序的基本思想是：先將待排序記錄序列分割成若干個“較稀疏的”子序列，分別進(jìn)行直接插入排序。經(jīng)過上述粗略調(diào)整，?整個序列中的記錄已經(jīng)基本有序，最后再對全部記錄進(jìn)行一次直接插入排序。具體實現(xiàn)時，首先選定兩個記錄間的距離d1，在整個待排序記錄序列中將所有間隔為d1?的記錄分成一組，進(jìn)行組內(nèi)直接插入排序，然后再取兩個記錄間的距離d2<d1，在整個待排序記錄序列中，將所有間隔為d2?的記錄分成一組，進(jìn)行組內(nèi)直接插入排序，直至選定兩個記錄間的距離dt=1?為止，此時只有一個子序列，即整個待排序記錄序列。
?
【性能分析】
（1）空間效率：僅用了一個輔助單元，空間復(fù)雜度為O(1)。
（2）時間效率：希爾排序時效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動次數(shù)依賴于步長因子序列的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的步長因子序列的方法。步長因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：步長因子中除?1?外沒有公因子，且最后一個步長因子必須為1。
O(log2n)~O(n^2)之間的一個值.
(3)穩(wěn)定性：希爾排序方法是一個不穩(wěn)定的排序方法。
?
三.交換類排序
交換排序主要是通過兩兩比較待排記錄的關(guān)鍵碼，若發(fā)生與排序要求相逆，則交換之。
?
1.冒泡排序(相鄰比較法)
冒泡排序是最簡單的一種交換排序。
假設(shè)在排序過程中，記錄序列R[1..n]的狀態(tài)為:
則第?i?趟起泡插入排序的基本思想為：借助對無序序列中的記錄進(jìn)行“交換”的操作，將無序序列中關(guān)鍵字最大的記錄“交換”到R[n-i+1]的位置上。
?
【算法如下】
[cpp]?view plaincopy【性能分析】
(1)空間效率：僅用了一個輔助單元，空間復(fù)雜度為O(1)。
(2)時間效率：最好情況的時間復(fù)雜度為O(n)，平均時間復(fù)雜度為O(n^2)。
(3)穩(wěn)定性：冒泡排序法是一種穩(wěn)定的排序方法
?
總比較次數(shù)
2.快速排序
快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，將待排序列分成兩部分。其中，一部分所有記錄的關(guān)鍵碼大于等于支點記錄的關(guān)鍵碼，另一部分所有記錄的關(guān)鍵碼小于支點記錄的關(guān)鍵碼。我們將待排序列按關(guān)鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關(guān)鍵碼有序.
如果每次劃分對一個元素定位后,該元素的左側(cè)子序列與右側(cè)子序列的長度相同,則下一步將是對兩個長度減半的子序列進(jìn)行排序,這是最理想的情況!
?
【算法如下】
[cpp]?view plaincopy
?
容易看出，調(diào)整過程中的樞軸位置并不重要，因此，為了減少記錄的移動次數(shù)，應(yīng)先將樞軸記錄“移出”，待求得樞軸記錄應(yīng)在的位置之后(此時low=high),再將樞軸記錄到位。
將上述“一次劃分”的算法改寫如下：
[cpp]?view plaincopy
[cpp]?view plaincopy
【性能分析】
(1)空間效率：快速排序是遞歸的，每層遞歸調(diào)用時的指針和參數(shù)均要用棧來存放，遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致。因而，存儲開銷在理想情況下為O(log2n)，即樹的高度；在最壞情況下，即二叉樹是一個單鏈，為O(n)。
(2)時間效率：在n?個記錄的待排序列中，一次劃分需要約?n?次關(guān)鍵碼比較，時效為O(n)，若設(shè)T(n)為對?n?個記錄的待排序列進(jìn)行快速排序所需時間。理想情況下：每次劃分，正好將分成兩個等長的子序列，則
? [plain]?view plaincopy?
可以證明,QuickSort的平均計算也是O(nlog2n).
最壞情況下：即每次劃分，只得到一個子序列，時效為O(n^2)。
快速排序是通常被認(rèn)為在同數(shù)量級O(nlog2n)的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來選取支點記錄，即將排序區(qū)間的兩個端點與中點三個記錄關(guān)鍵碼居中的調(diào)整為支點記錄。
(3)快速排序是一個不穩(wěn)定的排序方法.
(4) 最慘情況:空間復(fù)雜度->O(n),時間復(fù)雜度->O(n^2)
平均情況:空間復(fù)雜度->O(log2n),時間復(fù)雜度->O(nlog2n)
(5)快速排序比較適用于輸入規(guī)模n較大的情況.
?
四.選擇類排序
1.選擇排序
簡單選擇排序是最簡單的一種選擇類的排序方法。假設(shè)排序過程中，待排記錄序列的狀態(tài)為：
?
并且有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字，則第i?趟簡單選擇排序是，從無序序列R[i..n]的n-i+1?記錄中選出關(guān)鍵字最小的記錄加入有序序列。
操作方法：第一趟，從n?個記錄中找出關(guān)鍵碼最小的記錄與第1?個記錄交換；第二趟，從第二個記錄開始的n-1?個記錄中再選出關(guān)鍵碼最小的記錄與第2?個記錄交換；如此，第i趟，則從第i?個記錄開始的n-i+1?個記錄中選出關(guān)鍵碼最小的記錄與第?i?個記錄交換，直到整個序列按關(guān)鍵碼有序。
?
【算法如下】
[cpp]?view plaincopy【性能分析】
(1)空間效率：僅用了一個輔助單元，空間復(fù)雜度為O(1)。
(2)時間效率：簡單選擇排序的最好和平均時間復(fù)雜度均為O(n^2)。
(3)穩(wěn)定性：不同教材對簡單選擇排序的穩(wěn)定性有爭議，一般認(rèn)為，若是從前往后比較來選擇第i?小的記錄則該算法是穩(wěn)定的，若是從后往前比較來選擇第i?小的記錄則該算法是不穩(wěn)定的。
?
2.堆排序
堆排序的特點是，在以后各趟的“選擇”中利用在第一趟選擇中已經(jīng)得到的關(guān)鍵字比較的結(jié)果.
堆的定義:?堆是滿足下列性質(zhì)的數(shù)列{r1,?r2,?…，rn}：
若將此數(shù)列看成是一棵完全二叉樹，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分別是堆，并且當(dāng)左/右子樹不空時，根結(jié)點的值小于(或大于)左/右子樹根結(jié)點的值。
由此，若上述數(shù)列是堆，則r1?必是數(shù)列中的最小值或最大值，分別稱作小頂堆或大頂堆。
堆排序即是利用堆的特性對記錄序列進(jìn)行排序的一種排序方法。具體作法是：設(shè)有?n?個元素，將其按關(guān)鍵碼排序。首先將這?n?個元素按關(guān)鍵碼建成堆，將堆頂元素輸出，得到n?個元素中關(guān)鍵碼最小(或最大)的元素。然后，再對剩下的n-1?個元素建成堆，輸出堆頂元素，得到n?個元素中關(guān)鍵碼次小(或次大)的元素。如此反復(fù)，便得到一個按關(guān)鍵碼有序的序列。稱這個過程為堆排序。
?
因此，實現(xiàn)堆排序需解決兩個問題：
（1）如何將n?個元素的序列按關(guān)鍵碼建成堆。
建堆方法：對初始序列建堆的過程，就是一個反復(fù)進(jìn)行篩選的過程。n?個結(jié)點的完全二叉樹，則最后一個結(jié)點是第?n/2?個結(jié)點的孩子。對第?n/2?個結(jié)點為根的子樹篩選，使該子樹成為堆，之后向前依次對各結(jié)點為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點。
（2）輸出堆頂元素后，怎樣調(diào)整剩余n-1?個元素，使其按關(guān)鍵碼成為一個新堆。
調(diào)整方法：設(shè)有m?個元素的堆，輸出堆頂元素后，剩下m-1?個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。將根結(jié)點與左、右孩子中較小(或小大)的進(jìn)行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結(jié)點不滿足堆的性質(zhì)；若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結(jié)點不滿足堆的性質(zhì)。繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點，堆被建成。稱這個自根結(jié)點到葉子結(jié)點的調(diào)整過程為篩選。
?
【算法如下】
堆排序的算法如下所示：
[cpp]?view plaincopy?
其中篩選的算法如下所示。為將R[s..m]調(diào)整為“大頂堆”，算法中“篩選”應(yīng)沿關(guān)鍵字較大的孩子結(jié)點向下進(jìn)行。
[cpp]?view plaincopy?
【性能分析】
（1）空間效率：僅用了一個輔助單元，空間復(fù)雜度為O(1)。
（2）時間效率：
①對深度為k?的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1);
②對n?個關(guān)鍵字，建成深度為h(=?log2n?+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為4n;
③調(diào)整“堆頂”n-1?次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過
[plain]?view plaincopy
因此，堆排序的平均和最壞時間復(fù)雜度均為O(nlogn)。
(3)堆排序是一個不穩(wěn)定的排序方法。
?
3.二路歸并排序:
【算法思想】
歸并排序的基本思想是：將兩個或兩個以上的有序子序列“歸并”為一個有序序列。
在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的有序子序列，
空間復(fù)雜度為O(n),穩(wěn)定,時間復(fù)雜度O(nlog2n)
【算法如下】
[cpp]?view plaincopy?
歸并排序的算法可以有兩種形式：遞歸的和遞推的，它是由兩種不同的程序設(shè)計思想得出的。
在此，只討論遞歸形式的算法，這是一種自頂向下的分析方法：如果記錄無序序列R[s..t]的兩部分R[s..?(s+t)/2?]和R[?(s+t)/2+1..t?]分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列，由此，應(yīng)該先分別對這兩部分進(jìn)行2-路歸并排序。
[cpp]?view plaincopy
?
【性能分析】
(1)空間效率：需要一個與表等長的輔助元素數(shù)組空間，所以空間復(fù)雜度為O(n)。
(2)時間效率：對n?個元素的表，將這n?個元素看作葉結(jié)點，若將兩兩歸并生成的子表看作它們的父結(jié)點，則歸并過程對應(yīng)由葉向根生成一棵二叉樹的過程。所以歸并趟數(shù)約等于二叉樹的高度-1，即log2n，每趟歸并需移動記錄n?次，故時間復(fù)雜度為O(nlog2n)。
(3)穩(wěn)定性：歸并排序是一個穩(wěn)定的排序方法。
穩(wěn)定的排序算法：
插入排序、冒泡排序、歸并排序、基排序（插入冒泡歸并基）
非穩(wěn)定的排序算法：
快速排序、選擇排序、希爾排序、堆排序（快速選擇希爾堆）
總結(jié)
以上是生活随笔為你收集整理的各类排序算法总结（作者：__Boost）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Spark集群配置
- 下一篇： Ubuntu上手动安装sbt