算法基础

　　递归

1 def func(num):
2     if num / 2 > 0:
3         num -= 1
4         print(num)
5         num = func(num)
6         print('quit')
7     return num
8 
9 func(10)

　　二分查找

 1 def binary_search(data_list,find_num):
 2     mid_pos = int(len(data_list) / 2)  # 计算需要查找数据的长度的一半
 3     mid_val = data_list[mid_pos]  # 获取中间位置的那个值
 4     print(data_list)  # 查看每次剩余筛选的数据列表
 5     if len(data_list) > 0:  # 当列表长度大于0时,则一直查找
 6         if mid_val > find_num:  # 如果中间的数比实际要查找的数大,那么这个数肯定在左边
 7             print("%s should be in left of [%s]" % (find_num, mid_val))
 8             binary_search(data_list[:mid_pos], find_num)
 9         elif mid_val < find_num:  # 如果中间的数比实际查找的数小,那么这个数肯定在右边
10             print("%s should be in right of [%s]" % (find_num, mid_val))
11             binary_search(data_list[mid_pos:], find_num)
12         else:  # 如果中间数与实际查找的数恰巧相等,那么这个数肯定是要找的拿个数
13             print("Find %s" % find_num)
14 
15     else:  # 否则就是买药这个数
16         print("cannot find [%s] in data_list" % find_num)
17 
18 if __name__ == '__main__':
19     primes = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
20     binary_search(primes, 1)   # 在列表里面查找1

二分查找二

 1 def binary_search(array, target):
 2     """
 3     二分查找
 4     前提是数组排序好的
 5     先把中间值找出来
 6     当中间元素大于查找的目标元素，则将左边的索引位置移动到中间位置的下一个位置
 7     当中间元素小于查找的目标元素，则将右边的索引位置移动到中间位置的上一个位置
 8     当中间元素等于查找的目标元素，则停止查找，返回目标元素位置
 9     :param array:
10     :param target:
11     :return:
12     """
13     left = 0
14     right = len(array) - 1
15     while left <= right:
16         mid_position = (left + right) // 2
17         if array[mid_position] == target:
18             return mid_position
19         elif target < array[mid_position]:
20             right = mid_position - 1
21         else:
22             left = mid_position + 1
23     return -1

多维数组交叉

 1 array = [[col for col in range(4)] for row in range(4)]  # 初始化一个4*4数组
 2 # array=[[col for col in 'abcd'] for row in range(4)]
 3 
 4 for row in array:  # 旋转前先看看数组长啥样
 5     print(row)
 6 
 7 for i, row in enumerate(array):
 8 
 9     for index in range(i, len(row)):
10         tmp = array[index][i]  # 将每一列数据在每一次遍历前,临时存储
11         array[index][i] = array[i][index]  # 将每一次遍历行的值,赋值给交叉的列
12         print(tmp, array[i][index])  # = tmp
13         array[i][index] = tmp  # 将之前保存的交叉列的值,赋值给交叉行的对应值
14     for r in array:  # 打印每次交换后的值
15         print(r)

冒泡排序

 1 def bubble_sort(array):
 2     """
 3     每次将后面的元素大于前面的元素交换位置
 4     :param array:
 5     :return:
 6     """
 7     for i in range(len(array)):
 8         for j in range(i + 1, len(array)):
 9             if array[i] > array[j]:
10                 array[i], array[j] = array[j], array[i]

插入排序

 1 def insert_sort(array):
 2     """
 3     找出最小位置，然后替换
 4     :param array:
 5     :return:
 6     """
 7     for i in range(len(array)):
 8         key = array[i]
 9         j = i - 1
10         while j >= 0 and array[j] > key:
11             array[j + 1] = array[j]
12             j -= 1
13         array[j + 1] = key

选择排序

 1 def select_sort(array):
 2     """
 3     选则一个最小的位置，然后交换两个元素的位置
 4     :param array:
 5     :return:
 6     """
 7     for i in range(len(array) - 1):
 8         min_index = i
 9         for j in range(i + 1, len(array)):
10             if array[j] < array[min_index]:
11                 min_index = j
12         array[i], array[min_index] = array[min_index], array[i]

快速排序

def quick_sort(array):
    """
    将一个数组分割为三份，一个为基数，一个是比基数大的列表，一个是比基数小的列表
    然后再将比基数小的列表按照上面方式再分三份，直到分到不能再分位置
    同样，也将比基数大的列表按上述分三份，直到不能再分为止
    最后合并得到一个排序好的列表
    :param array:
    :return:
    """
    if len(array) < 2:
        return array
    first_element = array[0]
    left = [i for i in array[1:] if i <= first_element]
    right = [i for i in array[1:] if i > first_element]
    return quick_sort(left) + [first_element] + quick_sort(right)

快速排序二

 1 def partition(array, p, r):
 2     x = array[r]
 3     i = p - 1
 4     for j in range(p, r):
 5         if array[j] <= x:
 6             i = i + 1
 7             array[i], array[j] = array[j], array[i]
 8     array[i + 1], array[r] = array[r], array[i + 1]
 9     return i + 1
10 
11 
12 def quick_sort2(array, p, r):
13     if p < r:
14         q = partition(array, p, r)
15         quick_sort2(array, p, q - 1)
16         quick_sort2(array, q + 1, r)

斐波那契数列

1 def fibonacci(n):
2     a, b = 0, 1
3     while n > 0:
4         yield b
5         a, b = b, a + b
6         n -= 1

阶乘

 1 def factorial(n):
 2     """
 3     阶乘
 4     1 * 2 * ... * n
 5     直到n为1，则返回，然后合并相乘
 6     :param n:
 7     :return:
 8     """
 9     # return n * factorial(n - 1) if n != 1 else n
10     result = 1
11     for i in range(1, n + 1):
12         result *= i
13     return result

线性搜索

 1 def line_search(array, target):
 2     """
 3     线性查找
 4     按照数组顺序，依次查找目标元素
 5     :param array:
 6     :param target:
 7     :return:
 8     """
 9     position = 0
10     while position < len(array):
11         if array[position] == target:
12             return position
13         position += 1
14     return -1