人心的成見是一座大山。一旦有山擋在面前，則很難到達下一站。所需要做的，是穿過這座山。
偶然間看了一個視頻，說的是EMA+SMA的自動交易策略，這個視頻做的很用心，在入場的時間不僅要看EMA的金叉，還需要看其他一些條件，而出場會用到另外的條件。結合最近的算法機試，瞬間就思緒萬千，其實在很多時候，低層次(算法應用）的我們，總是在O(n2)的維度中忙忙碌碌，我們總覺得自己很努力了，但仍然過不好，活不精彩，賺不到錢，處處抱怨。就像我已經有思路解出某道題了，已經把代碼敲出來，自測也通過了，但一提交就是運行超時、通過率30%一樣，低層次的算法應用怎么都穿不過這座山。
如果我們提升了算法的應用層次，就比如說從線性查找變成二分查找，運行的時間就大幅度降了下來，有些題目就能輕松通過了，而在人生的道路上也就能快速穿過那座大山，到達一個原來一直無法觸摸的層次。
算法無處不在，在初期我們一定是先要學習一些低層次的容易理解的算法，不要著急，這一階段應該是很困難，感覺就類似當年初學C語言學到指針的時候，指針淘汰了一大部分人，在那個時候感覺指針已經是天花板了，但再后來回頭一看，學會了指針只不過是新的一個臺階的開始而已。基礎算法亦是如此，我們只有先弄懂它們，能跟著把代碼寫出來順利執行，能自己在沒有提示和參考的情況下把代碼寫出來，能熟練反應出幾種同類型算法之間的代碼關鍵不同，能知道把它們應用到哪些場景，才算是走上了入門的臺階。也才是下一個層級算法學習的開始。簡單的說，學習初階的算法只是為了能有基礎去學習高階的算法，只有高階的算法才能讓你穿過那座山。如果學習初階后就停下來，那就沒有非常大的意義。
01_低效排序
一開始都基本上要接觸這3個 O(n2)的排序方法，包括冒泡、選擇和插入。這里直接會勸退很多人，特別是某些語言已經自帶sort函數了，會有很多人覺得不會費力去學，即便學了也只是認為懂個大概就可以了。我的觀點還是上面寫的，它只是你能否去接觸高階算法應用的基礎，基礎不牢，高階算法永遠無法得心應手。
冒泡排序
很多算法都來源勞動人民的生活經驗的總結，跟物理學一樣，一定要跟具體的實際存在的事物相結合才容易搞懂。
冒泡，就像是往杯子里倒汽水，氣泡一定會在水中上升浮到水面上。我們可以把最大值當泡泡，也可以把最小值當泡泡。想像一個帶刻度的玻璃試管(封閉的)，當一個泡泡上升到頂部的時候，水位就下降一格，第二個泡泡上升到這格的時候，水位再下降一格，所以小循環里循環計數上限每輪都會減去1，也就是減掉輪數。
def buble_sort_test(arr):ilen = len(arr)for i in range(ilen-1): # n-1輪for j in range( ilen-1 -j): # 水位每輪下降if arr[j] > arr[j+1]:arr[j],arr[j+1] = arr[j+1],arr[j]由于使用了2輪循環，時間復雜度為O(n*n)。
冒泡排序優化
很多時候需要看運氣，運氣好的情況會比運氣不好的情況獲利會好的多，但基礎的冒泡排序無視運氣的成分，哪怕是已經給出1個排序好的列表，冒泡仍會矜矜業業把n*n的圈數跑完。
在學習的視頻課程中看到了冒泡排序的優化方法（選擇排序用不了），它的思路就是如果上一次j和j+1的循環過程中，完全沒有發生變化，就意味著已經排序好了，也就不需要再進行循環了，這樣運氣好的情況下只要一輪就可以提前結束了（提前下班真開心！）
def buble_sort_opt(arr):ilen = len(arr)for i in range(ilen-1):b_swapped = False # 標志位 - 未交換for j in range(ilen-1-i):if arr[j]>arr[j+1]:arr[j],arr[j+1] = arr[j+1],arr[j]b_swapped = True # 交換則標志位為Trueif not b_swapped:break
然而事情的發展并不是我們想像的那么美好，好運的概率往往比較小，就像是交易的過程中總覺得自己能賺錢，但恰恰總是虧錢一樣。我們用10000個0~100000的隨機數進行測試，發現冒泡優化的方案仍有很多情況下是比原冒泡時間要長的。故事又一次告訴我們抖機靈的做法往往只在特定情況下(小概率）會有超額收益，在常規的情況下可能都是虧錢的。
選擇排序
選擇排序，也就是先選擇出1個最小值（或最大值），再排序把選出的值放到每輪的序號位置上，而序號位置的數換到被選值的序號位置。簡單舉例就是新生排隊，大家先全站成一列，然后報身高，第一輪報出身高最矮的，排到第1個，但注意這里不是全體后移而是原來第1個的要換到最矮的位置上，然后進行第二輪報身高，這次排第1個的就不用報了。
def select_sort_1(arr):ilen = len(arr):for i in range(ilen-1):imin = ifor j in range(i,ilen):if arr[j] < arr[imin]:imin = jarr[imin],arr[i] = arr[i],arr[imin] # 最小值放到第i輪的序號上
選擇排序相比冒泡動不動就要交換的情況而言，選擇排序每一輪只會執行一次交換操作，所以選擇排序在大樣本的列表排序的時候要明顯比冒泡快，比如10萬個元素0~10萬的隨機數測試中，選擇排序完成時間是121.985秒，而冒泡排序達到了可怕的352.436秒。
選擇排序中使用內置函數
學習的視頻中給出的一個使用python內置函數的選擇排序，可以讓我們比較清楚的認識到其實內置函數也是需要耗費時間的，不要只看for循環或while循環的次數，內置函數往往也相當于一個for循環。另外，新創建的列表會額外占用內存，是不推薦的。
不過測試的結果看到，使用內置函數相同于去除了交換的步驟，最后的測試時間大約是原選擇排序的1/3。
def select_sort_innefunc(arr):new_arr = []for i in range(len(arr)):vmin = min(arr) # 內置函數求最小值new_arr.append(vmin)arr.remove(vmin) # 不去除則每次都是同一個最小值return new_arr然后我嘗試著不使用新列表和append的方式，使用min()內置函數進行排序，就會遇到要是不把找到的vmin給remove掉，那么每次min(arr)還是一樣的，但一旦在原arr中remove掉vmin的位置，就會出現list index out of range的問題。
插入排序
學習視頻介紹的非常好，用打牌為例，不過我稍微變換一下場景為現在牌已經被等分成了幾份(比如4份) 于是我手里有13張（52/4)，然后我要進行理牌，把成隊的、三個的、四個的放在一起，以左邊放最小的，右邊放最大的，再后面拿到K就插到Q和A之間。插入排序多少與這樣的情況有很大的關聯，以便于我們去理解它。
插入排序就涉及到了邊界判斷，另外至少已經有1個數了才能進行Insert操作，否則就只是append操作。一般的情況下，如果左邊的數小于當前操作的數循環就可以停下來了，但左邊如果沒有阻擋會讓"指針"指到外面去了，所以需要添加邊界條件 j>=0防止出界。
def insert_sort(arr):for i in range(1, len(arr)): # 第0張必須存在才能insertcurr = arr[i] # 本輪當前值j = i-1 # 本輪左邊指針while(j>=0 and curr<arr[j]): # 左指針不能出界 and 當前值比左側的小arr[j+1] = arr[j]j -= 1 # 繼續左移arr[j+1] = curr # 本輪插入位置根據我們自己打牌的經驗，這種理牌的方法還是很有效率的吧，通過測試我們得到了同一列表(.copy())的運行時間：選擇排序為124.32秒，在選擇排序中使用min內置函數的44.285秒，而插入排序的時間是147.82秒。
使用內置排序函數
直接使用python內置的排序函數進行排序，得到的運行時間是11.0321 ms，相比上面的三種排序(選擇140.46s，冒泡，插入）的幾百秒明顯內置的排序要強大的多的多。
如果在實際的應用中，肯定是使用系統內置的排序方法進行。并且這里又給了我們當頭一棒，低效的算法與高效的算法差距居然如此之大，這個又豈是努力和忙碌能夠補的上的？
趕緊打好算法基礎，在有了扎實的基礎上，我們再繼續學習高效的算法，加油吧！
--------
02_高效的排序
相比前面的三種排序，有三種較為高效的排序，分別是快速排序，歸并排序和堆排序。其中堆排序理解起來很困難先放一放，而快速排序與歸并排序恰好都用到了遞歸，因此這一節來學習遞歸與快速排序和歸并排序。
遞歸的思考
首先問AI：什么是遞歸？
遞歸（Recursion） 是一種 函數調用自身 的編程技巧，用于將一個大問題分解為 規模更小但結構相同 的子問題，直到子問題簡單到可以直接求解（稱為基線條件或終止條件）。
📌 一句話理解
遞歸就是 “自己調用自己，直到不需要再調用”。
🌰 經典例子：計算階乘?
n!🧠 遞歸的三要素
基線條件（Base Case）：
什么時候停止遞歸，避免無限循環。遞歸條件（Recursive Case）：
如何將問題拆分為更小的同類子問題。返回值組合：
如何將子問題的結果合并為最終答案?? 遞歸的缺點
效率低：可能存在重復計算（如斐波那契數列）。
棧溢出：遞歸層數太深時，會耗盡調用棧（Python 默認限制約 1000 層）
sys.setrecursionlimit(2000) # 設置為 2000 層，或更大
可以說，這樣的說明懂的人能看懂，不懂的人還是看不懂。
遞歸經典例子
于是我們先來看一下經典例子：計算階乘，斐波那契數列 與文件夾遍歷：
計算階乘
這種明顯是數學題，通過對題目進行多步的推算，從而獲得它的函數表達式或解析式。首先是從0開始0的階乘是1， 1的階乘也是1， 2的階乘 = 2*1 = 2, 3的階乘=3*2*1 = 6（2*3）， 4的階乘=4*3*2*1=24（6*4），5的階乘是5*4*3*2*1=120 （24*5），于是 n的階乘n*n-1*n-2*.... = (n-1)!*n
這樣就得到函數解析式： y = x*(x-1)! 當x >=2 時，或者 y = 1 (x=0 ,1)
在這里我們得到的函數解析式并不是單純的Y與X的關系，還牽扯到上一個Y的值，回想一下我們在指標中使用的EMA，SMA以及DMA等，這些指標也都需要用到上一輪的數據，又比如在pandas里用shift(x)來實現。參考：量化交易backtrader實踐(三)_指標與策略篇(1)_指標簡介與手工雙均線策略
其實很容易理解的就是在EXCEL中我們新增了一列，用來累加某列的某個數值（比如當天的收入）從而獲取累加的總收入。那么我就覺得這類使用遞歸就容易理解和編寫代碼了。
重新舉個例子，老板查帳，發現最近兩天的總資產是空的沒有填寫，找來財務說財務前兩天休假，不過根據再前一天的數值和某個公式能補填上，那么這就有點遞歸的意思，今天的數值與昨天的數值有關系，昨天的數值與前天的又有關系，倒查到大前天有數據(遞歸退出條件），于是可以從大前天開始，根據公式計算出前天的數值填上，再根據前天的數值根據公式計算出昨天的數值填上，再根據昨天的數值和公式得到今天的數值，補填完畢。所以遞歸對于解決數學問題中與上個數值有關系的問題時，可以使用遞歸。我們也看到了遞歸其實是兩步走的，第一步是向前反查，直至查到退出條件成立，然后第二步，向后計算。
這樣其實挺累的，老板又發現某一列的數據缺失了好幾個月，財務說這個從第2天開始就沒有填，一天一天倒查太累了，于是直接從頭開始進行計算，這樣就省去了倒查的時間，只要從頭進行循環計算就好了，從這個例子上我覺得是當遞歸需要的次數過多時，還不如直接使用循環。但這種事只能財務來做，老板只需要知道根據昨天的數值今天應該是多少就足夠了。
def factorial(n):if n==0:return 1else:return n* factorial(n-1)#-------------------def factorial_iter(n):result = 1for i in range(2, n+1):result *= ireturn result計算斐波那契數列
這個比階乘要復雜一點，因為 F(n) = F(n-1)+F(n-2)，它跟昨天還有前天的數值都有關系，站在老板的角度上，我不管你幾天前的數據是什么，我只要昨天的財務和前天的財務過來一起對帳就可以了，所以遞歸的思路容易理解，但千萬注意遞歸先要倒著查回去，再滿足退出條件后又正著計算回來。
def Febo1(n): # 遞歸的寫法if n==1 or n==2:return 1return febo1(n-1)+febo1(n-2)-----------------
def Febo2(n): # 循環的寫法if n==1 or n==2:return 1a,b = 0,1for _ in range(2,n+1): # 注意n+1a,b = b, a+breturn b文件夾遍歷
前面2個例子都是數學方向上的，如果我們分析出函數的解析式，可以看到用遞歸或者循環的方式都可以，注意這里是把解析式已經拿到的情況，對于這類問題，可能關鍵點還是在于數學的分析上，所以我們應該對于這類分析多練習一下，比如說從0開始自己在紙上寫出運算結果，寫出4到5個后，再去求它的解析式。
如果不是函數，那么可能就沒有求函數解析式的步驟，比如說文件夾遍歷，某個目錄下面有多個子目錄，有多少個文件，這些不點進去都不知道，所以只能都點進去。而點進這個文件夾后再點進另一個文件夾，所有的操作都是相同的步驟，操作完了就back。所以遞歸還能解決這類“未知”的問題。
突然想起來擴展卡爾曼濾波也是遞歸，漢諾塔也是遞歸，循環可能知道起點和終點，但遞歸不一定。
import os
def list_path(path):for item in os.listdir(path):full_path = os.path.join(path,item)if os.path.isdir(full_path):list_path(full_path): # 遞歸調用else:print(full_path)文件夾應該就是樹結構吧，感覺這類探索類的問題往往可以用遞歸的方式來做。
快速排序
差點跑偏了，趕緊先把剛剛學習的快速排序給做好筆記！
快速排序跟歸并排序都使用了遞歸，在快速排序中，其核心思想是左側拿起1個數，一輪操作后把它放到它應該在的位置（也就是它的左邊都比它小，右邊都比它大），教學視頻稱之為歸位，它的函數名為partition，翻譯過來就叫“分區，分割”。然后以這個位置為分割成左和右2個部分，分別對左部分再進行分區，右部分再進行分區。
按照函數以及遞歸調用的次序，會先進行左側的處理，左側又從左0拿起1個數，一輪比較后放到它應該在的位置，然后又遞歸調用，又去處理下一輪的左側，直到分割后只有1個數，向上返回，處理最小單位的右側，再返回處理上一層的右側.... 返回到剛開始分割的左邊都完成，再處理右邊......
def partition(arr, left, right):tmp = arr[left] # 左0取數while(left < right): # 至少有2個數字while(left<right and arr[right]>tmp): # 先取右邊比tmp小的移到arr[left]right -=1arr[left] = arr[right]while(left<right and arr[left]<tmp): # 再取左邊比tmp大的移到arr[right]left +=1arr[right] = arr[left]arr[left] = tmpreturn left # 返回分割位置
當處理完分區，得到分割點位置后，再分別對左側和右側進行快速排序處理，所以函數為
def quick_sort_1(arr, left, right):if left < right:ipart = partition(arr,left,right) # 先計算分割位置quick_sort_1(arr, left, ipart) # 排序左側quick_sort_1(arr, ipart+1, right) # 排序右側程序完成后執行，快速排序的運行時間是120ms vs. 選擇排序列的147s，速度差不多1000倍，的確是強大不少。
歸并排序
趁著還記得住，趕緊記筆記！
歸并排序也用了遞歸，并且也使用類似左指針，右指針這種雙指針的操作；與快速排序不同的地方是快速排序會先起手計算分區位置，而歸并排序直接用了二分法，歸并排序玄妙之處在于先二分，遞歸調用對左側二分，對右側二分，進到遞歸中再次二分，這樣用不了幾輪，列表就被拆成只有1個字符，這時就滿足退出遞歸條件。
一旦在最后一層退出遞歸，馬上進行歸并即merge()操作，通過3個指針把左、右二塊的數值排序放到一個新的list中，然后退回到上一層。這樣退回到上面時已經把小塊的數字完成了排序。
我們看一下歸并的操作如下所示，兩塊有序列表，各用一個指針指在左0位置，進行比較，小的那個指針右移，并把數值放到新的列表中，以此類推。注意兩個列表總有一個要先走(完），則另一個的剩下的可直接添加進新列表中
步驟 ? ? ? ?當前比較 ? ? ?輸出數組（out）
------------------------------------------------
step 0 ? 2↑ 4 ?9 ?| ?1↑ 3 ?7 ? [ ]
step 1 ? 2↑ 4 ?9 ?| ?1 ?3↑ 7 ? [1] ? ? ? ?(1<2)
step 2 ? 2 ?4↑ 9 ?| ?3 ?3↑ 7 ? [1,2] ? ? ?(2<3)
step 3 ? 2 ?4↑ 9 ?| ?3 ?7↑ ? ? [1,2,3] ? ?(3<4)
step 4 ? 2 ?4 ?9↑ | ?7↑ ? ? ? ?[1,2,3,4] ?(4<7)
step 5 ? 9↑ ? ? ? ?| ?7 ?9↑ ? ? [1,2,3,4,7] (7<9)
step 6 ? 9↑ ? ? ? ?| ?9↑ ? ? ? ?[1,2,3,4,7,9]
def merge(arr, left, mid, right): # 前提是2塊有序 1，2，6，4； 3，5，8，7i = left # 指向左邊的最左j = mid +1 # 指向右邊的最左tmp_list = [] # 新列表while (i<=mid and j<=right):if arr[i]<=arr[j]:tmp_list.append(arr[i])i+=1else:tmp_list.append(arr[j])j+=1# 總有一個要先走，但不確定誰先走while i<= mid:tmp_list.append(arr[i])i += 1while j<= right:tmp_list.append(arr[j])j += 1arr[left:right+1] = tmp_list當merge函數完成后，就可以用遞歸把整個歸并排序實現了
def merge_sort(arr, left, right):if left < right:mid = (left + right)//2merge_sort(arr, left, mid) # 遞歸繼續拆左邊merge_sort(arr, mid+1, right) # 遞歸拆右邊# print(arr)merge(arr, left, mid,right)以上就完成了歸并排序，測試100000個隨機數的歸并排序，與快速排序差不多，也是1xx ms。
至此，我們又在遞歸的基礎上學習了2個高效的排序，快速排序和歸并排序。看看我們的成長吧，從原來只知道選擇和冒泡排序，已經成長到熟練選擇、冒泡、插入排序的代碼，接著理解了快速排序和歸并排序它們的原理，也敲出了相應的代碼，我們已經把原來400秒的運行時間縮短到了200毫秒內，這是怎么的一個進步啊！
雖然內置的.sort()函數排序跑的更快（只有20ms），所以我們在編寫程序的時候如果用到排序肯定還是首選內置排序，但不同的排序的方式都是一種算法的思路，就像是不同流派的劍招，一方面我們不能機械的只是用來做排序，我們要用不同的思路來解決類似的問題，我們需要舉一反三的應用；另一方面不同的思路的印證，大腦中才會有各多更好的思路來幫助我們解決實際的問題，讓我們更加輕松快速的穿過那座山，以及后面的一座座山。
03_在低效的基礎上的進階排序
插入排序與二分查找結合
在前面已經學習過了插入排序，結合我們打牌時摸到一張然后將它插入到手上已經排好的牌的某個位置上，也就是說手上的已經是排序好了的，結合我們學習二分查找必須要排序好的知識點，既然前面x張已經排序好了，那就不需要再像冒泡哪樣每一張都比較一下再前移，而是可以直接用二分查找來獲取插入的位置，這樣是不是就能提高效率了？
def insert_sort_with_binary(arr):for i in range(1, len(arr)):tmp = arr[i]j = i-1if i < 6: # 前5張仍用原來的插入排序while j>=0 and arr[j]>tmp:arr[j+1] = arr[j] # 每一個都要挪動j -= 1arr[j+1] = tmp else: # 第6張開始二分left = 0right = jif arr[right] > tmp:arr.pop(i) # 這個數會插入到前面去，先pop出來while left <= right: # 二分查找mid = (left+right)//2if arr[mid] > tmp:right = mid -1else:left = mid +1arr.insert(left, tmp) # 注意是插入到left位置，千萬不要mid位置啊！然后，添加上裝飾器計算運行時間，得到插入排序和改用二分查找的插入排序在list(range(100000))的數的排序時間分別是216019.97 ms(216秒）和10514.48 ms(10.5秒），效率的確是有了很大的提升。
插入排序再分組——希爾排序
“不積跬步，無以至千里；不積小流，無以成江海。” ——《荀子·勸學》
前面學習了快速排序、歸并排序后，急著去折騰字符串子串與集合子集的題目去了，一些其他的排序如希爾，計數，桶排序，基數排序全都跳過了，還好后來想想還是稍微學習一下，漲漲見識于是把這幾個視頻看了一遍。才發現事物是普遍聯系的，而老師前面給你花大時間精力講的全是基礎，反而沒花多少講的才是基礎之上的高階元素，只不過這些需要自己去拓展和鞏固。
希爾排序就是插入排序的基礎上的升級版，而另外三個是一步一步走向山巔的基石。先回來看希爾排序，我們剛剛完成了一個插入排序與二分查找相結合的排序方法，正沾沾自喜ing...然后看到了視頻中講解的希爾排序，如五雷轟頂般。
def shell_sort(arr):def insert_gap_sort(arr,gap): # 原插入排序代碼幾乎不動，把1改成gap即可for i in range(gap, len(arr)):tmp = arr[i]j = i - gapwhile j>=0 and arr[j]>tmp:arr[j+gap] = arr[j]j -= gaparr[j+gap] = tmpd = len(arr)//2while d>=1:insert_gap_sort(arr,d)d //= 2同樣的一個列表，使用希爾排序的時間是283.7 ms (0.28s)連半秒都不需要，而插入排序是216秒，而且希爾排序完全是建立在插入排序的基礎之上，只是根據數量分了組(gap)然后不斷做整除2的動作。
還是那句話，我們不能機械的只是用來做排序，我們要用不同的思路來解決類似的問題，我們需要舉一反三的應用，認真踏實的每一步都對你能達到的高度至關重要！
)
