排序算法是什么?有多少種?排序算法總結(jié)又是怎樣?以下是留學(xué)網(wǎng)為您整理的排序算法總結(jié)，供您參考!
【排序算法總結(jié)】
排序算法：一種能將一串?dāng)?shù)據(jù)依照特定的排序方式進(jìn)行排列的一種算法。
排序算法性能：取決于時(shí)間和空間復(fù)雜度，其次還得考慮穩(wěn)定性，及其適應(yīng)的場(chǎng)景。
穩(wěn)定性：讓原本有相等鍵值的記錄維持相對(duì)次序。也就是若一個(gè)排序算法是穩(wěn)定的，當(dāng)有倆個(gè)相等鍵值的記錄R和S，且原本的序列中R在S前，那么排序后的列表中R應(yīng)該也在S之前。
以下來總結(jié)常用的排序算法，加深對(duì)排序的理解。
冒泡排序
原理
倆倆比較相鄰記錄的排序碼，若發(fā)生逆序，則交換;有倆種方式進(jìn)行冒泡，一種是先把小的冒泡到前邊去，另一種是把大的元素冒泡到后邊。
性能
時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(1)。排序是穩(wěn)定的，排序比較次數(shù)與初始序列無關(guān)，但交換次數(shù)與初始序列有關(guān)。
優(yōu)化
若初始序列就是排序好的，對(duì)于冒泡排序仍然還要比較O(N^2)次，但無交換次數(shù)。可根據(jù)這個(gè)進(jìn)行優(yōu)化，設(shè)置一個(gè)flag，當(dāng)在一趟序列中沒有發(fā)生交換，則該序列已排序好，但優(yōu)化后排序的時(shí)間復(fù)雜度沒有發(fā)生量級(jí)的改變。
代碼
插入排序
原理
依次選擇一個(gè)待排序的數(shù)據(jù)，插入到前邊已排好序的序列中。
性能
時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(1)。算法是穩(wěn)定的，比較次數(shù)和交換次數(shù)都與初始序列有關(guān)。
優(yōu)化
直接插入排序每次往前插入時(shí)，是按順序依次往前找，可在這里進(jìn)行優(yōu)化，往前找合適的插入位置時(shí)采用二分查找的方式，即折半插入。
折半插入排序相對(duì)直接插入排序而言：平均性能更快，時(shí)間復(fù)雜度降至O(NlogN)，排序是穩(wěn)定的，但排序的比較次數(shù)與初始序列無關(guān)，總是需要foor(log(i))+1次排序比較。
使用場(chǎng)景
當(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á)到線性排序的效率。
但插入排序在每次往前插入時(shí)只能將數(shù)據(jù)移動(dòng)一位，效率比較低。
所以希爾排序的思想是：
先是取一個(gè)合適的gap
縮小間隔gap，例如去gap=ceil(gap/2)，重復(fù)上述子序列劃分和排序
直到，最后gap=1時(shí)，將所有元素放在同一個(gè)序列中進(jìn)行插入排序?yàn)橹埂?BR> 性能
開始時(shí)，gap取值較大，子序列中的元素較少，排序速度快，克服了直接插入排序的缺點(diǎn);其次，gap值逐漸變小后，雖然子序列的元素逐漸變多，但大多元素已基本有序，所以繼承了直接插入排序的優(yōu)點(diǎn)，能以近線性的速度排好序。
代碼
選擇排序
原理
每次從未排序的序列中找到最小值，記錄并最后存放到已排序序列的末尾
性能
時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(1)，排序是不穩(wěn)定的(把最小值交換到已排序的末尾導(dǎo)致的)，每次都能確定一個(gè)元素所在的最終位置，比較次數(shù)與初始序列無關(guān)。
代碼
快速排序
原理
分而治之思想：
Divide：找到基準(zhǔn)元素pivot，將數(shù)組A[p..r]劃分為A[p..pivotpos-1]和A[pivotpos+1…q]，左邊的元素都比基準(zhǔn)小，右邊的元素都比基準(zhǔn)大;
Conquer：對(duì)倆個(gè)劃分的數(shù)組進(jìn)行遞歸排序;
Combine：因?yàn)榛鶞?zhǔn)的作用，使得倆個(gè)子數(shù)組就地有序，無需合并操作。
性能
快排的平均時(shí)間復(fù)雜度為O(NlogN)，空間復(fù)雜度為O(logN)，但最壞情況下，時(shí)間復(fù)雜度為O(N^2)，空間復(fù)雜度為O(N);且排序是不穩(wěn)定的，但每次都能確定一個(gè)元素所在序列中的最終位置，復(fù)雜度與初始序列有關(guān)。
優(yōu)化
當(dāng)初始序列是非遞減序列時(shí)，快排性能下降到最壞情況，主要因?yàn)榛鶞?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：遞歸的解決倆個(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)到該元素的前一個(gè)節(jié)點(diǎn)為最大堆，如此往復(fù)，最終得到一個(gè)遞增序列
性能
時(shí)間復(fù)雜度為O(NlogN)，空間復(fù)雜度為O(1)，因?yàn)槔玫呐判蚩臻g仍然是初始的序列，并未開辟新空間。算法是不穩(wěn)定的，與初始序列無關(guān)。
使用場(chǎng)景
想知道最大值或最小值時(shí)，比如優(yōu)先級(jí)隊(duì)列，作業(yè)調(diào)度等場(chǎng)景。
代碼
計(jì)數(shù)排序
原理
先把每個(gè)元素的出現(xiàn)次數(shù)算出來，然后算出該元素所在最終排好序列中的絕對(duì)位置(最終位置)，再依次把初始序列中的元素，根據(jù)該元素所在最終的絕對(duì)位置移到排序數(shù)組中。
性能
時(shí)間復(fù)雜度為O(N+K)，空間復(fù)雜度為O(N+K)，算法是穩(wěn)定的，與初始序列無關(guān)，不需要進(jìn)行比較就能排好序的算法。
使用場(chǎng)景
算法只能使用在已知序列中的元素在0-k之間，且要求排序的復(fù)雜度在線性效率上。
代碼
桶排序
原理
根據(jù)待排序列元素的大小范圍，均勻獨(dú)立的劃分M個(gè)桶
將N個(gè)輸入元素分布到各個(gè)桶中去
再對(duì)各個(gè)桶中的元素進(jìn)行排序
此時(shí)再按次序把各桶中的元素列出來即是已排序好的。
性能
時(shí)間復(fù)雜度為O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空間復(fù)雜度為O(N+M)，算法是穩(wěn)定的，且與初始序列無關(guān)。
使用場(chǎng)景
算法思想和散列中的開散列法差不多，當(dāng)沖突時(shí)放入同一個(gè)桶中;可應(yīng)用于數(shù)據(jù)量分布比較均勻，或比較側(cè)重于區(qū)間數(shù)量時(shí)。
基數(shù)排序
原理
對(duì)于有d個(gè)關(guān)鍵字時(shí)，可以分別按關(guān)鍵字進(jìn)行排序。有倆種方法：
MSD：先從高位開始進(jìn)行排序，在每個(gè)關(guān)鍵字上，可采用計(jì)數(shù)排序
LSD：先從低位開始進(jìn)行排序，在每個(gè)關(guān)鍵字上，可采用桶排序
性能
時(shí)間復(fù)雜度為O(d*(N+K))，空間復(fù)雜度為O(N+K)。
總結(jié)
以上排序算法的時(shí)間、空間與穩(wěn)定性的總結(jié)如下：