算法_python_学习记录_01
人心的成见是一座大山。一旦有山挡在面前，则很难到达下一站。所需要做的，是穿过这座山。
偶然间看了一个视频，说的是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的动作。
还是那句话，我们不能机械的只是用来做排序，我们要用不同的思路来解决类似的问题，我们需要举一反三的应用，认真踏实的每一步都对你能达到的高度至关重要！