数据结构与算法（python）1

自学笔记：

本文章包含递归和三种排序方法：冒泡排序、选择排序和插入排序。

---

1.递归

两种递归方式：

def func1(x):
    if x>0:
        func(x-1)
        print(x)

def func2(x):
    if x>0:
        print(x)
        func1(x-1)

func1(3)
func2(3)

输出结果分别为：

func1(3)：

1

2

3

func2(3):

3

2

1

汉诺塔递归:    
n个盘子从a经过b移动到c：    
1.把n-1个盘子从a经过c移动到b    
2.把第n个盘子从a移动到c     
3.把n-1个小圆盘从b经过a移动到c

def hanoi(n,a,b,c):
    if n>0:
        hanoi(n-1,a,c,b)
        print("%s 号圆盘moving from %s to %s"%(n,a,c))
        hanoi(n-1,b,a,c)
hanoi(3,'A柱','B柱','C柱')

打印结果：

1 号圆盘moving from A柱 to C柱
2 号圆盘moving from A柱 to B柱
1 号圆盘moving from C柱 to B柱
3 号圆盘moving from A柱 to C柱
1 号圆盘moving from B柱 to A柱
2 号圆盘moving from B柱 to C柱
1 号圆盘moving from A柱 to C柱

递归小结：

 3个LOW B排序方法：冒泡排序、选择排序、插入排序 时间复杂度都是O(n^2)：
都是原地排序
2.冒泡排序

#升序冒泡排序
def bubble_sort(li):
    for i in range(len(li)-1):#i表示趟
        exchange = False #交换标志位
        for j in range(len(li)-i-1):#j表示无序区长度
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]#交换值
                enchange = True
        if not exchange:#在无序区中没有元素交换，即列表已按顺序排好
            return #结束冒泡排序

3.选择排序

#简单选择排序缺陷：
#1.定义了两个列表,占用空间多，计算时间长
#2.min函数和remove函数最低复杂度为O(n)
#3.导致整个函数最低复杂度为O(n*n)
def select_sort_simple(li):
    li_new = []#储存原列表最小元素
    for i in range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new

#一个比较好的选择排序：将最小元素与第一个元素交换位置
#复杂度：O(n*n)
def select_sort(li):
    for i in range(len(li)-1):#i表示趟
        min_loc = i #记录无序区最小值的位置
        for j in range(i,len(li)):#j表示无序区
            if li[j] < li[min_loc]:
                min_loc = j #与冒泡排序的不同
        li[i],li[min_loc] = li[min_loc],li[i]#每趟只交换一次最小值和当前数据
     

4.插入排序

#时间复杂度：O(n*n)
def insert_sort(li):
    for i in range(1,len(li)):#i表示摸到的牌的下标
        tmp = li[i]#用tmp：
        j=i-1#一列牌的下标
        while j>=0 and li[j] > tmp:#循环用于查找插牌位置
            li[j+1]=li[j]
            j -= 1
        li[j+1] = tmp