算法和数据结构

算法：一个计算过程，解决问题的办法

递归

递归的两个必须条件

递推（调用自身）
回溯（结束条件）

来看几个例子：

eg1：该函数不是递归，没有结束条件

def func1(n):
    print(n)
    func1(n - 1)

eg2：该函数亦不是递归，虽有条件，但条件是无穷的

def func2(n):
    if n > 0:
        print(n)
        func2(n + 1)

eg3：该函数亦是递归，满足递归的两个条件

def func3(n):
    if n > 0:
        print(n)
        func3(n - 1)

eg4：该函数亦是递归，满足递归的两个条件

def func4(n):
    if n > 0:
        func4(n - 1)
        print(n)

那么，eg3 和 eg4的输出结果是一样的吗？如果不一样，为什么？

解释：

因为，func3执行的时候，print是在调用自身之前，所以当n是5传入函数时，会先打印5，再调用自身，这时候n是4,，依次循环递归。。。。到最后n=0，所以回溯时没有任何输出，所以func3 输出的结果是：5,4,3,2,1；而func4执行时，print是在调用自身之后，当n是5传入函数执行时，此时的n已经被减了1变成了4，再依次循环递归。。。。，再回溯的时候func4才有输出，的结果是：1,2,3,4,5

递归的简单使用，给出一个列表：[1, [2, [3, [4, [5, [6, [7, ]]]]]]]，需求：拿到列表中的元素（纯数字）

# coding=utf-8
li = [1, [2, [3, [4, [5, [6, [7, ]]]]]]]


def tell(li):
    for item in li:
        if type(item) is list:
            tell(item)
        else:
            print(item)


tell(li)

列表查找

顺序查找：最常用的就是for循环，挨个对比查找，效率极低！

二分查找：把一个列表一分为二（切片），判断要找的数大于还是小于中间值，大于则在右侧查找，小于在左侧查找。每次都是将列表一切为二进行查找！

原始的二分法（切片），时间复杂度为O(n)

def find(find_num, ll):
    print(ll)
    if len(ll) == 0:
        print('not find')
        return
    mid_index = len(ll) // 2
    if find_num > ll[mid_index]:
        ll = ll[mid_index + 1:]
        find(find_num, ll)
    elif find_num < ll[mid_index]:
        ll = ll[:mid_index]
        find(find_num, ll)
    else:
        print('find', ll[mid_index])


l = [1, 3, 5, 8, 12, 34, 45, 56, 67, 78, 89, 123, 234, 345, 456, 566, 789]
find(566, l)

改进后的二分法（不用切片），时间复杂度为O(logn)

def num_search(num_list, num):
    start = 0
    end = len(num_list) - 1
    while start <= end:
        mid = (end + start) // 2
        if num_list[mid] == num:
            return mid
        elif num_list[mid] < num:
            start = mid + 1
        else:
            end = mid - 1
    return


num_l = [i for i in range(1000)]
print(num_search(num_l, 666))

排序

冒泡排序

思路：比较列表相邻的两个数，如果前边的大于后边的，就交换这两个数。。。，（升序）

代码实现，时间复杂度：O(n*n)

import random


def sort_list(list1):
    for i in range(len(list1) - 1):
        for j in range(len(list1) - i - 1):
            if list1[j] > list1[j + 1]:
                list1[j], list1[j + 1] = list1[j + 1], list1[j]
    print('遍历次数： {}'.format(i))
    return list1


data = list(range(1000))
random.shuffle(data)
print(sort_list(data))

上面的代码虽然实现了冒泡排序，但是有个效率优化的问题，假设一个极端的例子，一个列表:[1,2,3,4,5,6,7,8,9]，按照上述的冒泡排序方法，程序会循环8次结束，但是在这个过程中，列表中的数字位置并未发生改变，那怎么解决这个问题呢？加一个变量来判断一次循环后数字的位置是否有改变，有就继续循环，没有就结束循环

import random


def sort_list(list1):
    for i in range(len(list1) - 1):
        change = 0
        for j in range(len(list1) - i - 1):
            if list1[j] > list1[j + 1]:
                list1[j], list1[j + 1] = list1[j + 1], list1[j]
                change = 1
        if change == 0:
            break
    print('遍历次数： {}'.format(i))
    return list1


data = list(range(1000))
random.shuffle(data)
print(sort_list(data))

改进后

选择排序

思路：循环列表，找到最小的值放到列表第一位，在遍历一次剩余数中的最小值，继续往后放。。。。

代码实现，时间复杂度：O(n*n)

def select_sort(li):
    for i in range(len(li) - 1):
        min_num = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_num]:
                min_num = j
        li[i], li[min_num] = li[min_num], li[i]


data = list(range(1000))
random.shuffle(data)
select_sort(data)
print(data)

插入排序

思路：列表分为无序区和有序区，最初的有序区只有一个值，每次从无序区选择一个值，插入到有序区的位置，直到无序区为空！