如果說各種編程語言是程序員的招式，那么數據結構和算法就相當于程序員的內功。
想寫出精煉、優秀的代碼，不通過不斷的錘煉，是很難做到的。
一、排序算法
排序算法作為數據結構的重要部分，系統地學習一下是很有必要的。
1、排序的概念
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。
排序分為內部排序和外部排序。
若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。
反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。
2、排序分類
八大排序算法均屬于內部排序。如果按照策略來分類，大致可分為：交換排序、插入排序、選擇排序、歸并排序和基數排序。如下圖所示：
進一步描述八大排序：
①插入排序
將第一個和第二個元素排好序，然后將第3個元素插入到已經排好序的元素中，依次類推（插入排序最好的情況就是數組已經有序了）。
②希爾排序
因為插入排序每次只能操作一個元素，效率低。元素個數N，取奇數k=N/2，將下標差值為k的數分為一組（一組元素個數看總元素個數決定），在組內構成有序序列，再取k=k/2，將下標差值為k的數分為一組，構成有序序列，直到k=1，然后再進行直接插入排序。
③簡單選擇排序
選出最小的數和第一個數交換，再在剩余的數中又選擇最小的和第二個數交換，依次類推。
④堆排序
以升序排序為例，利用小根堆的性質（堆頂元素最小）不斷輸出最小元素，直到堆中沒有元素
1.構建小根堆
2.輸出堆頂元素
3.將堆低元素放一個到堆頂，再重新構造成小根堆，再輸出堆頂元素，以此類推。
⑤冒泡排序
改進1：如果某次冒泡不存在數據交換，則說明已經排序好了，可以直接退出排序
改進2：頭尾進行冒泡，每次把最大的沉底，最小的浮上去，兩邊往中間靠1
⑥快速排序
選擇一個基準元素，比基準元素小的放基準元素的前面，比基準元素大的放基準元素的后面，這種動作叫分區，每次分區都把一個數列分成了兩部分，每次分區都使得一個數字有序，然后將基準元素前面部分和后面部分繼續分區，一直分區直到分區的區間中只有一個元素的時候，一個元素的序列肯定是有序的嘛，所以最后一個升序的序列就完成啦。
⑦歸并排序
將一個無序的數列一直一分為二，直到分到序列中只有一個數的時候，這個序列肯定是有序的，因為只有一個數，然后將兩個只含有一個數字的序列合并為含有兩個數字的有序序列，這樣一直進行下去，最后就變成了一個大的有序數列
⑧基數排序
找到最大的數，開個比最大的數大一點的數組，遍歷每個元素，某個元素為k，則a[k]++,最好遍歷數組a，a[k]等于多少就輸出多少個k。只能處理整型數。
三、詳解八大排序算法
1.插入排序
直接插入排序的核心思想就是：將數組中的所有元素依次跟前面已經排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，直到全部元素都比較過。
因此，從上面的描述中我們可以發現，直接插入排序可以用兩個循環完成：
第一層循環：遍歷待比較的所有數組元素。
第二層循環：將本輪選擇的元素(selected)與已經排好序的元素(ordered)相比較。如果：selected > ordered，那么將二者交換。
2.希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。
希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
算法步驟：
a.選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
b.按增量序列個數k，對序列進行k 趟排序；
c.每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
3.簡單選擇排序
簡單選擇排序的實現思想：比較+交換
從待排序序列中，找到關鍵字最小的元素；
如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
從余下的 N - 1 個元素中，找出關鍵字最小的元素，重復(1)、(2)步，直到排序結束。因此我們可以發現，簡單選擇排序也是通過兩層循環實現。第一層循環：依次遍歷序列當中的每一個元素 第二層循環：將遍歷得到的當前元素依次與余下的元素進行比較，符合最小元素的條件，則交換。
4.堆排序
堆：本質是一種數組對象。特別重要的一點性質：任意的葉子節點小于（或大于）它所有的父節點。對此，又分為大頂堆和小頂堆：
大頂堆要求節點的元素都要大于其孩子。
小頂堆要求節點元素都小于其左右孩子。
兩者對左右孩子的大小關系不做任何要求。
利用堆排序，就是基于大頂堆或者小頂堆的一種排序方法。下面，我們通過大頂堆來實現。
基本思想：堆排序可以按照以下步驟來完成：
a.首先將序列構建稱為大頂堆；（這樣滿足了大頂堆那條性質：位于根節點的元素一定是當前序列的最大值）。
b.取出當前大頂堆的根節點，將其與序列末尾元素進行交換；（此時：序列末尾的元素為已排序的最大值；由于交換了元素，當前位于根節點的堆并不一定滿足大頂堆的性質）。
c.對交換后的n-1個序列元素進行調整，使其滿足大頂堆的性質。
d.重復2.3步驟，直至堆中只有1個元素為止。
5.冒泡排序
算法思想：冒泡遍歷所有的數據，每次對相鄰元素進行兩兩比較，如果順序和預先規定的順序不一致，則進行位置交換；這樣一次遍歷會將最大或最小的數據上浮到頂端，之后再重復同樣的操作，直到所有的數據有序。這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端。
6.快速排序
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n logn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
算法步驟：
a.從數列中挑出一個元素，稱為 “基準”（pivot）。
b.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
c.遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
8.基數排序
基數排序：通過序列中各個元素的值，對排序的N個元素進行若干趟的“分配”與“收集”來實現排序。
分配：我們將L[i]中的元素取出，首先確定其個位上的數字，根據該數字分配到與之序號相同的桶中 。
收集：當序列中所有的元素都分配到對應的桶中，再按照順序依次將桶中的元素收集形成新的一個待排序列L[ ] 。
對新形成的序列L[ ]重復執行分配和收集元素中的十位、百位...直到分配完該序列中的最高位，則排序結束。
好了，本文就分享到這里，本文主要講解原理，不同編程語言實現方法不同，后面有機會再給大家分享具體實現方法。
長按前往圖中包含的公眾號關注
