一、直接插入排序

直接插入排序(Insertion
Sort)的基本思想是：每次將一個待排序的元素記錄，按其關鍵字大小插入到它前面已經排好序的子序列中的適當位置，直到全部元素插入完成為止。

設需要排序的數組為a[0…n-1]。

1. 初始時，i = 0，a[0]自成1個有序區，無序區為a[1..n-1]。

2. 將a[i]併入當前的有序區a[0…i-1]中形成a[0…i]的有序區間。

3. i++並重複第二步直到 i == n-1，排序完成。

這裡，我將a[i]併入當前的有序區時，設置了一個臨時變數 tmp 用於交換兩個無序元素，這樣簡化了代碼。

時間複雜度&空間複雜度

如果目標是把n個元素的序列按序排列，那麼採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n
- 1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n - 1) / 2次。插入排序的賦值操作是比較操作的次數減去(n -
1)次。平均來說插入排序演算法複雜度為O(n2)。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。

這裡再介紹另外一個排序演算法概念，穩定性：假定在待排序的序列中，存在多個具有相同的關鍵字的元素，若經過排序，這些元素的相對次序保持不變，即在原序列中，a[1]
= a[j]，且 a[i] 在 a[j] 之前，而在排序後的序列中，a[i] 仍在 a[j]
之前，則稱這種排序演算法是穩定的;否則稱為不穩定的。在簡單插入排序中只有當兩個無序的元素不相等時，才會進行交換，所以相等元素的相對位置不會改變。

二、希爾排序

希爾排序(Shell
Sort)又稱為「縮小增量排序」。該方法的基本思想是：先將整個待排元素序列分割成若干個子序列(由相隔某個「增量」的元素組成的)分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序(增量足夠小，例如為1)時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下(接近最好情況)，效率是很高的，因此希爾排序在時間效率上比前一種方法有較大提高。

基本步驟，在此我們選擇增量gap=n/2，縮小增量繼續以gap =
gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2...1}，稱為增量序列。希爾排序的增量序列的選擇與證明是個數學難題，我選擇的這個增量序列是比較常用的，也是希爾建議的增量，稱為希爾增量，但其實這個增量序列不是最優的。此處我們做示例使用希爾增量。

希爾排序中，由於相同元素可能被分於不同排序組中，所以它們的相對位置很可能發生變化，如上圖中的 25 ，所以希爾排序演算法是一種不穩定的演算法。

希爾排序在數組中採用跳躍式分組的策略，通過某個增量將數組元素劃分為若干組，然後分組進行插入排序，隨後逐步縮小增量，繼續按組進行插入排序操作，直至增量為1。希爾排序通過這種策略使得整個數組在初始階段達到從宏觀上看基本有序，小的基本在前，大的基本在後。然後縮小增量，到增量為1時，其實多數情況下只需微調即可，不會涉及過多的數據移動。

上面選擇的增量序列{n/2,(n/2)/2...1}(希爾增量)，其最壞時間複雜度依然為O(n2)，一些經過優化的增量序列如代碼中的方法經過複雜證明可使得最壞時間複雜度為O(n3/2)。

三、選擇排序

選擇排序的思想：從所有序列中先找到最小的，然後放到第一個位置。之後再看剩餘元素中最小的，放到第二個位置……以此類推，就可以完成整個的排序工作。可以很清楚的發現，選擇排序是固定位置，找元素。相比於插入排序的固定元素找位置，是兩種思維方式。

基這種思想，我做出了一步優化，同時將無序序列中的最大最小值找出來，放到有序序列的頭和尾，簡單來說就是從所有序列中先找到最小和最大的的，然後最小的放到第一個位置，最大的放到最後一個位置。之後再看剩餘元素中最小的和最大的，放到第二個位置和倒數第二個位置……以此類推，也可以完成整個的排序工作。而且比前一種更快。

從選擇排序的思想或者是上面的代碼中，我們都不難看出，尋找最小的元素需要一個循環的過程，而排序又是需要一個循環的過程。因此顯而易見，這個演算法的時間複雜度也是O(n*n)的。這就意味值在n比較小的情況下，演算法可以保證一定的速度，當n足夠大時，演算法的效率會降低。並且隨著n的增大，演算法的時間增長很快。

傳統的簡單選擇排序,每趟循環只能確定一個元素排序後的定位。我們可以考慮改進為每趟循環確定兩個元素(當前趟最大和最小記錄)的位置,從而減少排序所需的循環次數。改進後對n個數據進行排序,最多只需進行[n/2]趟循環即可。由以上分析易知選擇排序的依然不穩定。

四、堆排序

堆排序的思想(以大頂堆為例)：

利用堆頂記錄的是最大關鍵字這一特性，每一輪取堆頂元素放入有序區，就類似選擇排序每一輪選擇一個最大值放入有序區，可以把堆排序看成是選擇排序的改進。

將初始待排序關鍵字序列(R0,R1,R2....Rn)構建成大頂堆，此堆為初始的無序區;

將堆頂元素R[0]與最後一個元素R[n]交換，此時得到新的無序區(R0,R1,R2,......Rn-1)和新的有序區(Rn);

由於交換後新的堆頂R[0]可能違反堆的性質，因此需要對當前無序區(R0,R1,R2,......Rn-1)調整為新堆。

不斷重複此2、3步驟直到有序區的元素個數為n-1，則整個排序過程完成。

由以上分析易知堆排序也不穩定。由二叉樹的特點知道它的空間複雜度為O(N*logN)

五、冒泡排序

冒泡排序(Bubble
Sort)是一種簡單的排序演算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

步驟：

1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

3.針對所有的元素重複以上的步驟，除了最後一個。

4.持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

冒泡排序是一種穩定的排序演算法，它的最壞情況和平均複雜度是O(n2)，甚至連插入排序(O(n2)演算法複雜度)效率都比冒泡排序演算法更好，唯一的優勢在於基於它的改進演算法——快速排序演算法。

六、快速排序

快速排序是冒泡排序的一種改進，冒泡排序排完一趟是最大值冒出來了，那麼可不可以先選定一個值，然後掃描待排序序列，把小於該值的記錄和大於該值的記錄分成兩個單獨的序列，然後分別對這兩個序列進行上述操作。這就是快速排序，我們把選定的那個值稱為樞紐值，如果樞紐值為序列中的最大值，那麼一趟快速排序就變成了一趟冒泡排序。

快速排序使用分治法(Divide and conquer)策略來把一個串列(list)分為兩個子串列(sub-lists)。

步驟為：(1)從數列中挑出一個元素，稱為 "基準"(pivot);

(2)重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區(partition)操作。

(3)遞歸地(recursive)把小於基準值元素的子數列和大於基準值元素的子數列排序。

當我們每次劃分的時候選擇的基準數接近於整組數據的最大值或者最小值時，快速排序就會發生最壞的情況，但是每次選擇的基準數都接近於最大數或者最小數的概率隨著排序元素的增多就會越來越小，我們完全可以忽略這種情況。但是在數組有序的情況下，它也會發生最壞的情況，為了避免這種情況，我們在選擇基準數的時候可以採用三數取中法來選擇基準數。

三數取中法： 選擇這組數據的第一個元素、中間的元素、最後一個元素，這三個元素裡面值居中的元素作為基準數。

按照以上思想可以容易實現一下代碼：

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代(iteration)中，它至少會把一個元素擺到它最後的位置去。小區間優化：當劃分的子序列很小的時候(一般認為小於13個元素左右時)，我們在使用快速排序對這些小序列排序反而不如直接插入排序高效。因為快速排序對數組進行劃分最後就像一顆二叉樹一樣，當序列小於13個元素時我們再使用快排的話就相當於增加了二叉樹的最後幾層的結點數目，遞歸的次數就會驟增。所以我們在當子序列小於13個元素的時候就改用直接插入排序來對這些子序列進行排序。

根據上面的一些思想，我們對快速排序的實現共有如下幾種方法：

實現方式一：左右分治法

演算法思想：在待排序序列中選擇一個數據作為基準值(三數取中法選擇基準值)，定義兩個變數left,right開始分別記錄待排序區間的兩端的值，左變數向右找比基準值大的數據，找到後停下來，接著右變數向左開始找比基準值小的數據，找到後停下來，交換左右變數所記錄的數據，直到兩指針相遇，出循環後將左變數值與基準值進行交換，交換成功後比基準值小的數據都在其左邊，比基準值大的數據都在基準值的右邊，換言之基準值已經處於合適的位置。接著遞歸對基準值的左區間和右區間進行排序，當區間只有一個數據時，默認已經有序。

實現方式二：挖坑法

演算法思想：在待排序序列中選擇一個數據作為基準值(暫且將區間右端數據作為基準值)，首次將坑設在基準值處，定義兩個變數left,right開始分別記錄待排序區間的兩端，左變數向右找比基準值大的數據，找到後將該值填入坑中並且將坑的位置更新在左變數所記錄的位置，接著右變數向左開始找比基準值小的數據，找到後將該值填入坑中並且將坑的位置更新在右變數記錄的位置，直到兩變數相遇，出循環後比基準值小的數據都在其左邊，比基準值大的數據都在基準值的右邊，換言之基準值已經處於合適的位置。接著遞歸對基準值的左區間和右區間進行排序，當區間只有一個數據時，默認已經有序。

演算法實現3：前後指針法

演算法思想：在待排序序列中選擇一個數據作為基準值(暫且將區間右端數據作為基準值)，定義兩個臨時變數prev和cur,cur首次記錄待排序區間的第一個元素，prev指向cur的前一個位置，只要cur沒走到區間末尾，就在中間找比基準值小的數據，每找到一次將prev記錄的位置下標加一，然後如果二者所指元素不同就將其所指元素交換，直到cur走到區間的最右端退出循環，之後將prev++,將cur和prev所記錄的數據進行交換。至此基準值被排序到正確位置，遞歸其左右區間即可完成整個排序。

快速排序是一種快速的分而治之的演算法，它是已知的最快的排序演算法，其平均運行時間為O(N*1ogN)
。它的速度主要歸功於一個非長緊湊的並且高度優化的內部循環。但是他也是一種不穩定的排序，當基準數選擇的不合理的時候他的效率又會編程O(N*N)。快速排序的最好情況：
快速排序的最好情況是每次都劃分後左右子序列的大小都相等，其運行的時間就為O(N*1ogN)。快速排序的最壞情況：
快速排序的最壞的情況就是當分組重複生成一個空序列的時候，這時候其運行時間就變為O(N*N)快速排序的平均情況： 平均情況下是O(N*logN)。

快速排序非遞歸

思想同遞歸，只是要藉助額外空間來臨時存儲待排序區間的首尾元素值。

七、歸併排序

歸併排序是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。

歸併排序基本思想：設兩個有序的子序列(相當於輸入序列)放在同一序列中相鄰的位置上：a[begin1...end1]，a[begin2...end2]，先將它們合併到一個局部的暫存序列
temp (相當於輸出序列)中，待合併完成後將 temp 複製回 a[begin...end]中，從而完成排序。
在具體的合併過程中，設置begin1，begin2 和 index三個變數，其初值分別記錄這三個記錄區的起始位置。合併時依次比較 a[begin1] 和
a[begin2] 的關鍵字，取關鍵字較小(或較大)的記錄複製到 temp[index] 中，然後將被複制記錄的變數begin1 或 begin2 加
1，以及指向複製位置的變數 index加 1。重複這一過程直至兩個輸入的子序列有一個已全部複製完畢(不妨稱其為空)，此時將另一非空的子序列中剩餘記錄依次複製到
a中即可。

歸併排序是一種穩定的排序且效率是比較高的，設數列長為N，將數列分開成小數列一共要logN步，每步都是一個合併有序數列的過程，時間複雜度可以記為O(N)，故一共為O(N*logN)。因為歸併排序每次都是在相鄰的數據中進行操作，所以歸併排序在O(N*logN)的幾種排序方法(快速排序，歸併排序，希爾排序，堆排序)也是效率比較高的。

更多IT精品課程，訪問中公優就業官網：http://xue.ujiuye.com

勤工儉學計劃」，給你一個真正0元學習IT技術的機會！

http://www.ujiuye.com/zt/qgjx/?wt.bd=lsh11tt

找工作太難？不是你不行，我們來幫你！

http://www.ujiuye.com/zt/jyfc/?wt.bd=lsh11shtt

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！