二、各算法的特點(具體實現見後面的博客)
1.快速行
(1)算法思想
選擇壹個參考元素，將小於參考元素的元素放在前面，將大於參考元素的元素放在後面，然後將小於參考值元素的子序列和大於參考元素的子序列按原方法排序，直到整個序列有序；
(2)優點和缺點
優點:數據移動速度極快；
缺點:不穩定；
(3)效率分析
當序列比較混亂時，這種排序算法的效率更高。當數據有序時，就會退化為冒泡排序；
(4)基準的選擇
A.取三個數的中間值
具體思路是:將待排序序列中低、中、高三個位置的數據進行排序，以其中的數據為支點，存儲下標元素為0的支點；
B.隨機選擇基準
引入原因:當要排序的列是部分排序時，pivot的固定選擇使得快速排序效率低下；
具體思路是:以待排序列中的任意元素為基準；
(5)優化方法
a .當待排序序列的長度被分成壹定大小時，使用插入排序；
原因:對於非常小且部分有序的數組，快速排序不如插入。當待排序序列的長度被分割到壹定大小時，連續分割的效率比插入排序差，此時可以用插值代替快速排序；
B.壹次劃分後，等於鍵的元素可以集合在壹起，繼續下壹次劃分時，不需要再劃分等於鍵的元素；
(6)應用場景
A.找出數組中第k個最小的數字
取數組中的壹個元素m作為除法的基礎，即m=arr[0]。如果m前面的元素個數大於k，那麽第k個最小的數壹定在m前面的元素中，那麽我們只需要繼續在m前面的元素中尋找第k個最小的數；如果m前面的元素小於k，那麽第k個最小的數壹定在m後面的元素中，那麽我們只需要找到m後面的元素中的第k個最小的數；
2.氣泡分類
(1)基本原理
在壹組要排序的數字中，從上到下比較當前未排序的範圍內的所有數字，使較大的數字下沈，較小的數字上升。即每當兩個相鄰的數進行比較，發現它們的排序與排序要求相反時，就進行交換。
(2)優點和缺點
優點:穩定性
缺點:慢，壹次只能移動兩個相鄰的數據；
3.插入排序
(1)基本思想
在排序後的有序表中插入壹條記錄，得到壹個記錄數增加了1的新有序表。即把序列的第壹條記錄看作壹個有序子序列，然後壹條壹條地插入第二條記錄，直到整個序列是有序的。
(2)優點和缺點
優點:穩定快速。
缺點:比較的次數不壹定相同。比較次數越少，插入點後移動的數據就越多，尤其是數據量巨大的時候。
4.堆排序
4.1，二進制堆定義:
二叉堆是完全二叉樹或近似完全二叉樹。二進制堆滿足兩個特征:
(1)父節點的鍵值總是大於或等於(小於或等於)任何子節點的鍵值；
(2)每個節點的左子樹和右子樹是壹個二叉堆；
當父節點的鍵值總是大於或等於任意子節點的鍵值時，就是大根堆。當父節點的鍵值始終小於或等於任壹子節點的鍵值時，為小根堆；
4.2、堆存儲:
壹般用數組來表示堆，I節點的父節點下標是(i-1)/2。其左右子節點的下標分別為2*i+1和2*i+2。
4.3、堆的插入:
每次插入都會將新數據放在數組的末尾。我們可以發現，這個新數據從父節點到根節點，壹定是壹個有序序列，然後把這個新數據插入到這個有序數據中。
(1)按大根堆排序的基本思想
首先將初始數組構建成壹個大根堆，這壹對就是初始無序區；
然後，將最大元素與無序區域的最後記錄進行交換，從而獲得新的無序區域和有序區域，並滿足
因為交換後新的根可能會違反堆屬性，所以將當前的無序區域調整為堆。然後將最大元素與區間的最後壹條記錄再次交換，得到新的無序區和有序區，仍然滿足關系的值
..........
直到無序區只剩下壹個元素；
4.4:應用
在m個數中找出前k個最小的數，並按順序排列；
時間復雜度:O(K)[創建K個元素的最大堆的時間復雜度] +(M-K)*log(K)[比較剩余的M-K個數據，每次從新的最大堆堆最大堆]
5.希爾排序
(1)基本思想
首先將整個待排序元素序列分成若幹子序列(由壹定增量分隔的元素組成)進行直接插入排序，然後在排序前依次遞減增量。當整個序列中的元素基本有序(增量足夠小)時，對所有元素進行壹次直接插入排序(因為在元素基本有序的情況下直接插入排序是非常高效的)；
(2)適用場景
希爾排序中最重要的操作是比較，而不是交換。具有最佳已知步驟序列的Hill排序比直接插入排序更快，甚至比小數組中的快速排序和堆排序更快，但當涉及大量數據時，Hill排序仍然不如快速排序快。
6.合並排序
(1)基本思想
首先將初始序列的n條記錄視為n個有序子序列，每個子序列的長度為1。然後將n/2個長度為2的有序子序列成對合並，再將幾個長度為4的有序子序列成對合並，以此類推，直到得到壹個長度為n的有序序列。
(2)適用場景
如果n大，排序穩定，可以選擇歸並排序；
7.只需選擇排序
(1)基本思想
第壹遍:從第壹條記錄開始，比較後面的n-1條記錄，找出最小的記錄與第壹條記錄交換；
第二遍:從第二條記錄開始，比較接下來的n-2條記錄，找出最小的記錄與第二條記錄交換；
...........
Pass I:從第I條記錄開始，比較後面的n-i條記錄，找出最小的記錄與第I條記錄交換；
以此類推，n-1次比較後，n-1條記錄就位，剩下最大的記錄直接排在最後；