AI必備八大算法內功心法秘籍_風聞
雀跃-2019-08-06 17:53
一、前言
如果説各種編程語言是程序員的招式，那麼數據結構和算法就相當於程序員的內功。
想寫出精煉、優秀的代碼，不通過不斷的錘鍊，是很難做到的。
二、八大排序算法
排序算法作為數據結構的重要部分，系統地學習一下是很有必要的。
1、排序的概念
排序是計算機內經常進行的一種操作，其目的是將一組“無序”的記錄序列調整為“有序”的記錄序列。
排序分為內部排序和外部排序。
若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序。
反之，若參加排序的記錄數量很大，整個序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。
2、排序分類
八大排序算法均屬於內部排序。如果按照策略來分類，大致可分為：交換排序、插入排序、選擇排序、歸併排序和基數排序。如下圖所示：
3、算法分析
下表給出各種排序的基本性能，具體分析請參看各排序的詳解：
三、算法心法秘籍1.冒泡排序
冒泡排序是一種交換排序。
什麼是交換排序呢？
答曰：兩兩比較待排序的關鍵字，並交換不滿足次序要求的那對數，直到整個表都滿足次序要求為止。
算法思想
它重複地走訪要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是説該數列已經排序完成。
這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，故名冒泡排序。
動態效果示意圖：
假設有一個大小為 N 的無序序列。以升序冒泡排序為例，冒泡排序就是要每趟排序過程中通過兩兩比較相鄰元素，將小的數字放到前面，大的數字放在後面。
2.直接插入排序
直接插入排序（Insertion Sort）序是一種最簡單的插入排序。為簡化問題，我們下面只討論升序排序。
算法思想
插入排序：每一趟將一個待排序的記錄，按照其關鍵字的大小插入到有序隊列的合適位置裏，知道全部插入完成。
動態效果示意圖：
以上的過程，其實就是典型的直接插入排序，每次將一個新數據插入到有序隊列中的合適位置裏。
很簡單吧，接下來，我們要將這個算法轉化為編程語言。
假設有一組無序序列 R0, R1, … , RN-1。
(1) 我們先將這個序列中下標為 0 的元素視為元素個數為 1 的有序序列。
(2) 然後，我們要依次把 R1, R2, … , RN-1 插入到這個有序序列中。所以，我們需要一個外部循環，從下標 1 掃描到 N-1 。
(3) 接下來描述插入過程。假設這是要將 Ri 插入到前面有序的序列中。由前面所述，我們可知，插入Ri時，前 i-1 個數肯定已經是有序了。
所以我們需要將Ri 和R0 ~ Ri-1 進行比較，確定要插入的合適位置。這就需要一個內部循環，我們一般是從後往前比較，即從下標 i-1 開始向 0 進行掃描。
3.希爾排序
希爾(Shell)排序又稱為縮小增量排序，它是一種插入排序。它是直接插入排序算法的一種威力加強版。
希爾排序，也稱遞減增量排序算法，以其設計者希爾（Donald Shell）的名字命名，該算法由 1959 年公佈。
算法思想
我們舉個例子來描述算法流程（以下摘自維基百科）：
假設有這樣一組數 {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10}，如果我們以步長為 5 開始進行排序：
C++
1：13 14 94 33 82
2：25 59 94 65 23
3：45 27 73 25 39
4：10
然後我們對每列進行排序：
C++
1：10 14 73 25 23
2：13 27 94 33 39
3：25 59 94 65 82
4：45
將上述四行數字，依序接在一起時我們得到：{10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45}，然後再以 3 為步長：
C++
1：10 14 73
2：25 23 13
3：27 94 33
4：39 25 59
5：94 65 82
6：45
排序之後變為：
C++
1：10 14 13
2：25 23 33
3：27 25 59
4：39 65 73
5：45 94 82
6：94
最後以 1 為步長進行排序（此時就是簡單的插入排序了）。
可想而知，步長的選擇是希爾排序的重要部分。算法最開始以一定的步長進行排序，然後會繼續以更小的步長進行排序，最終算法以步長為 1 進行排序。當步長為 1 時，算法變為直接插入排序，這就保證了數據一定會被全部排序。
4.快速排序
快速排序是一種交換排序，它由C. A. R. Hoare在1962年提出。
算法思想
快速排序的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分：分割點左邊都是比它小的數，右邊都是比它大的數。
然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
動態效果示意圖：
詳細的圖解往往比大堆的文字更有説明力，所以直接上圖：
初始狀態為一組無序的數組：2、4、5、1、3。
經過以上操作步驟後，完成了第一次的排序，得到新的數組：1、2、5、4、3。
新的數組中，以2為分割點，左邊都是比2小的數，右邊都是比2大的數。
因為2已經在數組中找到了合適的位置，所以不用再動。
2左邊的數組只有一個元素1，所以顯然不用再排序，位置也被確定。（注：這種情況時，left指針和right指針顯然是重合的。因此在代碼中，我們可以通過設置判定條件left必須小於right，如果不滿足，則不用排序了）。
而對於2右邊的數組5、4、3，設置left指向5，right指向3，開始繼續重複圖中的一、二、三、四步驟，對新的數組進行排序。
5.簡單選擇排序
簡單選擇排序是一種選擇排序。
選擇排序：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結束為止。
二、算法思想
簡單排序很簡單，它的大致處理流程為：
從待排序序列中，找到關鍵字最小的元素；
如果最小元素不是待排序序列的第一個元素，將其和第一個元素互換；
從餘下的 N - 1 個元素中，找出關鍵字最小的元素，重複(1)、(2)步，直到排序結束。
動態效果示意圖：
舉例説明，處理過程示意圖如下所示：
6.堆排序
堆排序是一種選擇排序。
選擇排序：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結束為止。
算法思想
堆排序是利用堆的性質進行的一種選擇排序。
動態效果示意圖：
堆是一棵順序存儲的完全二叉樹。
其中每個結點的關鍵字都不大於其孩子結點的關鍵字，這樣的堆稱為小根堆。
其中每個結點的關鍵字都不小於其孩子結點的關鍵字，這樣的堆稱為大根堆。
舉例來説，對於n個元素的序列{R0, R1, … , Rn}當且僅當滿足下列關係之一時，稱之為堆：
Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整；
如上圖所示，序列R{3, 8, 15, 31, 25}是一個典型的小根堆。
堆中有兩個結點，元素3和元素8。
元素3在數組中以R[0]表示，它的左孩子結點是R[1]，右孩子結點是R[2]。
元素8在數組中以R[1]表示，它的左孩子結點是R[3]，右孩子結點是R[4]，它的父結點是R[0]。可以看出，它們滿足以下規律：
設當前元素在數組中以R[i]表示，那麼，
(1) 它的左孩子結點是：R[2*i+1];
(2) 它的右孩子結點是：R[2*i+2];
(3) 它的父結點是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
首先，按堆的定義將數組R[0..n]調整為堆（這個過程稱為創建初始堆），交換R[0]和R[n]；
然後，將R[0..n-1]調整為堆，交換R[0]和R[n-1]；
如此反覆，直到交換了R[0]和R[1]為止。
以上思想可歸納為兩個操作：
（1）根據初始數組去構造初始堆（構建一個完全二叉樹，保證所有的父結點都比它的孩子結點數值大）。
（2）每次交換第一個和最後一個元素，輸出最後一個元素（最大值），然後把剩下元素重新調整為大根堆。
當輸出完最後一個元素後，這個數組已經是按照從小到大的順序排列了。
先通過詳細的實例圖來看一下，如何構建初始堆。
設有一個無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。
構造了初始堆後，我們來看一下完整的堆排序處理：
還是針對前面提到的無序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 來加以説明。
相信，通過以上兩幅圖，應該能很直觀的演示堆排序的操作處理。
看完上面所述的流程你至少有一個疑問：
如何確定最後一個非葉子結點？
其實這是有一個公式的，設二叉樹結點總數為 n，則最後一個非葉子結點是第⌊n/2⌋個。
7.歸併排序
歸併排序是建立在歸併操作上的一種有效的排序算法，該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。
算法思想
該算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。
動態效果示意圖：
分而治之：
1、分階段
可以看到這種結構很像一棵完全二叉樹，本文的歸併排序我們採用遞歸去實現（也可採用迭代的方式去實現）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為logn。
2、治階段
再來看看治階段，我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合併為最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟。
8.基數排序
基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是隻能使用於整數。
算法思想
基本思想：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。
算法步驟：
將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。
從最低位開始，依次進行一次排序。
這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。
基數排序的方式可以採用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由鍵值的最右邊開始，而 MSD 則相反，由鍵值的最左邊開始。
不妨通過一個具體的實例來展示一下基數排序是如何進行的。 設有一個初始序列為: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我們知道，任何一個阿拉伯數，它的各個位數上的基數都是以 0~9 來表示的，所以我們不妨把 0~9 視為 10 個桶。
我們先根據序列的個位數的數字來進行分類，將其分到指定的桶中。例如：R[0] = 50，個位數上是 0，將這個數存入編號為 0 的桶中。
分類後，我們在從各個桶中，將這些數按照從編號 0 到編號 9 的順序依次將所有數取出來。這時，得到的序列就是個位數上呈遞增趨勢的序列。
按照個位數排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下來，可以對十位數、百位數也按照這種方法進行排序，最後就能得到排序完成的序列。
動態效果示意圖：
AI本身就是在大量數據中進行處理從而得到更精準的數據值，然而這些基本的八大算法就更應該要掌握好了。我們在人工智能課程學習中我們也會詳細講解到算法思維理解以及代碼操作，如果感興趣的可以下方留言。