冒泡排序,递归函数,二分法排序

冒泡排序

给出一个纯数字列表. 请对列表进行排序
思路:

完成 a 和 b 的数据交换. 例如, a = 10, b = 24 交换之后, a = 24, b = 10
循环列表. 判断 a[i] 和 a[i+1] 之间的大小关系, 如果 a[i] 比 a[i+1] 大. 则进行互换. 循环结束的时候.当前列表中最大的数据就会被移动到最右端.
想一想, 如果再次执行一次上面的操作. 最终第二大的数据就移动到了右端. 以此类推. 如果反复的进行执行相应的操作.那这个列表就变成了一个有序列表

lst = [10,2,3,4,1,5,7,6,9,8]
for j in range(len(lst)-1):   #第二次循环的时候是从第1个元素到倒数第2个元素,最后一个已经排列好了,就是第一次循环找出来的最大的,所以不用再循环一次
    for i in range(len(lst)-1-j):  #当lst里有两个元素的时候只循环一遍, 所以当lst里有10个元素的时候,循环9次就可以
        if lst[i] > lst[i+1]:
            lst[i],lst[i+1] = lst[i+1],lst[i]
print(lst) #[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

递归函数

自己调用自己

我们可以使用递归来遍历各种树形结构, 比如我们的文件夹系统. 可以使用递归遍历该文件夹中的所有文件

import os
def func(filepath, n): # d:/sylar/
    files = os.listdir(filepath)      #获取到当前文件夹中所有的文件
    for file in files:      　　　　　　#遍历文件夹中的文件,这里获取的是本层的文件名
        f_d = os.path.join(filepath, file)   #加入文件夹 获取到文件夹+文件d:/sylar/文件名
        if os.path.isdir(f_d):     　　　　　　#如果该路径下的文件是文件夹
            print("	"*n, file,":")     　　　#打印文件名
            func(f_d, n + 1)  　　　　　　　　　#继续进行相同操作
        else:    　　　　　　　　　　 #不是文件夹. 普通文件
            print("	"*n, file)   #递归出口,最终这里隐含着return

func("d:/sylar",0)

二分法查找

核心:掐头去尾取中间一次砍一半

两种算法: 常规算法和递归算法

二分查找每次能够排除掉一半的数据,查找的效率很高,但是局限性很大,必须是有序的序列才可以使用二分查找

要求:查找的序列必须是有序序列

# 判断n是否在lst中出现. 如果出现请返回n所在的位置
# 二分查找---非递归算法
lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789]
n = 101
left = 0
right = len(lst)-1   #索引值比长度少1
#count = 1
while left <= right:
    mid = (left + right)//2
    if n > lst[mid]:
        left = mid + 1
    if n <lst[mid]:
        right = mid - 1
    if n == lst[mid]:
        print("找到了")
        print(mid)
        #print(count)
        break
    #count = count + 1
else:
    print("不存在")

# 判断n是否在lst中出现. 如果出现请返回n所在的位置
# 二分查找---递归算法
lst = [22, 33, 44, 55, 66, 77, 88, 99, 101, 238, 345, 456, 567, 678, 789]

def func(n,left,right):
    if left <= right:
        mid = (left + right)//2
        if n > lst[mid]:
            left = mid + 1
            return func(n,left,right)
        if n < lst[mid]:
            right = mid - 1
            # 深坑. 函数的返回值返回给调用者
            return func(n,left,right)
        else:
            print("找到了")
            return mid
    else:
        print("不存在")
        return -1
ret = func(101,0,len(lst)-1)
print(ret)