排序算法是從事IT行業中最為常見的算法，排序是數值計算基礎，本次将講解各種排序算法。
一般情況下的算法思想是通過兩兩比較的方式進行排序，雖然從理論上來講采用兩兩比較可以解決現實問題，但是實際上卻不會采用兩兩比較的方式，是以，本次将會介紹性能較高的愛須算法，也是實際中用的最多的方法。
快速排序
快速排序(Quick Sort)采用分治法的思想，首先把一個數值序列劃分為兩個子序列，然後對兩個子序列再進行分治法的思想，計算過程如下：
- 從數值隊列中選擇一個基準元素
- 将隊列中的其他元素與基準元素進行比較，比基準元素小的元素放在基準元素的左邊，比基準元素大的元素放在右邊(降序排列則相反)，則隊列被基準元素劃分為左右兩個區間。
- 對兩個區間的值分别遞歸步驟2，使其最終形成有序的序列。
雖然上述步驟是采用遞歸的方式，但是當區間小于等于1時，将會直接傳回，是以不會無限制的遞歸下去，例如，對于隊列數值‘4、3、6、2、5’采用快速排序進行升序排列過程如圖所示：
快速排序基準區間劃分
以‘4’為基準，将比其小的元素‘3’，‘2’放到‘4’的左邊，比其大的‘6’，‘5’放到右邊，形成以4為基準的左右區間，然後對左右區間分别再次選擇出基準元素，重複上述過程，最終得到序列值‘2’，‘3’，‘4’，‘5’，‘6’
快速排序的時間複雜度O(nlogn)，空間複雜度與具體的實作有關。
歸并排序
歸并排序(Merge Sort)是指将兩個已經有序的序列合并成一個有序序列的排序方式。歸并排序可以采用疊代的方式進行排序。例如，有兩組數值序列A、B，采用歸并排序進行升序排序，則排序步驟如下
- 申請存放最終合并後的數值序列存放空間，空間大小為數值序列A、B的空間紙盒
- 初始化兩個指針，分别指向數值序列A、B的收元素位址
- 比較兩個指針對應的值，将較小的值放入到最終存放空間，并移動較小指針到序列的下一位置
- 重複步驟3，直到某個指針已經到序列的隊尾，且沒有元素可以和另外一個序列進行比較
- 将另外一個序列的剩餘元素直接複制到最終 序列存放空間的末尾
例如，兩組數值序列A、B，可以采用遞歸的思想，将一個大的序列拆分成兩組子序列，然後對兩組子序列再次進行拆分，直到每個子序列中僅有一個元素，然後将兩個隻有一個元素的序列歸并為一個含有兩個元素的序列，再将兩個含有兩個元素的序列進行歸并，以此類推，直到所有的元素都完成歸并，如圖：
歸并排序方法的時間複雜度：最差時間複雜度O(nlogn)(不了解複雜度的，請看本人上一篇文章)，最優時間複雜度O(n)，平均複雜度O(nlogn)
歸并排序方法的空間複雜度：具體與實作方法有關，不應高于O(n)
推排序
對排序(Heap Sort)是基于推的資料結構實作的排序算法，推是一種日常中使用較多的資料結構，對于含有N個數值序列的{X1,X2,X3.....Xn}，若滿足Xi小于等于K2i且Ki小于等于K2i+1其中(1<=i<=n/2)則可以稱作小根推，小根堆是堆頂的元素值，且是堆所有元素節點最小的值，相反，當Xi大于等于K2i且Ki大于等于K2i+1，即堆頂的元素值是堆裡所有節點關鍵字中最大的值，稱作大根堆。
根據上面描述，最小堆的第0個元素是整個堆中的最小值，最大堆的第0個元素是整個堆中的最大值
由于堆頂元素是最大值或最小值，是以可以利用此特性，每次從數組中直接選取出最大值或者最小值，使每次排序變的相對簡單，推排序的實作步驟氛圍以下4步：
- 将初始元素值X1,X2,X3......Xn建構大根推(最大堆)
- 将堆頂元素Xi與最後一個元素Xn置換，此時可将所有排序元素區分為兩個部分，其中，置換後的Xn屬于有序集合，前序元素{X1,X2,X3......Xn}屬于無序集合
- 根據步驟2的結果，将無序集合中的元素再洗進行大根堆調整，将得到的堆頂元素與最後的Xn-1置換，德大有序集合{Xn,Xn-1}及無需集合X1,X2,X3......Xn-2}
- 重複上述過程直到無序集合中的資料小于2，然後将有序幾個與無序集合的最後一個元素合并，最終得到完成的有序集合
排序元素的升序排序或者降序排序，取決于排序過程采用的是最小堆結構還是最大堆結構，以給定數組A[6]={18,8,5,39,20,10}為例，進行建構堆
首先構造一個二叉樹
建構初始堆
元素18所在的子樹找那個不滿足堆的性質，是以進一步調整後，從完全二叉樹最後一個非葉子節點開始，使子節點與目前節點進行比較，将最大的值做哦為目前節點，一次調節左子樹和右子樹
重複疊代進行堆排序，最終獲得從大到小的排序結果
此外還有基數排序，外排序等，不做具體介紹了。喜歡的話，點一下關注吧！每天都有文章哦！