【算法】汉诺塔、顺序查找和二分查找法、冒泡排序、插入排序、选择排序

1 时间装饰器
2 汉诺塔
3 顺序查找和二分查找法
4 冒泡排序
5 插入排序
6 选择排序

1 时间装饰器

import timedef cal_time(func):def wrapper(*args, **kwargs):t1 = time.time()result = func(*args, **kwargs)t2 = time.time()print("%s running time: %s secs." % (func.__name__, t2 - t1))return resultreturn wrapper

2 汉诺塔

"""
汉诺塔（Tower of Hanoi）是一个经典的数学问题，由法国数学家爱德华·卢卡斯（Édouard Lucas）在1883年提出。
它由三个柱子和若干个直径不同的圆盘组成。起初，所有的圆盘都按直径从大到小堆叠在第一个柱子上。
问题的目标是通过一些步骤将整个圆盘堆移动到另一个柱子上，且在移动过程中需要遵守以下规则：1. 每次只能移动一个圆盘。
2. 每次移动的圆盘必须放在另一个柱子上，并且放置在那个柱子上已经存在的圆盘之上（如果有的话），且必须小于下方的圆盘。这个问题的核心是找到最少的步骤将所有的圆盘移动到目标柱子上。对于n个圆盘，最少的移动次数是 \(2^n - 1\)。### 例子
假设有3个圆盘，初始状态如下：
- 圆盘1（最小）在最上面，圆盘3（最大）在最下面，都在柱子A上。目标是将这3个圆盘按照同样的顺序移动到柱子C上。最少的移动步骤为：
1. 将圆盘1从柱子A移动到柱子C。
2. 将圆盘2从柱子A移动到柱子B。
3. 将圆盘1从柱子C移动到柱子B（放在圆盘2上）。
4. 将圆盘3从柱子A移动到柱子C。
5. 将圆盘1从柱子B移动到柱子A。
6. 将圆盘2从柱子B移动到柱子C（放在圆盘3上）。
7. 将圆盘1从柱子A移动到柱子C（放在圆盘2上）。### 数学表达式
汉诺塔问题的最优解可以用递归算法来表示，其中：
- \( T(n) \) 表示移动n个圆盘所需的最少步数。
- 对于n个圆盘，递归公式为 \( T(n) = 2T(n-1) + 1 \)，其中 \( T(1) = 1 \)。汉诺塔问题的时间复杂度是 指数级别的。
具体来说，对于有n个圆盘的汉诺塔问题，最少的移动次数为2的n次方−1。
因此，汉诺塔问题的时间复杂度为O(2的n次方)。"""def hanoi(n, a, b, c):if n > 0:hanoi(n - 1, a, c, b)print("moving from %s to %s" % (a, c))hanoi(n - 1, b, a, c)hanoi(3, 'A', 'B', 'C')

3 顺序查找和二分查找法

from cal_time import *@cal_time
def linear_search(li, val):  # 线性排序for ind, v in enumerate(li):if v == val:return indelse:return None@cal_time
def binary_search(li: list, val: int):"""二分查找法（Binary Search）是一种高效的查找算法，适用于在一个已经排序的数组或列表中查找某个特定的元素。二分查找的核心思想是将搜索范围不断折半，从而迅速缩小查找范围。工作原理二分查找通过以下步骤来查找目标值：初始化：设定两个指针，分别指向数组的起始位置和结束位置，通常称为 left 和 right。查找中间元素：计算中间位置 mid，mid 的索引通常通过公式 mid = (left + right) // 2 计算。将目标值与 mid 位置的元素进行比较。缩小范围：如果目标值等于 mid 位置的元素，则查找成功，返回该元素的索引。如果目标值小于 mid 位置的元素，说明目标值在左半部分，于是将 right 更新为 mid - 1。如果目标值大于 mid 位置的元素，说明目标值在右半部分，于是将 left 更新为 mid + 1。重复：重复以上步骤，直到找到目标值或搜索范围为空（即 left > right）。返回结果：如果找到目标值，返回其索引。如果找不到，通常返回 -1 或其他特定值以表示查找失败。时间复杂度二分查找的时间复杂度为O(logn)，其中 n 是数组中的元素数量。相比于线性查找O(n)，二分查找在处理大规模数据时更加高效。注意事项前提条件：二分查找只适用于已排序的数组或列表。数据类型：二分查找的对象通常是可索引的序列（如数组或列表）。:param li::param val::return:"""left = 0right = len(li) - 1while left <= right:  # 候选区有值mid = (left + right) // 2if li[mid] == val:return midelif li[mid] > val:  # 带查找的值在mid左侧right = mid - 1else:  # li[mid] < val 带查找的值在mid右侧left = mid + 1else:return Noneli = list(range(1000))
# linear_search(li, 389)
binary_search(li, 389)

4 冒泡排序

"""
冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历要排序的列表，
比较相邻的元素并根据需要交换它们的位置，使得每一轮遍历之后，最大的元素“冒泡”到列表的末尾。
这个过程不断重复，直到整个列表有序为止。算法步骤
从列表的第一个元素开始，依次比较相邻的两个元素。
如果前一个元素大于后一个元素，则交换它们的位置。
对每一对相邻元素执行相同的操作，从列表开始到最后的未排序部分为止。
完成一次遍历后，最大的元素就会移动到列表的末尾。
忽略列表中已排序的部分，重复上述步骤，直到没有元素需要交换，列表排序完成。时间复杂度
冒泡排序的最坏情况和平均时间复杂度均为
O(n的2次方)，其中n 是列表中元素的数量。
虽然这个算法很简单，但由于其效率较低，在实际应用中，通常仅用于教育目的或非常小的数据集
"""import random
from cal_time import *@cal_time
def bubble_sort(li: list) -> None:for i in range(len(li) - 1):  # 第i趟exchange = Falsefor j in range(len(li) - i - 1):if li[j] > li[j + 1]:li[j], li[j + 1] = li[j + 1], li[j]exchange = Trueif not exchange:returnli = list(range(10000))
random.shuffle(li)  # 用于随机打乱（洗牌）一个列表中的元素顺序bubble_sort(li)

5 插入排序

"""
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理类似于人们排序扑克牌：
每次将一个新的元素插入到已经排好序的部分中。这个算法对于小规模数据集或者部分已经排序的数据集非常有效。算法步骤
开始：从第二个元素（索引为1）开始，将其视为待插入的元素。
插入：将该元素与它之前的元素依次比较。如果该元素比前面的元素小，就将前面的元素向后移动一位，直到找到一个合适的位置将该元素插入。
重复：对每一个未排序的元素重复上述步骤，直到整个数组有序。时间复杂度
插入排序的时间复杂度为O(n2)，其中 n 是数组中的元素数量。在最佳情况下（数组已经有序），时间复杂度为O(n)。
尽管它的效率不如更复杂的排序算法，但由于其简单性和在某些情况下的有效性，插入排序仍然是一个有用的工具。
"""def insert_sort(li: list):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 -= 1li[j + 1] = tmpprint(li)li = [3, 2, 4, 1, 5, 7, 9, 6, 8]
# print(li)
insert_sort(li)

6 选择排序

"""
选择排序（Selection Sort）是一种简单的排序算法，
它的基本思想是每一轮从未排序的部分中选择最小（或最大）的元素，并将其放在已排序部分的末尾。
通过不断地选择和交换位置，最终使整个列表有序。算法步骤
从未排序的列表中找到最小（或最大）的元素。
将这个元素与未排序部分的第一个元素交换位置，确保这个最小元素成为已排序部分的一部分。
忽略已经排序的部分，继续从剩下的未排序部分中重复上述步骤，直到整个列表排序完成。选择排序的时间复杂度为O(n2)，其中 n 是列表中元素的数量。
这个算法在时间复杂度上和冒泡排序一样，但通常进行的交换次数更少。
因此，虽然它仍然不是最优的排序算法，但在某些特定情况下比冒泡排序更有效。
"""def select_sort_simple(li: list) -> list:li_new = []for i in range(len(li)):min_val = min(li)li_new.append(min_val)li.remove(min_val)return li_newdef select_sort(li: list):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 = jli[i], li[min_loc] = li[min_loc], li[i]print(li)li = [3, 2, 4, 1, 5, 7, 9, 6, 8]
print(li)
select_sort(li)