python算法(没完结)

python算法(没完结)

三月 03, 2026

排序

冒泡/选择

我的笔记里暂时不写这俩

插入

第一个元素看作已经排序好的了，然后从前往后遍历
可以想象成扑克牌，我们拿出来一张往前比较，到他的位置插进去
这里i代表我们的扑克牌
j代表正在进行比较的牌
但是这里就有一个问题，我们假设第一个元素是排好的了，可是如果第一个元素没有排好怎么办
所以要在i对应的循环内再添加俩变量代表值和循环结束后插入的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
n = int(input())
a = list(map(int , sys.stdin.readline().split()))
for i in range(1, n):
    value = a[i]
    insert_idx = 0
    for j in range(i - 1 , -1 , -1):
        if a[j] > value:
            a[j + 1] = a[j]
        else:
            insert_idx = j + 1
            break
    a[insert_idx] = value
print(' '.join(map(str , a)))

快速排序

首先找一个基准值(一般是left)
把列表分成3部分 小于基准，大于基准，等于基准
然后左右再执行该策略 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
def huafen(a,left,right):
    idx = left + 1
    for i in range (left+1,right+1):
        if a[i] < a[left]:
            a[i],a[idx] = a[idx],a[i]
            idx += 1
    a[idx-1],a[left] = a[left],a[idx-1]
    return idx - 1
def qs(a,left,right):
    if left < right:
        mid=huafen(a,left,right)
        #a[left:mid],a[mid],a[mid:right]
        qs(a,left,mid-1)
        #不要拍mid
        qs(a,mid+1,right)



n = int(input())
a = list(map(int, sys.stdin.readline().split()))
qs(a,0,n-1)
print(' '.join(map(str,a)))

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
def merge(a,b):
    result = []
    while len(a)!=0 and len(b)!=0:
        if a[0] < b[0]:
            result.append(a.pop(0))
        else:
            result.append(b.pop(0))
    result.extend(a)
    result.extend(b)
    return result
def merge_sort(a):
    if len(a) < 2:
        return a
    mid = len(a)//2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left,right)
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
a = merge_sort(a)
print(' '.join(map(str, a)))


桶排序

初始化k个桶
遍历数据到桶中
桶单独排序
拼接桶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
def tongsort(a,bucketcount):
    '''
    a是输入的数据
    bucketcount是桶的个数
    '''
    #最大值最小数
    min_a,max_a = min(a),max(a)
    #桶大小
    bucketsize = (max_a - min_a + 1) // bucketcount
    #结果
    res = [[] for _ in range(bucketcount + 1)]#这个是一个列表作为元素的列表
    #给桶里输入数据
    for x in a:
        idx = (x - min_a) // bucketsize
        #这个idx就是我输入的数据应该在什么位置
        #当前的x和min做比较，然后做出的比较和每个桶的范围(大小)相除得来
        res[idx].append(x)
    #开始给每个桶里的数据排序
    ans = []
    for res_x in res:
        res_x.sort()
        ans += res_x
    return ans
n = int(input())
a = list(map(int,sys.stdin.readline().split()))
a = tongsort(a,min(10000,n))
print(' '.join(map(str,a)))

基本算法

复杂度

一般我们关注的是最坏的时间复杂度 O(f(n))
如果同时存在多项，只考虑指数级的最高项
O(n^2+n)==O(n^2)
然后也删除指数级的常数
比如
O(n*n/2-n+1)==O(n*n)

枚举

方法

- 确定解空间(一维、二维)
- 确定空间的边界(每个变量的最小值、最大值、步长)
- 估算时间复杂度
- 如果上一步无法通过则减小枚举空间、变换枚举顺序重新迭代

典型

百钱买百鸡

递归

理解:
把一个大的问题转化为一个规模更小但是相似的问题
比如一个n的问题，那我只需要知道n-1的问题，n-1就是n-2的问题，一直到一个最小的深度也就是出口。
典型：
递归求阶乘

1
2
3
4
5
6
7
def fd(a):
    if a < 2:
        return 1;
    return a * fd(a-1)

n = int(input())
print(fd(n))
典例:
  汉诺塔
  这个要拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import os
import sys

def move(n,a,b,c):
    #如果没有柱子了就停下
    if n == 0:
        return
    #反复执行如下操作
    #从A柱子挪到B柱子，通过柱子C
    move(n-1,a,c,b)
    #挪完了看一下结果
    print(f"{a}->{c}")
    #从B柱子挪到C柱子，通过柱子A
    move(n-1,b,a,c)
move(3,'A','B','C')

进制转换

python内部就有对应的函数
bin()转二进制
oct()转八进制
hex()转十六进制

前缀和

对于一个长度为n的列表a，前缀和为sum[i]=a[0]+a[1]+....
比如a=[1,3,4,2,5],sum=[1,4,8,10,15]
前缀和的性质:
  sum[i] = sum[i - 1] + a[i]
  a[l] + ... a[r] = sum[r] - sum[l-1]
主要作用是快速求l-r之间的和