首页 > 编程语言 >Python基础算法笔记

Python基础算法笔记

时间:2024-08-04 22:41:26浏览次数:14  
标签:tmp Python range 笔记 li 算法 heap 排序 def

整理自B站视频 https://www.bilibili.com/video/BV1uA411N7c5

递归

1. 汉诺塔问题

# n个圆盘,从a经过b移动到c
def hanoi(n, a, b, c):
    if n > 0:
        # 将n-1个圆盘从a经过c移动到b
        hanoi(n - 1, a, c, b)
        # 将最底层的圆盘从a移动到c
        print("moving from %s to %s" % (a, c))
        # 将n-1个圆盘从b经过a移动到c
        hanoi(n - 1, b, a, c)


hanoi(3, 'A', 'B', 'C')

查找

1. 顺序查找

def linear_search(li, val):
    for ind, v in enumerate(li):
        if v == val:
            return ind
    else:
        return None

2. 二分查找

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

排序

1.冒泡排序

通过反复比较相邻元素并交换顺序不正确的元素,将最大或最小的元素逐渐"冒泡"到列表的一端。

def bubble_sort(li):
    for i in range(len(li) - 1):
        # exchange = False
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
        #         exchange = True
        # if not exchange:
        #     return

# 测试排序
import random
li = list(range(10))
random.shuffle(li)
print(li)
bubble_sort(li)
print(li)

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$
排序稳定性: 稳定

2.选择排序

通过反复寻找未排序部分中的最小或最大元素并将其放到已排序部分的末尾,逐步完成整个排序。

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

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$
排序稳定性: 不稳定

3.插入排序

通过逐步将每个元素插入到已排序部分的正确位置,从而构建最终的有序列表。

def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and li[j] > tmp:
            li[j + 1] = li[j]
            j -= 1
        li[j + 1] = tmp

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$
排序稳定性: 稳定

4.快速排序

通过选择一个基准元素并将列表分成比基准小和大的两部分,然后递归地排序每一部分,最终得到有序列表。

def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left


def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid - 1)
        quick_sort(li, mid + 1, right)

时间复杂度: $O(nlogn)$
空间复杂度: $O(logn)$
排序稳定性: 不稳定

5.堆排序

通过将列表构建成一个大根堆或小根堆,逐步将堆顶的最大或最小元素移到列表末尾,然后调整堆来继续排序。

# 大根堆
def sift(li, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个节点位置
    :return:
    """
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] > li[j]:
            j = j + 1
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp
            break
    else:
        li[i] = tmp


def heap_sort(li):
    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        sift(li, i, n - 1)
    for i in range(n - 1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i - 1)

时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$
排序稳定性: 不稳定

使用python内置heapq

import heapq
import random

li = list(range(10))
random.shuffle(li)
print(li)

heapq.heapify(li)  # 建堆
n = len(li)
for i in range(n):
    print(heapq.heappop(li), end=",")

topk问题

# sift函数调整成小根堆
def sift(li, low, high):
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个节点位置
    :return:
    """
    i = low
    j = 2 * i + 1
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] < li[j]:
            j = j + 1
        if li[j] < tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp
            break
    else:
        li[i] = tmp


def topk(li, k):
    heap = li[0:k]
    # 1.建堆
    for i in range((k - 2) // 2, -1, -1):
        sift(heap, i, k - 1)
    # 2.遍历
    for i in range(k, len(li) - 1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k - 1)
    # 3.出数
    for i in range(k - 1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i - 1)
    return heap

使用内置heapq解决topk问题

import heapq
import random


def topk(li, k):
    heap = li[:k]
    heapq.heapify(heap)
    for i in li[k:]:
        if i > heap[0]:
            heapq.heapreplace(heap, i)
    topk_li = []
    for i in range(k):
        topk_li.append(heapq.heappop(heap))
    return topk_li[::-1]


li = list(range(100))
random.shuffle(li)
print(topk(li, 10))

再进一步

import heapq
import random


def topk(li, k):
    return heapq.nlargest(k, li)


li = list(range(100))
random.shuffle(li)
print(topk(li, 10))

6.归并排序

通过将列表递归地分成更小的部分,分别排序这些部分,然后将它们合并成一个有序的列表。

import random


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

    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high + 1] = ltmp


def merge_sort(li, low, high):
    if low < high:
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        merge(li, low, mid, high)


li = list(range(100))
random.shuffle(li)
print(li)
merge_sort(li, 0, len(li) - 1)
print(li)

时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$
排序稳定性: 稳定

7.希尔排序

希尔排序是一种改进的插入排序算法,通过比较和交换间隔较大的元素逐步减少间隔,最终使列表逐渐有序。

def insert_sort_gap(li, gap):
    for i in range(gap, len(li)):
        tmp = li[i]
        j = i - gap
        while j >= 0 and li[j] > tmp:
            li[j + gap] = li[j]
            j -= gap
        li[j + gap] = tmp


def shell_sort(li):
    n = len(li) // 2
    while n >= 1:
        insert_sort_gap(li, n)
        n //= 2

8.计数排序

计数排序是一种非比较排序算法,通过计数每个元素出现的次数,然后按照计数结果将元素依次放入最终排序列表中。

def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count + 1)]
    for val in li:
        count[val] += 1
    li.clear()
    for ind, val in enumerate(count):
        for _ in range(val):
            li.append(ind)

9.桶排序

桶排序是一种分配排序算法,通过将元素分到不同的桶中,然后分别对每个桶进行排序,最后将桶中的元素合并以得到最终的有序列表。

def bucket_sort(li, n=100, max_num=10000):
    # 创建桶
    buckets = [[] for _ in range(n)]
    for var in li:
        i = min(var // (max_num // n), n - 1)
        buckets[i].append(var)
        for j in range(len(buckets[i]) - 1, 0, -1):
            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_li = []
    for buc in buckets:
        sorted_li.extend(buc)
    return sorted_li

10.基数排序

基数排序是一种非比较排序算法,通过逐位(从最低位到最高位)对数字进行排序,依次处理每一位,最终得到有序列表。

def radix_sort(li):
    max_num = max(li)
    it = 0
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            digit = (var // 10 ** it) % 10
            buckets[digit].append(var)
        li.clear()
        for buc in buckets:
            li.extend(buc)
        it += 1

标签:tmp,Python,range,笔记,li,算法,heap,排序,def
From: https://www.cnblogs.com/rustling/p/18342350

相关文章

  • 24412-Python链接LDAP(Kerbores)认证的Impala
    24412-Python链接LDAP(Kerbores)认证的Impala必须安装pyImpala才行pipinstallimpylaPython3.x链接LDAP(Kerbores)认证的Impala代码fromimpala.dbapiimportconnectimpala_host="172.10.194.101"impala_port="25004"impala_user='huabingood_test&......
  • 动态规划,蒙特卡洛,TD,Qlearing,Sars,DQN,REINFORCE算法对比
    动态规划(DynamicProgramming,DP)通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划的步骤识别子问题:定义问题的递归解法,识别状态和选择。确定DP数组:确定存储子问题解的数据结构,通常是数组或矩阵。确定状态转移方程:找出状态之间的关系,即状态转移方程。......
  • 优化蒙特卡洛算法笔记1
    fromkaiwu_agent.utils.common_funcimportcreate_cls,attachedSampleData=create_cls("SampleData",state=None,action=None,reward=None)ObsData=create_cls("ObsData",feature=None)ActData=create_cls("ActData",ac......
  • Python_DAG-有向无环图-igraph
    DAG-有向无环图-igraph安装pipinstallpython-igraphpipinstallpycairopiplist发现Python安装的有igraph包有两个:igraph、python-igraph有向图 有向图(Digraph)是图论中的一种图结构,其中的边(弧)具有方向性,表明从一个节点(顶点)到另一个节点的单向关系。与无向图不同,无向......
  • 【Python系列】深入理解 Python 中的 `nonlocal` 关键字
    ......
  • 学习笔记第十七天
    1.Shell基本语法    1.注释:以#符号开始,直到行末,用于解释代码或暂时禁用某行代码。    2.命令:如echo、ls等,用于执行系统命令或调用外部程序。    3.控制结构:包括if语句、for循环、while循环等,用于控制脚本的流程。2.创建和执行脚本    1.......
  • KMP算法
     ......
  • KMP算法
    写在前面喜报:听了四遍都没学懂的KMP算法,终于在gyy大佬的耐心讲解下搞懂了,大佬orz!!!正文kmp算法本质上就是对模式串(要匹配的子串两个串中短的那个)中很多重复的前缀和后缀索引起来,使得在一个地方失配了也不要紧,不用重新来的算法(看不懂不要紧)下面我们就来详细介绍一下kmp的几个......
  • 《802.11无线网络权威指南-无线网络导论》-- 读书笔记1
    专业术语发射塔:celltower,指信号发射塔基站,接入点:accesspoint无线数据网络:wirelessdatanetwork基站:basestationauthorization:授权,认证serviceprovider:服务供应商hotspot:热点WAN:广域网络infraredlight:红外线频带:frequencyband带宽:bandwidth,即可供使用的频率......
  • KMP学习笔记
    KMP一种字符串单模匹配算法。原理当模式串\(s\)与文本串\(t\)进行匹配时,容易想到的一种朴素做法就是将模式串的第一位与文本串的每一位进行试配。但是这样效率过低,容易被数据卡成\(O(n^2)\)。KMP单模匹配算法引入了一个失配数组border。定义一个字符串的border为一......