㈠ O（n2）排序演算法的總結
最近在慕課網上學習了O（n2）時間復雜度的相關演算法，總算是對這些演算法的優缺點有了詳細的特點。其實對於任何的演算法，沒有優點和缺點，而是有相應的特點。所以我們應該結合不同的排序環境來選擇不同的排序演算法，從而達到在實現時間和執行效率上的平衡。這是因為，越是簡單的排序演算法，實現起來肯定是越容易，而且出現BUG的概率也不會太大。相反，復雜演算法可能效率更高，但是出現問題的可能性也會更大。下面，我就結合O（n2）時間復雜度的四個經典排序演算法，為您詳細講解這四個演算法的特點。
定義：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。
圖示說明：
源碼實現：
分析：通過選擇排序的圖示和源碼我們可以看出來，選擇排序要進行兩次循環，而且最關鍵的是內層循環在每一次執行時都是全部執行完的。那我們有沒有辦法讓內層循環不用每次都執行完呢？方法肯定是有的，這就是冒泡排序。
定義：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的元素列，一次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到沒有相鄰元素需要交換，也就是說該元素已經排序完成。
圖示說明：
源碼實現：
分析：從圖示和源碼可以看出來，從執行次數上來說，冒泡排序是比選擇排序的循環次數更少的。那是不是就可以說，如果待排序的數組中元素比較合適，冒泡排序在時間復雜度上是不是會比選擇排序更好呢？真的是這樣的嗎？
其實不是的，經過多次測試驗證，冒泡排序基本上是比選擇排序的時間復雜度要差的，這是為什麼呢？從源碼中我們可以很明顯的看出來，雖然冒泡排序是比選擇排序執行次數少了，但是交換的次數明顯增多了，而如果你對計算機程序指令的實現原理只要有一個基本的認識，就應該知道交換動作比賦值動作是需要更多指令操作的。所以說，最終冒泡排序大部分情況下，比選擇排序的時間復雜度都要高。
既然交換動作這么消耗資源，那有沒有一種方法，即能夠減少內層循環的執行次數，又可以減少甚至是無需交換操作呢？這就要請出插入排序了。
定義：插入排序（Insertion Sort）的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，即每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
圖示說明：
源碼實現：
分析：從圖示和源碼可以看出來，插入排序（優化後的）是沒有交換操作的，而且對於內層循環來說，如果待排序的元素是比較大的值，那內層循環執行的次數會非常的少。因此，如果原始數據基本上是有序的，那使用插入排序的效率會非常的高。在O（n2）級別的排序演算法還可以再優化嗎？如果可以從哪裡優化呢？下面我們來介紹希爾排序，正是這個排序演算法的提出，使得排序演算法打破了O（n2）時間復雜度的禁錮。
定義：希爾排序(Shell's Sort)是插入排序的一種又稱「縮小增量排序」（Diminishing Increment Sort），是直接插入排序演算法的一種更高效的改進版本。該演算法的基本思想是：把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，排序演算法便終止。
對於希爾排序來說，最關鍵的就是增量該如何選取。這個增量該怎麼確定，這還真是個數學難題，至今沒有解答。但是通過大量的實驗，還是有個經驗值的。我們的例子給出的增量選取公式是：h = 3 * h + 1，下面請看圖示說明。
圖示說明：
源碼實現：
分析：從插入排序中我們知道，插入排在待排序數組基本有序時，插入排序的演算法效率會非常高，所以我們可以這樣認為，希爾排序的最終思想就是：先將整個待排記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，在對全體進行一次直接插入排序。
而希爾排序的效率之所以很高，就是因為這個基本思想確實很有用：即當h值大的時候，數據項每一趟排序需要移動元素的個數很少，但數據項移動的距離很長。這是非常有效率的。而當h減小時，每一趟排序需要移動的元素的個數增多，但是此時數據項已經接近於它們排序後最終的位置，這對於插入排序可以更有效率。正是這兩種情況的結合才使希爾排序效率那麼高。
對於增量的選取，可以稱得上是一種魔法。在希爾的原稿中，他建議初始的間距為N/2，簡單地把每一趟排序分成了兩半。但是，這被證明並不是最好的數列。盡管對於大多數的數據來說這個方法還是比插入排序效果好，但是這種方法有時會使運行時間降到O(N2)，這並不比插入排序的效率更高。間隔序列中的數字互質通常被認為很重要：也就是說，除了1之外它們沒有公約數。這個約束條件使每一趟排序更有可能保持前一趟排序已排好的效果。希爾最初以N/2為間隔的低效性就是歸咎於它沒有遵守這個准則。
總結：上面就是四種經典O（n2）級別排序演算法的相關說明。其實在各種場合下選擇排序和冒泡排序基本上是不會使用的，因為使用場景基本沒有。而對於插入排序和希爾排序來說，在待排序數據基本有序的情況下，使用場景還是有的，比如一些日誌文件中存儲的日誌，可能大部分的日誌記錄都是基於時間排序，只是在某些極端情況下導致一些日誌晚存儲了導致時間不一致。
我是徐建航， 這是我寫的第31篇文章，歡迎你加入007社群，七天寫一篇，一起寫七年，七年之後一起去南極。
㈡ 面試必會八大排序演算法（Python）
一、插入排序
介紹
插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。
演算法適用於少量數據的排序，時間復雜度為O(n^2)。
插入排演算法是穩定的排序方法。
步驟
①從第一個元素開始，該元素可以認為已經被排序
②取出下一個元素，在已經排序的元素序列中從後向前掃描
③如果該元素（已排序）大於新元素，將該元素移到下一位置
④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
⑤將新元素插入到該位置中
⑥重復步驟2
排序演示
演算法實現
二、冒泡排序
介紹
冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。
原理
循環遍歷列表，每次循環找出循環最大的元素排在後面；
需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。
步驟
①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
③針對所有的元素重復以上的步驟，除了最後一個。
④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
演算法實現：
三、快速排序
介紹
快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是：挖坑填數 + 分治法。
首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
實現步驟
①從數列中挑出一個元素，稱為 「基準」（pivot）；
②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；
③對所有兩個小數列重復第二步，直至各區間只有一個數。
排序演示
演算法實現
四、希爾排序
介紹
希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。
希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；
·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。
基本思想
①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；
②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。
排序演示
演算法實現
五、選擇排序
介紹
選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。
基本思想
選擇排序的基本思想：比較 + 交換。
第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；
第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；
以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。
排序演示
選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。
演算法實現
六、堆排序
介紹
堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。
利用數組的特點快速指定索引的元素。
基本思想
堆分為大根堆和小根堆，是完全二叉樹。
大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。
在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
排序演示
演算法實現
七、歸並排序
介紹
歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
基本思想
歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。
演算法思想
自上而下遞歸法（假如序列共有n個元素）
① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；
② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；
③ 重復步驟②，直到所有元素排序完畢。
自下而上迭代法
① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；
② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；
④ 重復步驟③直到某一指針達到序列尾；
⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。
排序演示
演算法實現
八、基數排序
介紹
基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。
基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。
在某些時候，基數排序法的效率高於其他的穩定性排序法。
基本思想
將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。
基數排序按照優先從高位或低位來排序有兩種實現方案：
MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。
LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。
排序效果
演算法實現
九、總結
各種排序的穩定性、時間復雜度、空間復雜度的總結：
平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；
從時間復雜度來說：
線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；
O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；
線性階O(n)排序：基數排序，此外還有桶、箱排序。