排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。
常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。
本文將依次介紹上述八大排序算法。
算法一：插入排序
插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
算法步驟：
- 將第一待排序序列第一個(gè)元素看做一個(gè)
有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。 - 從頭到尾依次掃描
未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）
算法二：希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
- 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)， 效率高， 即可以達(dá)到線性排序的效率；
- 但插入排序一般來說是低效的， 因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位。
希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。
算法步驟：
- 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
- 每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
算法三：選擇排序
選擇排序(Selection sort)也是一種簡(jiǎn)單直觀的排序算法。
算法步驟：
- 首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置；
- 再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾；
- 重復(fù)第二步，直到所有元素均排序完畢。
算法四：冒泡排序
冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
算法步驟：
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
- 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
算法五：歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
算法步驟：
- 申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；
- 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
- 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
- 重復(fù)步驟3直到某一指針達(dá)到序列尾；
- 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
詳細(xì)介紹：歸并排序
算法六：快速排序
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。
算法步驟：
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）。
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
詳細(xì)介紹：快速排序
算法七：堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
堆排序的平均時(shí)間復(fù)雜度為Ο(nlogn) 。
算法步驟：
- 創(chuàng)建一個(gè)堆
H[0..n-1]； - 把堆首（最大值）和堆尾互換；
- 把堆的尺寸縮小1，并調(diào)用
shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置； - 重復(fù)步驟2，直到堆的尺寸為1。
詳細(xì)介紹：堆排序
算法八：基數(shù)排序
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
說基數(shù)排序之前，我們簡(jiǎn)單介紹桶排序：
算法思想：是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。簡(jiǎn)單來說，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對(duì)每個(gè)桶里面的在進(jìn)行排序。
例如要對(duì)大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序。
首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ)[10..20]的整數(shù)，……集合B[i]存儲(chǔ)[(i-1)*10, i*10]的整數(shù)，i=1,2,..100。總共有100個(gè)桶。
然后，對(duì)A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對(duì)應(yīng)的桶B[j]中。 再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來說任何排序法都可以。
最后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這 樣就得到所有數(shù)字排好序的一個(gè)序列了。
假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。如果對(duì)每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是O(n+m*n/m*log(n/m))=O(n+nlogn–nlogm)。從上式看出，當(dāng)m接近n的時(shí)候，桶排序復(fù)雜度接近O(n).
當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的。這個(gè)假設(shè)是很強(qiáng)的，實(shí)際應(yīng)用中效果并沒有這么好。如果所有的數(shù)字都落在同一個(gè)桶中，那就退化成一般的排序了。
前面說的幾大排序算法，大部分時(shí)間復(fù)雜度都是O（n2），也有部分排序算法時(shí)間復(fù)雜度是O(nlogn)。而桶式排序卻能實(shí)現(xiàn)O（n）的時(shí)間復(fù)雜度。但桶排序的缺點(diǎn)是：
- 首先是空間復(fù)雜度比較高，需要的額外開銷大。排序有兩個(gè)數(shù)組的空間開銷，一個(gè)存放待排序數(shù)組，一個(gè)就是所謂的桶，比如待排序值是從0到m-1，那就需要m個(gè)桶，這個(gè)桶數(shù)組就要至少m個(gè)空間。
- 其次待排序的元素都要在一定的范圍內(nèi)等等。
總結(jié)
各種排序的穩(wěn)定性，時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性總結(jié)如下圖：
關(guān)于時(shí)間復(fù)雜度：
- 平方階(O(n2))排序：各類簡(jiǎn)單排序:直接插入、直接選擇和冒泡排序。
- 線性對(duì)數(shù)階(O(nlog2n))排序：快速排序、堆排序和歸并排序。
- O(n1+§))排序：§是介于0和1之間的常數(shù)。
- 線性階(O(n))排序：基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(wěn)定性：
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序；
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
