蒙珣的博客

活好当下，做好今天该做的事情。

0%

python 算法（持续更新）

Posted on Edited on In
Symbols count in article: 2.7k Reading time ≈ 2 mins.

递归

递归的两个特点：

  • 调用自身
  • 结束条件

两个递归实例：

先打印结果再调用自身

1
2
3
4
5
6
def func1(x):
  if x>0:
    print(x)
    func1(x-1)
    
func1(5)

结果：

1
2
3
4
5
5
4
3
2
1

先调用自身再打印结果

1
2
3
4
5
6
def func2(x):
  if x>0:
  	func2(x-1)
    print(x)
    
func2(5)

结果

1
2
3
4
5
1
2
3
4
5



汉诺塔（hanoi）

思考

n个盘子时：

  1. 把n-1个盘子从A经过C移动到B
  2. 把第n个盘子从A移动到C
  3. 把n-1个小盘子从B经过A移动到C
1
2
3
4
5
6
7
8
9
10
11
12
# n个盘子，a、b、c三个柱子
def hanoi(n,a,b,c):
  # 盘子的数量大于0，不然就减成负数了
  if n>0:
    # 我们会通过很多步骤讲n-1个盘子经过c柱子移动到b柱子上
    hanoi(n-1,a,c,b)
    # 再将最底下的盘子n移动到c上
    print("moving form %s to %s" % (a,c))
    # 再将b柱子上的盘子经过a移动到c上
    hanoi(n-1,b,a,c)
 
hanoi(3,"A","B","C")

输出结果：

1
2
3
4
5
6
7
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C



查找

列表查找（Linear Search）

列表查找（线性表查找）：从列表中查找指定元素

  • 输入：列表、待查找元素
  • 输出：元素下标（未找到元素时一般返回None或-1）

内置列表查找函数：index（）

顺序查找：也叫线性查找，从列表第一个元素开始，顺序搜索，直到找到元素或搜索到列表最后一个元素为止

1
2
3
4
5
6
7
8
9
10
11
12
#传入一个列表，与要查找的值
def linearSearch(li,val):
    for ind,v in enumerate(li):
        if v == val:
            return ind
    else:
        return None

li = [2,5,6,8,1,5]
val = 10

print(LinearSearch(li,val))

时间复杂度：O(n)



二分查找（Binary Search）

二分查找：又叫折半查找，从有序列表的初始候选区li[O:n]开始 ，通过对待查找的值与候选区域中间值得比较，可以使候选区减少一半

二分查找需要先排序，但是有可能排序时间要远多于线性查找O(n)，所以如果你对这个列表需要以后的多次查找，可以使用二分查找

Python的内置查找函数：.index()是线性查找的，因为没办法确定列表是有序的

1
2
3
4
5
6
7
8
9
10
11
12
13
def binarySearch(li,val):
  left = 0
  right = len(li)-1
while left <= right:		# 候选区有值就循环
  mid = (left+right)//2
  if li[mid] < val:
    left = left[mid]+1
  elif li[mid] > val:
    right = right[mid]-1
  elif li[mid] == val:
    return mid
else:
  return None

时间复杂度：O(logn)



排序

常见排序书算法

  1. 排序Low B三人组

    • 冒泡排序
    • 选择排序
    • 插入排序

  2. 排序NB三人组

    • 快速排序
    • 堆排序
    • 归并排序

  3. 其他排序

    • 希尔排序
    • 计数排序
    • 基数排序

列表排序

  • 列表排序：将无序的列表变为有序的列表
    • 输入：列表
    • 输出：有序列表
  • 升序与降序
  • 内置排序函数：sort()



冒泡排序（Bubble Sort）

  • 列表每两个相邻的数，如果前面比后面大，则交换这两个数。
  • 一趟排序完成后，则无序区减少一个数，有序区增加一个数。
1
2
3
4
5
6
7
8
9
10
def bubbleSort(li):
  for i in range(len(li)-1):
    for k in range(li)-i-1:
      if li[k] > li[k+1]:
        li[k],li[k+1] = li[k+1],li[k]

li = [random.randint(0,10000) for i in range(1000)]
print(li)
bubble_sort(li)
print(li)



选择排序 （Select Sort）

  • 一趟排序记录最小的数，放到第一个位置
  • 再一趟排序记录记录列表无序区最小的数，放到第二个位置
  • 算法关键点：有序区和无序区、无序区最小数的位置

方法一「不推荐」

1
2
3
4
5
6
7
def select_sort(li):
  li_new = []
  for i in range(len(li)):
    min_val = min(li)
    li_new.append(min_val)
    li.remove(min_val)
  return li
  • min()函数的时间复杂度为O(n)
  • remove()函数的时间复杂度为O(n)，因为删除列表的一个个数后，需要将被删除数后的其他数一一移动一个位置
  • 因为新创建了一个列表，所以他的空间复杂度也增加了

方法二

1
2
3
4
5
6
7
8
def select_sort(li):
  for i in range(len(li)-1):	# i是第几趟
    min_loc = i
    for j in range(i+1,len(li)):
			if li[j] < li[min_loc]:
        min_loc = j
    li[j],li[min_loc] = li[min_loc],li[j]
  return li



插入排序（Insert Sort）

  • 初始时手里（有序区）只有一张手牌
  • 每次（从无序区）摸一张牌，插入到手里已有牌的正确位置
1
2
3
4
5
6
7
8
9
10
11
12
def insert_sort(li):
  for i in range(1,len(li)):			# i 指摸到牌的下标
    tmp = li[i]
    j = i - 1											# j 指手里牌的下标
    while j >= 0 and li[j] > tmp:
      li[j+1] = li[j]
      j -= 1
    li[j+1] = tmp
      
li = [3,5,7,9,0,1,2,4]
insert_sort(li)
print(li)
  • 时间复杂度为：O(n^2)



快速排序（Quick_sort）

  • 取一个元素p（第一个元素），使元素p归位；
  • 列表被p分成两部分，左边都比p小，右边都比p大
  • 递归完成排序

快速排序-框架

1
2
3
4
5
def quick_sort(data,left,right):
  if left < right:
    mid = partition(data,left,right)
    quick_sort(data,left,mid-1)
   	quick_sort(data,mid+1,right)