事实上，入门算法最好是从C/C++入手，对于一些数据结构可以有更深刻的理解，这篇笔记只是由于博主参加蓝桥杯报名的python组而去进行的粗浅学习，放在这里仅仅是作为”撑场面”的存在，如果让我现在再学习我会推荐https://labuladong.online/algo/home/

一.时间复杂度与空间复杂度

1.时间复杂度

​ 时间复杂度表示程序运行的**“估算的”**单位时长，可以理解为是一个时间单位，它并不与程序在某一台机器上运行的实际时长挂钩。

​ 时间复杂度使用O()来表示，一般来说，时间复杂度根据问群体规模来确定n，并根据算法确定具体的复杂度。

2.空间复杂度

​ 同样地，空间复杂度则表示**“估算的“**内存用量，同样可以理解为一个空间单位，并不是某一种语言在某一个机器下的内存占用。

​ 同样，空间复杂度也使用O()来表示，空间复杂度则根据数据类型来确定：

  • 仅使用变量：O(1)
  • 使用长度为n的列表：O(n)
  • 使用边长为n的二维列表：O(n2)

由于内存造价比较便宜，相比较之下，时间比空间更为重要。

二.递归

  • 递归的特点：

    • 调用自身
    • 结束条件

  • 汉诺塔问题

​ 事实上，汉诺塔(Hannoi Tower)问题就是很典型的递归,要设法将n(n>2)个盘子按规定的方式从a柱移动到b柱，当n过于庞大时，是没有办法一次性求解出的，但是，我们通过推理发现移动n个盘子和移动n-1个盘子之间存在联系：

  1. 将n-1个盘子通过b移动到c
  2. 将第n个盘子移动到b
  3. 将n-1个盘子从c通过a移动到b

当我们将前n-1个盘子打包看作一个整体时，有以上移动方法，同样的n-1个盘子也一样，以此类推，一直到n=2时，这样就实现了复杂问题的简单子问题化。

三.查找

​ 查找是指在一批次数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。

1.顺序查找(线性查找)

​ 从列表第一个元素开始，顺序进行搜索，直到找到元素或者搜索完列表为止。

def linear_search(data_set, value):
    for i in range(len(data_set)-1):
        if data_set[i] == value:
            return i
     return None

2.折半查找(二分查找)

​ 二分查找要求列表是有序的。(以下是一个从小到大排序的数据容器data_set)

def binary_search(data_set, value):
    left = 0
    right = len(data_set)-1
    while left <= right:
        mid = (left + right) // 2
        if data_set[mid] == value:
            return mid
        elif data_set[mid] > value:
           	right = mid - 1
        else:
            left = mid + 1
   	return None

三.排序

​ 排序即将一组“无序”的记录序列调整为“有序”的记录序列。

1.冒泡排序

​ 以升序为例如下：

def bubble_sort(data_set):
    for i in range(len(data_set)-1):
        for j in range(len(data_set)-i-1):
            if data_set[j] > data_set[j+1]:
                data_set[j], data_set[j+1] = data_set[j+1], data_set[j]

2.选择排序

​ 遍历列表，每遍历一次得到最小数据并排入新列表

def select_sort(data_set):
    set_new = []
    for i in range(len(data_set)):
        min_val = min(data_set)
        set_new.append(min_val)
        data_set.remove(min_val)
    return set_new

这种排序方式并不好，需要建立一个新的数据容器，会重新申请内存空间，并且remove方法也会增加程序的时间复杂度。遵循原地排序且时间复杂度更低的原则，对其做出以下优化：

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

3.插入排序

在无序空间中划出一块有序空间，再基于有序空间从无序空间中拿取数据并排列。形似斗地主中的抓牌洗牌

def insert_sort(data_set):
    for i in range(1,len(data_set)): #i表示无序区的牌的下标
        tmp = data_set[i]
        j = i-1 #j表示手里摸到的牌的下标
        while j>=0 and data_set[j]>tmp:
            data_set[j+1] = data_set[j]
            j -= 1
   		data_set[j+1] = tmp

4.快速排序

​ 选定第一个元素，将比它大的排到它右边，比它小的排到左边，再重复这个工作，最终就能得到有序的列表。

def partition(data_set,left,right):
    tmp = data_set[left] #临时变量保存第一个数据
	while left < right:	#保证当left==right时退出循环
        while left < right and  data_set[right] >= tmp:
            right -= 1
       	data_set[left] = data_set[right]
        while left < right and data_set[left] <= tmp:
            left += 1
       	data_set[right] = data_set[left]
   	data_set[left] = tmp
    return left
def quick_sort(data_set,left,right):
    if left<right:
    	mid = partition(data_set,left,right)
    	quick_sort(data_set,left,mid-1)
    	quick_sort(data_set,mid+1,right)

5.堆排序

1.堆排序前置知识

树与二叉树

  • 树是一种数据结构，比如计算机目录结构

  • 树是一种可以定义递归的结构

  • 树是由n个节点组成的集合

    • 如果n=0，是空树
    • 如果n>0，那存在一个节点作为树的根节点，其他节点可以分为m个集合，而每个集合本身又是一棵树

  • 树的度：最大分叉数

  • 树的深度：分叉层数

  • 叶节点：度为0的节点

  • 二叉树：度不超过2的树

  • 满二叉树：每一层节点都达到最大值的二叉树

  • 完全二叉树：叶节点只出现在最下层和次下层，且最下层节点都集中在该层最左边的若干位置的二叉树

二叉树的存储方式
  • 链式存储方式(之后数据结构中讲)
  • 顺序存储方式

如果将一个二叉树的结构以列表的形式从根节点从左往右顺序表示，那么父子节点间关系如下：

  1. 左子节点下标 = 2*父节点下标+1
  2. 右子节点下标 = 2*父节点下标+2
堆(特殊的完全二叉树)
  • 大根堆：父节点总是大于子节点
  • 小根堆：父节点总是小于子节点

堆的向下调整：

当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆

2.堆排序

堆排序大致上分为两步：

  • 建立堆(“农村包围城市”)
  • 从根节点拿数
  • 向下调整
#向下调整函数
def sift_big(data_set,low,high):	#low指向根节点，high指堆的最后一个元素
    i = low
    j = 2 * i + 1
    tmp = data_set[low]
    while j <= high:
        if j+1 <= high and data_set[j+1] > data_set[j]:
            j += 1 
       	if data_set[j] > tmp:
        	data_set[i] = data_set[j]
            i = j
            j = 2 * i + 1
        else:
            data_set[i] = tmp
            break
   	else:
    	data_set[i] = tmp
        
#堆排序
def heap_sort(data_set):
    n = len(data_set)
    for i in range((n-2)//2,-1,-1):
        #i表示建堆的时候调整的部分的根的下标
        sift_big(data_set,i,n-1)  #至此，建堆完成
	for i in range(n-1,-1,-1):
        #i指向当前堆的最后一个元素
        data_set[0], data_set[i] = data_set[i], data_set[0]
        sift_big(data_set,0,i-1)

heapq 基本操作

1. 创建最小堆

heapq 直接在 Python 列表 上操作，并不会创建新的数据结构。

python复制编辑import heapq

# 定义一个列表
nums = [5, 3, 8, 1, 2]

# 转换为最小堆
heapq.heapify(nums)
print(nums)  # 输出：[1, 2, 8, 3, 5]  （堆的内部结构，不是完全排序）

heapify() 只保证堆的特性：最小元素在索引 0，但不是完整排序的列表。

2. 插入元素

heapq.heappush(heap, item)：插入新元素，保持最小堆特性。

python复制编辑heapq.heappush(nums, 4)
print(nums)  # 输出：[1, 2, 4, 3, 5, 8]

3. 弹出最小元素

heapq.heappop(heap)：删除并返回最小值。

python复制编辑min_value = heapq.heappop(nums)
print(min_value)  # 输出：1
print(nums)  # 输出：[2, 3, 4, 5, 8]

4. 替换堆顶

heapq.heapreplace(heap, item)：删除堆顶元素，并插入 item，保证堆的特性。

python复制编辑heapq.heapreplace(nums, 6)
print(nums)  # 输出：[2, 3, 4, 6, 8]

⚠️ 与 heappop + heappush 的区别：

  • heapreplace() 是一步完成的，效率更高 O(log n)
  • heappop() + heappush() 是两步，需要 2 * O(log n)

5. 获取最小的 K 个元素

heapq.nsmallest(k, iterable)：返回 前 k 小 的元素。

python复制编辑nums = [5, 3, 8, 1, 2]
smallest_3 = heapq.nsmallest(3, nums)
print(smallest_3)  # 输出：[1, 2, 3]

类似的： heapq.nlargest(k, iterable)：返回 前 k 大 的元素。

topk问题

topk问题，指在n个数中，设计算法得到前k大的数(k<n)

解决思路：

  • 排序后切片 O(nlogn)
  • LowB三人组 O(nk)
  • 堆排序 O(nlogk)

堆排序解决思路:

  • 选取前k个元素建立小根堆，根节点元素就是这个小根堆第k大的元素
  • 从第k-1个元素开始，依次与根节点元素比较，小的略过，大的代替，并向下调整
  • 重复第二步操作直到列表最后一个元素
def sift_small(data_set,low,high):	#low指向根节点，high指堆的最后一个元素
    i = low
    j = 2 * i + 1
    tmp = data_set[low]
    while j <= high:
        if j+1 <= high and data_set[j+1] < data_set[j]:
            j += 1 
       	if data_set[j] < tmp:
        	data_set[i] = data_set[j]
            i = j
            j = 2 * i + 1
        else:
            data_set[i] = tmp
            break
   	else:
    	data_set[i] = tmp
        
def topk(data_set,k):
    heap = data_set[0:k]
    for i in range((k-2)//2, -1, -1):
        sift_small(heap,i,k-1)
   	for i in range(k, len(data_set)):
        if data_set[i] > heap[0]:
            heap[0] = data_set[i]
            sift_small(heap,0,k-1)
  	for i in range(k-1,-1,-1):
        heap[0], heap[i] = heap[i], heap[0]
        sift_small(heap,0,i-1)
 	return heap

6.归并排序

假设列表分两段有序，将其合为一个有序列表的操作成为一次归并

def merge(data_set,low,mid,high):
  	i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if data_set[i] < data_set[j]:
            ltmp.append(data_set[i])
            i += 1
        else:
            ltmp.append(data_set[j])
            j += 1
 	while i <= mid:
        ltmp.append(data_set[i])
        i += 1
 	while j <= high:
        ltmp.append(data_set[j])
        j += 1
  	data_set[low:high+1] = ltmp

def merge_sort(data_set,low,high):
    if low < high: #保证data_set至少两个元素
        mid = (low + high)//2
        merge_sort(data_set,low,mid)
        merge_sort(data_set,mid+1,high)
        merge(data_set,low,mid,high)	
        #当列表仅有两个元素时第一次执行merge函数，这样一来，mid左右一定是有序的

7.希尔排序

希尔排序本质上是分组插入排序，每次分组之后，列表会接近于有序的状态，最后一次分组结束会完全有序

def insert_sort_gap(data_set,gap):
    for i in range(gap,len(data_set)): #i表示无序区的牌的下标
        tmp = data_set[i]
        j = i-gap #j表示手里摸到的牌的下标
        while j>=0 and data_set[j]>tmp:
            data_set[j+gap] = data_set[j]
            j -= gap
   		data_set[j+gap] = tmp
def shell_sort(data_set):
    d = len(data_set)//2
    while d >= 1:
        insert_sort_gap(data_set,d)
        d //= 2

需要注意的是，希尔排序的时间复杂度取决于gap的取值方式，详见https://en.wikipedia.org/wiki/Shellsort

8.计数排序

非比较排序，需要知道列表元素的上界和下界，适用于大量且密集的数据集合

def count_sort(data_set,low,high):
    count = [0 for _ in range(low,high+1)]
    for val in data_set:
        count[val] += 1
  	data_set.clear()
    for i in range(low,high+1):
        while count[i] != 0:
            for j in range(count[i]):
                data_set.append(i)	#这是循环操作，大部分语言通用
#或者
def count_sort(data_set,low,high):
    count = [0 for _ in range(low,high+1)]
    for val in data_set:
        count[val] += 1
   	for index, val in enumerate(count):		
        #运用python内置函数enumerate，通过for循环截取count列表的下标和值
        for i in range(val):
            data_set.append(index)

9.桶排序

桶排序，指的是知道上界与下界的情况下，以上下界为基准均分为若干个“桶”，每个“桶”的上下界也知道，进而在桶里使用计数排序或其他排序

def bucket_sort(data_set,n,low,high):  #n表示桶的个数
    buckets = [[] for _ in range(n)]
    for var in data_set:
        i = min((var-low)//((high-low)//n),n-1)  #防止var==high的情况
        buckets[i].append(var)
        #分桶完成
 	#以下可以等完全分完桶后对每一个buckets[i]进行计数排序或者其他排序，也可以边分桶边排序：
    	for j in range(len(buckets[i])-1,0,-1):  #j表示buckets[i]中无序区最后一个元素的下标
            if buckets[i][j] <buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
            else:
                break
   	sorted_data_set = []
    for buc in buckets:
        sorted_data_set.extend(buc)
   	return sorted_data_set

桶排序的时间复杂度取决于数据的分布情况

10.基数排序

本质上是多关键词排序，实现方法用到分桶

def radix_sort(data_set):
    max_num = max(data_set)
    it = 0 # it表示迭代轮数
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)] #0~9分十个桶
        for var in data_set:
            digit = (var // 10 ** it) % 10
            buckets[digit].append(var)
            #分桶完成
            data_set.clear()
            for buc in buckets:
                data_set.extend(buc)
           	#数据写回data_set
            it += 1