一.分治：將長數組一分為二，大的分成小的，再每個小的里面操作

1.快排（自我推薦），竟然敢取這么吊的名字，說明一定會有它的牛b之處

過程：先選擇分割位，再進行分割，在選擇分割位的時候，實際上就在排序了，當分割完成，排序即完成；從上到下一步到位

步驟：

1.左右邊界判斷，left<=right,retrun;

2.分割點定位，默認選第一個點（實際上選哪個點都可以，看起來就很靈活），while循環中，大于分割點的移到右邊，小于分割點的移到左邊，最后left=right就是要找的分割位

3.分割成左右子數組進入循環

2.歸并

過程：先平均分割，再在兩個子序列中合并排序，排序方式也很普通

步驟：

1.左右邊界判斷，如上

2.找中間點，分割進入左右子序列（遞歸）

3.兩個子序列間的合并排序，排序后結果更新到原始序列

對比分析：nlgn

主觀：快排單程，歸并要往返，快排要快一點

客觀：1.快排最好情況，分割lgn次，每次比較n次，無交換；最差情況，分割n次，每次比較n次 ，時間復雜度變為n2

　　　2.歸并排序，穩定，nlgn

二：插入

1.直接插入排序

過程：在有序的序列中，從后向前，一步一步找到合適的位置；先和最后一個位置比較，若小余它，則交換，再與前面的比較，直到交換至合適的位置；這里也可不進行交換操作，直接前面數據后移，找到合適空位插入

2.希爾排序（不穩定復雜度不確定）：對直接插入排序的優化，將序列與處理為總體有序，減少操作步驟

過程：通過增量gap間隔抽取子序列，通過插入排序先排序，再逐步減小gap，直到處理完整序列

步驟：

1.取gap循環，每次循環gap減小，直至為1

2.循環內差值排序

三：基礎

1.冒泡

2.交換

四：堆排序（自我推薦），時間和空間都很棒，依賴二叉樹結構，調整序列順序，先綁定，再聯動

過程

1.構造堆，n取全集，i先選子節點，再通過循環選擇父節點，i表示這個位置就是要放最大的值，i表示一個范圍，以此節點為父的所有子樹

2.使用構造好的堆，取出堆頂，放在排序隊列中，再進入n-1堆的構造，這次的i取堆頂，重復構造取出堆頂放入隊列中

構造堆步驟：通過給定數據，默認當前二叉樹，通過變化節點位置實現堆排序

1.確定父節點i，也是作為最大值位置；左節點2*i-1，右節點2*i+1

2.三個節點判斷，若父節點最大，直接退出；若左/右節點大，與父節點交互位置，并進入該子節點的判斷排序，在構造堆的過程中，完成整體的排序效果；注意構造堆過程中，堆與數據同時變化位置

3.取堆頂，并與堆尾交換，因為整體有序，所以從堆頂開始判斷，重新構造堆即可，異常情況已躲避

二叉樹的分層與晉級與分治算法本質相同：分治更加形象，都是分了lgn層，最大值都是要從最低層，一層一層比較到最頂層，不同在于，前者平行比較，后者垂直比較，使用空間少，但前者優化一下，似乎也可以實現相同效果

五：非比較排序

1.計數排序，類似加密統計的方式

過程：

1.篩選數據范圍，找出最大，最小值

2.開辟空間，計數存儲，這是個遍歷統計過程

3.數據還原，還原后的數據即排序后的數據

2.桶排序，分治思想，總體劃分成多個桶，即范圍，每個桶內再排序