数据结构与算法

C++数据结构与算法

my::数据结构与算法

指针的引用

可视化数据结构与算法(usfca.edu)

〇、绪论

1 数据结构

术语：

数据：信息的载体。

数据元素：数据的基本单位，由若干个数据项组成。

数据对象：同性质元素集合。

数据类型：原子类型，结构类型，抽象数据类型（类）。

数据结构三要素：

逻辑结构：线性结构，非线性结构。

存储结构：顺序存储，链式存储，索引存储，散列存储。

2 算法

算法评估：

性质：有穷性，确定性，可行性，输入，输出。

好算法：正确性，可读性，健壮性，高效率与低储存量。

时间复杂度：T( n ) = O( f(n) )

时间复杂度数学定义：若 T(n) 和 f(n) 是定义再正整数集合上的两个函数，则存在正常数 C 和 n0，使得当 n >= n0 时，都满足 0 <= T(n) <= Cf(n)

时间复杂度比较：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n**2) < O(n**3) < O(2**n) < O(n!) < O(n**n)

空间复杂度：S( n ) = O( g( n ) )，即辅助空间。

一、线性表

1 线性表

线性存储的一种数据结构。

// 定义
// 静态
struct {elem[],length};
// 动态
struct {*data,length};

// 函数
// 初始化，O(1)
void InitList(SqList& L);
// 返回线性表长，O(1)
int Length(SqList L);
// 按值查找，O(n)
int LocateElem(SqList L, ElemType e);
// 按位查找，注意超界，O(1)
int GetElem(SqList L, int i);
// 插入，判断i，判断空间是否剩余，后续元素后移，O( n )
bool ListInsert(SqList& L,int i,ElemType e);
// 删除，判断i，后续元素前移，O(n)
bool ListDelete(SqList& L,int i,ElemType& e);
// 打印，遍历，O(n)
void PrintList(SqList L);
// 判空，长度，O(1)
bool Empty(SqList L);
// 摧毁，长度置0，O(1)
void DestroyList(SqList& L);

2 链表

线性存储数据，存储的数据地址不连续。

2.1 单链表

// 定义
// 动态
struct {data,*next};

// 函数
// 头插法逆向初始化单链表，先创建头结点，再输入值，O(n)
LinkList List_HeadInsert(LinkList &L);
// 尾插法正向初始化，需要尾指针，其他同逆向，尾指针最后置空，O(n)
LinkList List_TailInsert(LinkList &L);
// 下标查找结点，O(n)
Lode* GetElem(LinkList L,int i);
// 值查找结点，O(n)
Lode* LocateElem(LinkList L,ElemType e);

// 原地插入删除 O(1)，查找结点再插入删除O(n)，求表长 O(n)。
// 删除插入某个结点的前一结点是 O(n)。

2.2 双向链表

// 定义
// 动态
struct {data,*next,*prior};

// 函数
// 便于找到前驱结点，更好地插入和删除。

2.3 循环链表

循环单链表：基本同理，但判空条件不是 *next 指向 null ，而是是否等于头指针。（指向头结点）

循环双链表：基本同理，空表时 next 和 prior 都指向头结点。

2.4 静态链表

// 定义
// 指针是数据下标（游标），其他同理。
struct(){data,next};
// next 是下一元素的数组下标，next == -1 为结束标记

3 一元多项式

用计算机表示一元多项式。

typedef struct LNode{
    float coef; // 系数
    int expn; // 指数
    struct LNode* next; // 链表下一项
}pnode, *polynomial;

二、栈、队列和数组

1 栈

先进后出的线性表。

特性：

卡特兰数：n 个不同元素进栈，出栈的可能情况是 $\frac{1}NaN C{n \choose k}$

栈的应用：

my::文本编辑器代码

my::迷宫算法代码

表达式求值（未实现）

1.1 顺序栈

// 定义
// 静态
struct {data[],*next};

// 函数
// 初始化栈，O(1)
void InitStack(SqStack &S);
// 判空，top == -1，O(1)
bool StackEmpty(SqStack S);
// 入栈，栈满 top == MaxSize - 1，O(1)
bool Push(SqStack &S,ElemType x);
// 出栈，O(1)
bool Pop(SqStack &S , ElemType &x);
// 读栈顶元素，O(1)
bool GetTop(SqStack S , ElemType &x);

1.2 其他栈

// 共享栈
// 同空间不同栈底。
(top0 == -1) && (top1 == MaxSize) // 为空。
(top1 - top0) == 1 // 为栈满

// 链栈
// 动态
struct {data,*next};

2 队列

先进先出的线性表。

顺序队列：

struct { data[] , front , rear };

栈空：front = rear = 0

rear == MaxSize 不能判断队满

循环队列：

初始：front = rear = 0

front+1：front = (front + 1)%MaxSize

rear+1：rear = (rear + 1)%MaxSize

长度：(rear+MaxSize-front)%MaxSize

判断栈满：

牺牲一个单元

满：(rear + 1)%MaxSize == front

空：front == rear

长度：(rear+MaxSize-front)%MaxSize

增设表示元素个数的成员，size

设置 tag 判断队空

tag = 0，因删除 front == rear，队空

tag = 1，因插入front == rear，队满

链式队列：

结点：struct node {data,*next};

队列：struct queue{*front,*rear};

front == NULL && rear == NULL 队列为空

双端队列：

两端入两端出。

输出受限：两端入一端出。

输入受限：一端入两端出。

// 所有队列操作

// 初始化，O(1)
void InitQueue(SqQueue &Q);
// 判空，O(1)
bool isEmpty(SqQueue Q);
// 入队，判满，O(1)
bool EnQueue(SqQueue &Q,ElemType x);
// 出队，判空，O(1)
bool DeQueue(SqQueue &Q,ElemType &x);
// 获得队头元素，O(1)
bool GetHead(SqQueue Q,ElemType &x);

3 数组

维度和维界不变的线性表。

行存储： LOC(a[i,j]) = LOC(a[0,0]) + [i*(col_len+ 1)+j] * size

列存储： LOC(a[i,j]) = LOC(a[0,0]) + [j*(row_len+1)+i] * size

不定参数

4 特殊矩阵

压缩矩阵：多同值元素仅分配一个存储空间，零元素不分配空间。

特殊矩阵：有许多相同元素或零，且分布有一定规律。

矩阵分区：下三角区，主对角线，上三角区。

行优先：先存完该行的每一列。

列优先：先存完该列的每一行。

对称矩阵：

定义：n 阶矩阵任一元素都 a[i,j] = a[j,i]。一般上三角折到下三角。

三角矩阵：

下三角矩阵：上三角区元素均为同一变量（不包括主对角线），则在线性存储时尾部加一个空间存上三角值。

上三角矩阵：同理。

三对角矩阵：

定义：n 阶矩阵任一元素 a[i,j]，当 |i - j| > 1 时有 a[i,j] = 0

通俗：首位两行各两个元素，其他行每行只有三个元素，坐标是j = i-1，j = i，j = i+1

稀疏矩阵：

定义：m n的矩阵中含有t个非零元素，当`t / ( m n) <= 0.5` 时称为稀疏矩阵。

存储方式：数组，十字链表。

三、串

1 串

存字符的线性表。

// 定义
// 静态
struct {ch[],length};
// 动态
struct {*ch,length};

// 函数
// 赋值，串 T 值改为 chars
void StrAssign(String &T,String chars);
// 复制，串 S 复制给 T
void StrCopy(String &T,String S);
// 判空
bool StrEmpty(String S );
// 比较，len(S) - len(T)
bool StrCompare(String S,String T);
// 串长
int StrLength(String S);
// return Sub = S[pos:pos+len]
void SubString( String &Sub,String S,int pos,int len);
// 拼接
void Concat(String &T,String S1,String S2);
// 找 S 中第一次出现的子串 T 的索引
int Index(String S,String T);
// 清空
void ClearString(String &S);
// 销毁
void DestroyString(String &S);

2 KMP算法

class Solution {
public:
    int strStr(string haystack, string needle) {
        int len = haystack.size();
        int subLen = needle.size();
        int lp = 0;
        int rp = 0;
        int res = -1;

        vector<int> next(subLen, 0);

        buildNext(needle, subLen, next);

        while (lp < len && rp < subLen)
        {
            if (haystack[lp] == needle[rp])
            {
                lp++;
                rp++;
            }
            else if (rp > 0)
            {
                rp = next[rp - 1];
            }
            else
            {
                lp++;
            }
        }

        if (rp == subLen)
        {
            res = lp - rp;
        }
        
        return res;
    }

    void buildNext(string needle, int subLen, vector<int>& next)
    {
        int prefix_len = 0;
        int i = 1;

        while(i < subLen)
        {
            if(needle[prefix_len] == needle[i])
            {
                prefix_len++;
                next[i] = prefix_len;
                i++;
            }
            else
            {
                if(prefix_len != 0)
                {
                    prefix_len = next[prefix_len - 1];
                }
                else
                {
                    next[i] = 0;
                    i++;
                }
            }
        }
    }
};

四、树

1 树

分支关系的非线性结构。

任何一个非空树是一个二元组。Tree = ( root , F )：

root：根节点。

F：子树森林。

完美二叉树, 完全二叉树和完满二叉树 - veli - 博客园 (cnblogs.com)

基本概念名称	意义
结点	数据元素 + 若干指向子树的分支
结点的度	分支的个数
树的度	树中所有结点的度的最大值
叶子结点	度等于0的结点
分支结点	度大于0的结点
孩子结点	下一级
双亲结点	上一级
兄弟结点	同级
祖先结点	上级
子孙结点	下级
层次	树的层数
深度	最大层次
森林	多个互不相交的树的集合

2 二叉树

每个结点至多只有两颗子树，且子树有左右之分的树。

二叉树的五种状态：

空

只有跟结点

有根结点和左子树

有根结点和右子树

有跟结点和左右子树

二叉树性质：

在二叉树的第 i 层至多有 2 ^ ( i - 1 )个结点( i >= 1)。

深度为 k 的二叉树上至多有 2 ^ k - 1个结点( k >= 1)。

任何一颗二叉树，他含有n0个叶子结点，n2个度为2的结点，则必然有n0 = n2 + 1。

满二叉树（完美二叉树）：深度为 k 且含有 2 ^ k - 1 个结点的二叉树。

完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1至n 的结点一一对应。（从左到右从上到下编号，不一定是满二叉树）

完全二叉树性质（123如上）：

具有 n 个结点的完全二叉树的深度为 ⌊log2 n⌋+ 1 。（⌊⌋ 向下取整）

⌊2i⌋ 为根节点，i 的左孩子是 2i ，右孩子是 2i + 1。所以若 2i / 2i + 1 > n 则该结点无左孩子/右孩子。

typedef struct BiTNode    //二叉链表
{
        TElemType data;
        struct BiTNode* lchild, * rchild;  //左右孩子
}BiTNode, * BiTree;

typedef struct TriTNode    //三叉链表
{
        TElemType data;
        struct TriTNode* lchild, * rchild;  //左右孩子
        struct TriTNode* parent;  //双亲结点
}TriTNode, * TriTree;

typedef struct BPTNode   //双亲链表
{
        TElemType data;
        int* parent;  //双亲结点
        char LRTag;  //标志自己是左孩子还是右孩子
}BPTNode;
typedef struct BPTree
{
        BPTNode nodes[MAX_TREE_SIZE];
        int num_node;  //结点数目
        int root;  //根节点
}BPTree;

SqBiTree[MAX_TREE_SIZE];    //顺序存储（按编号，常用于完全二叉树）

五、图

六、算法

text::算法进阶

七、案例

1 日期之差

author::日期之差

// 计算从 0001-1-1 起的天数
int countdays(int y, int m, int d)
{
    if (m < 3)    y--, m += 12;
    return 365 * y + (y >> 2) - y / 100 + y / 400 + (153 * m - 457) / 5 + d - 306;
}

Python数据结构与算法

text::Python

text::Python蓝桥杯题集

一、引论

图灵机：

左半全a右半全b判断是否满足要求。

例子：aaaabbbb，从头开始，先擦除头a，再右移到尾，擦除尾b，再左移到a，擦除头a，循环，直到全被擦除返回真，否则返回假。

数据类型的性能：

# O(1)
x = lst[i]
lst[i] = x

# O(1)
lst.append(x)

# O(n + k)(k是被加列表长度)
lst = lst + new_lst

# 外部库数据结构
pip install pythonds3

# 二叉堆
from pythonds3.trees.binary_heap import BinaryHeap

二、栈

1 栈实现

list末端是栈顶，首端是栈底。底不会变，变的是顶的位置。（时间复杂度较低）

class Stack:
	def __init__(self):
        self.__stack = []

    def push(self,item:any)->None:
        self.__stack.append(item)

    def pop(self)->any:
        return self.__stack.pop()

    def peek(self)->any:
        return self.__stack[-1]

    def isEmpty(self)->bool:
        return self.__stack == []

    def size(self)->int:
        return len(self.__stack)

2 表达式求值

三、队列

1 队列实现

# list首端队首，末端队尾
class Queue:
    def __init__(self):
        self.__queue = []

    def enqueue(self,item:any)->None:
        self.__queue.append(item)

    def dequeue(self)->any:
        return self.__queue.pop(0)

    def isEmpty(self)->bool:
        return self.__queue == []

    def size(self)->int:
        return len(self.__queue)
# 其中enqueue为 O(1)，dequeue为O(n)

# list首端队尾，末端队首
class Queue:
    def __init__(self):
        self.__queue = []

    def enqueue(self,item:any)->None:
        self.__queue.insert(0,item)

    def dequeue(self)->any:
        return self.__queue.pop()

    def isEmpty(self)->bool:
        return self.__queue == []

    def size(self)->int:
        return len(self.__queue)
# 其中enqueue为O(n)，dequeue为O(1)

2 双端队列实现

如果端相反，则操作和时间复杂度都相反。

# list首端队首，末端队尾
class Deque:
    def __init__(self):
        self.__deque = []

    def addFront(self,item:any)->None:
        self.__deque.insert(0,item)

    def addRear(self,item:any)->None:
        self.__deque.append(item)

    def removeFront(self)->any:
        return self.__deque.pop(0)

    def removeRear(self)->any:
        return self.__deque.pop()

    def isEmpty(self)->bool:
        return self.__deque == []

    def size(self)->int:
        return len(self.__deque)
# 其中addFront/removeFront为O(n)，addRear/removeRear为O(1)

四、链表

1 普通无序链表

class Node:
    def __init__(self,intidata:any):
        self.__data = intidata
        self.__next = None

    def getData(self)->any:
        return self.__data

    def getNext(self)->any:
        return self.__next

    def setData(self,newdata:any)->None:
        self.__data = newdata

    def setNext(self,newnext:any)->None:
        self.__next = newnext

class HeadNode:
    def __init__(self):
        self.__next = None

    def getNext(self)->Node:
        return self.__next

    def setNext(self,newnext:any)->None:
        self.__next = newnext

    def insert(self,item:any,location:int=1)->None:
        new = Node(item)
        if location == 1:
            if self.getNext() != None:
                new.setNext(self.getNext())
                self.setNext(new)
            else:
                self.setNext(new)
        else:
            n = self.getNext()
            for i in range(1,location - 1):
                n = n.getNext()
            new.setNext(n.getNext())
            n.setNext(new)

    def peek(self)->list:
        res = []
        if self.getNext() != None:
            n = self.getNext()
            while n.getNext() != None:
                res.append(n.getData())
                n = n.getNext()
            res.append(n.getData())
        return res

    def count(self)->int:
        res = 0
        n = self.getNext()
        if n != None:
            while n != None:
                res += 1
                n = n.getNext()
        return res

    def reverse(self,head):
        prev = None
        curr = head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev
    
    def remove(self,location:int)->Node:
        pass

    def search(self,item:any)->int:
        pass

2 有序表

定义：按大小顺序排好的链表。

五、散列

1 哈希表

事先确定了数据的位置，查找的时间为：O(1)

def hash( num )：计算哈希值。（一般是求余）

hash_lst对应余数值，查找时计算余数值后在 hash_lst 中寻找是否有该数值。

完美散列函数：每一个数据项都映射到不同的槽中。

好的散列函数：

冲突少（近似完美）

计算难度低（额外开销小）

充分分散数据项（节约空间）

作为一致性校验的数据“指纹”函数需要具备如下的特性：

压缩性：任意长度的数据，得到的“指纹”长度是固定的。

易计算性：从原数据计算“指纹”很容易。（从指纹计算原数据是不可能的）

抗修改性：对原数据的微小变动，都会引起“指纹”的大改变。

抗冲突性：已知原数据和“指纹”，要找到相同指纹的数据（伪造）是非常困难的。

产生了哈希冲突：如果产生了哈希冲突，那么哈希映射的值们会形成一个链表，当链表过长时（长度>8），此时链表又会转化成红黑树。

案例：md5（128位），SHA-0/SHA-1（160位（20 Bytes）），SHA-256，SHA-224，SHA-512，SHA-384

应用：密码，网盘（先上传散列值，比较服务器中有无该资源，有则存链接，无则上传文件）

# python中自带的加密
import hashlib
m = hashlib.md5()
m.update("password".encode('utf-8')) # 更新m中的字符串
pw = m.hexdigest()
print(pw)
print(hashlib.md5(("Hello World!".encode('utf-8'))).hexdigest())

2 折叠法

将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余。

隔数反转：隔一个数将数字进行反转。（属于一种微调手段，以便更好符合散列特效）

s = "12312311231"
h = [0 for i in range(len(s))]
gap = 2
count = 0
for i in range(0,len(s),gap):
    i = int(s[i:i+gap-1])
    count += i
h[count % len(s)] = s
print(h)

3 平方取中法

先对数进行平方，再取平方数中间两位，最后对散列表大小求余。

4 设计注意

变位词：字母一样，顺序不同。为了防止可以将字符所在位置设为权重相乘。

5 冲突解决

开放定址（open addressing）：在冲突的数据项处重新再逐个向后找一个空槽。该方法叫线性探测（linear probing）：

缺点：有聚集的趋势。

改进：逐个向后找改为跳跃式探测，例如一次+3。（尽量将散列表大小设为素数，防止周期）

改进：不再固定为一个值，而是逐步增加，例：+1 , +3 , +5 , +7 …

数据项链（Chaining）：将槽扩展为数据项集合。（散列 + 排序查找）

6 ADT Map

dict：映射Map。

class HashTable:
    def __init__(self,size:int):
        self.size = size
        self.slots = [None] * self.size # 保存key
        self.data = [None] * self.size # 保存data
    # hash函数
    def hashfunction(self,key:any)->any:
        return key % self.size
    # 再hash函数
    def rehash(self,oldhash:int)->any:
        return (oldhash + 1) % self.size
    # 存key-val
    def put(self,key:any,data:any)->None:
        hashvalue = self.hashfunction(key)
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:
                nextslot = self.rehash(hashvalue)
                while self.slots[nextslot] != None and self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot)
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data
    # key获得data
    def get(self,key:any)->any:
        startslot = self.hashfunction(key)
        data = None
        stop = False
        found = False
        position = startslot
        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position)
                if position == startslot:
                    stop = True
        return data
    # 索引查找
    def __getitem__(self, key):
        return self.get(key)
    # 索引设置
    def __setitem__(self, key, data):
        self.put(key,data)

六、树

1 术语

基本同C语言。

名称	意义
入边	进入该节点的边
出边	离开该节点的边

2 列表嵌套法

# 二叉树
myTree = [root,left,right]
# 多叉树
myTree = [root,first,second,third,...]

class myTree:
    def __init__(self,r:any):
        self.BinaryTree = [r,[],[]]
    # 左子树插入
    def insertLeft(self,root,newBrance):
        t = root.pop(1)
        if len(t) > 1:
            root.insert(1,[newBrance,t,[]])
        else:
            root.insert(1,[newBrance,[],[]])
        return root
    # 右子树插入
    def insertRight(self,root,newBrance):
        t = root.pop(2)
        if len(t) > 1:
            root.insert(2,[newBrance,t,[]])
        else:
            root.insert(2,[newBrance,[],[]])
        return root

3 节点链接法

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
    # 左插入
    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
    # 右插入
    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

4 表达式树

my::表达式树

求表达式值

例：$((5+((3+7)(4-1)))+(45))$

思路：碰到左括号左下降，碰到数字记录后回升，碰到操作数记录后右下降，碰到右括号回升，留一个栈记录父节点。

5 树的遍历

前序遍历（preorder）：NLR。先根再递归前序访问左子树，最后前序访问右子树。

中序遍历（inorder）：LNR。先递归地中序访问左子树，再访问根，最后中序访问右子树。

后序遍历（postorder）：LRN。先递归地后序访问左子树，再后序访问右子树，最后访问根。

class TreeOrder:
	# 前序
    def preorder(self,tree:BinaryTree):
        if tree:
            print(tree.getRootVal())
            self.preorder(tree.getLeftChild())
            self.preorder(tree.getRightChild())
	# 中序
    def inorder(self,tree:BinaryTree):
        if tree:
            self.inorder(tree.getLeftChild())
            print(tree.getRootVal())
            self.inorder(tree.getRightChild())
	# 后序
    def postorder(self,tree:BinaryTree):
        if tree:
            self.postorder(tree.getLeftChild())
            self.postorder(tree.getRightChild())
            print(tree.getRootVal())

    # 另一种表示
    def preorder(self):
        print(self.key)
        if self.leftChild:
            self.leftChild.preoder()
        if self.rightChild:
            self.rightChild.preorder()

6 二叉堆实现优先队列

my::二叉堆

最小 key 排在队首称为最小堆（min heap），反之是最大堆。（max heap）

实现：完全二叉树。

最小堆（小根堆）：任何一个节点 x ，其父节点 p 中的 key 均小于 x 中的 key。

最大堆（大根堆）：任何一个节点 x ，其父节点 p 中的 key 均大于 x 中的 key。

时间： $O(log n)$

heapq：Python中heapq模块浅析_heapq.heappush-CSDN博客

题目：

100258. 最高频率的 ID - 力扣（LeetCode）

class BinaryHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    # 上浮
    def percUp(self, i:int)->None:
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i // 2]:
                self.heapList[i],self.heapList[i // 2] = self.heapList[i // 2],self.heapList[i]
            i //= 2
    # 下沉
    def percDown(self,i:int)->None:
        while i * 2 <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                self.heapList[i],self.heapList[mc] = self.heapList[mc],self.heapList[i]
            i = mc
    # 最小子孩子
    def minChild(self,i:int)->int:
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1
    # 插入后上浮保持有序
    def insert(self,key:any)->None:
        self.heapList.append(key)
        self.currentSize += 1
        self.percUp(self.currentSize)
    # 插入后尾节点替换主根，然后下沉保持有序
    def findMin(self)->any:
        if self.size() > 0:
            return self.heapList[1]
        else:
            return None
    def delMin(self)->any:
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize -= 1
        self.heapList.pop()
        self.percDown(1)
        return retval
    def isEmpty(self)->bool:
        return self.currentSize > 0
    def size(self)->int:
        return self.currentSize
    # 下沉法控制时间是O(n)
    def buildHeap(self,lst:list):
        i = len(lst) // 2
        self.currentSize = len(lst)
        self.heapList = [0] + lst[:]
        print(len(self.heapList),i)
        while i > 0:
            print(self.heapList,i)
            self.percDown(i)
            i -= 1
        print(self.heapList,i)

7 二叉查找树

实现：有序表数据结构 + 二分搜索或散列表数据结构 + 散列及冲突解决

性质：比父节点小的 key 都出现在左子树，比父节点大的 key 都出现在右子树。

普通二叉查找树最坏：O( log n )，最好：O( n )（单链表），插入时受数据顺序影响，最终会形成不同的二叉查找树。

my::二叉查找树

8 AVL树

平衡二叉查找树。

平衡因子：高度差，大于0左重，小于0右重，若每个节点平衡因子都在 [-1,0,1] 之中则成为平衡树。

时间：O( log n )（类似斐波那契数列）

插入：按照二叉查找树的规则，插入到指定位置，当高度差大于1时，进行旋转。

旋转规则（高度差大于1时）：

LL：爷父子，都是左边。此时爷爷变成父亲的右结点（右旋），父亲变成两者父结点。

RR：爷父子，都是右边。此时爷爷变成父亲的左结点（左旋），父亲变成两者父结点。

LR：父在爷的左边，子在父右边。此时父亲先变成孩子的左结点，然后爷爷变成孩子右节点（先左旋再右旋），孩子变成两者父结点。

RL：父在爷的右边，子在父左边。此时父亲先变成孩子的右结点，然后爷爷变成孩子左节点（先右旋再左旋），孩子变成两者父结点。

删除：

删除叶节点：直接删除。

删除的节点只有左子树或右子树：直接删除后让左 / 右子树代替即可。

删除的节点左右子树都有：找到直接前驱或后继（下一个存在于AVL树中比他小或大的数），直接替换，然后删除直接前驱或后继，删除后按照删除规则继续判定。

9 B树

B树：多路平衡查找树。

m阶B树：多叉查找树。树中每个结点至多有m个孩子结点（即至多有m-1个关键字）

比如一个5阶B树，一个节点有：[20, 30, 62, 89]这样的四个值，那么他会有五个子节点，分别是：<20, >20 and <30, >30 and <62, >62 and <89, >89

B树结构如下：[n,p0,k1,p1,k2, … , kn,pn]

n：结点的关键字个数

p：指针，指向孩子结点

k：关键字，通过关键字来判断孩子的位置。

演示：B-Tree Visualization (usfca.edu)

构建B树：当前结点个数不满足阶树时，直接插入到指定位置。当达到阶树后，比如5阶B树，某个结点原来就有4个值，再插入1个，此时中间值就会向上分裂。比如：[600, 800, 1000, 1200]，插入1400后，此时会变成根结点是[1000]，左边指向[600, 800]，右边指向[1000, 1200]。依次类推，每次当达到了阶数就会向上分裂。如果是偶数比如4阶就是左边的数为中间值。比如[600, 800, 1000]，插入1200后，变成根结点是[800]，左边是[600]，右边是[800, 1000]

使用场景：B树通常用于数据库和文件系统中，用于实现索引数据结构，可以提高数据库查询的效率，减少磁盘IO次数。

10 B+树

同理于B数，但是B+树数据是全部存在叶子处，节点上只存是数据指针，同时根部会形成链表，从左到右依次连接。

和B数的区别：

所有数据都会出现在叶子节点。

叶子节点会形成一个单向链表。

演示：B+ Tree Visualization (usfca.edu)

构建B树：插入规则同理，只不过在裂变时，会把中间数据值放入叶子节点，同时构建一个链表。

使用场景：B+树也被广泛应用于数据库系统中，用于实现索引结构、范围查询和多级索引，B+树相比B树更适合用于磁盘存储，因为B+树的内部节点只存储键值，并通过指针链接叶子节点。

11 红黑树

自身性质：

二叉搜索树。（左根右）

根和叶子都是黑色。叶子结点是NULL。（根叶黑）

所有的红色结点左右孩子都是黑色的，也就是不存在两个连续的黑色结点。（不红红）

任一结点到叶结点所有途径的黑色结点的数量相同。（黑路同）

特点：

最长路径不超过最短路径的两倍，也就是任一结点左右子树的高度差不超过两倍。相比起AVL树（高度差不超过1），AVL树查询更高效，而红黑树插入和删除更高效。

插入：

插入按照AVL树的规则，插入的节点默认是红色。因为这样只可能违反根叶黑或不红红，相比插入黑色更容易调整。

若性质被破坏，则需要调整，调整规则如下：

插入的是根结点：直接变黑

插入的结点的叔叔是红色：叔父爷变色，同时爷爷变成插入结点继续做判定。

插入的结点的叔叔是黑色：按AVL树旋转规则（LL，RR，LR，RL）旋转后对旋转的两个点变色。

删除：

删除的节点只有左孩子或右孩子：直接删除后让左 / 右子树代替后变黑即可。

没有孩子（不包括空）：

红节点：直接删除。

黑节点：

author::红黑树 - 删除_哔哩哔哩_bilibili

使用场景：红黑树也被广泛用于实现Map和Set等数据结构（C++中的STL），以及在操作系统中用于实现进程调度、文件系统等，其中最著名的例子是Linux内核中红黑树的应用。

12 多路归并树

13 败者树

七、图（Graph）

1 术语

若有向图中不存在任何圈，则称作 “ 有向无圈图 directed acyclic graph：DAG “（树是一种DAG，该问题更简单）

名称	意义
顶点Vertex（节点Node）	图的基本组成部分，顶点具有名称标识Key，也可以携带数据项payload
边Edge（弧Arc）	边连接两个顶点，可以有向或者无向
权重Weight	从一个顶点到另一个顶点的代价
路径Path	由边依次连接起来的顶点序列。无权路径的长度为边的数量，带权是权重和
圈Cycle	首尾顶点相同的路径
V	顶点集合
E	边集合
e=( v , w )	E中每条边 e=( v , w )，v 和 w 都是V中顶点
子图	V 和 E 的子集

2 邻接矩阵

优点：简单，容易得到顶点如何连接。

缺点：边数少会变成稀疏矩阵。

3 邻接表

my::邻接表

维护一个包含所有顶点的主列表(master list)，主列表中的每个顶点再关联一个与自身有边连接的所有顶点的列表。

class Vertex:
	def __init__(self, key: any):
        self.id = key
        self.connectedTo = {}
    def addNeighbor(self, nbr:object, weight=0) -> None:
        self.connectedTo[nbr] = weight
    def __str__(self)->any:
        return '[{0}]'.format(str(self.id)) + '<->' + str([x.id for x in self.connectedTo])
    def getConnections(self)->any:
        return self.connectedTo.keys()
    def getId(self)->any:
        return self.id
    def getWeight(self,nbr:any)->any:
        return self.connectedTo[nbr]
    
class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0
    def addVertex(self,key:any)->Vertex:
        self.numVertices += 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex
    def getVertex(self,vKey:any)->any:
        if vKey in self.vertList:
            return self.vertList[vKey]
        else:
            return None
    def __contains__(self, vKey:any)->bool:
        return vKey in self.vertList
    def addEdge(self,fromVert:any,toVert:any,weight:any)->None:
        if fromVert not in self.vertList:
            newVertex = self.addVertex(fromVert)
        if toVert not in self.vertList:
            newVertex = self.addVertex(toVert)
        self.vertList[fromVert].addNeighbor(self.vertList[toVert],weight)
    def Vertices(self)->list:
        return list(self.vertList.keys())
    def __iter__(self)->iter:
        return iter(self.vertList.values())

4 骑士周游问题

哈密顿通路(回路)与哈密顿图 (Hamilton图) 通过图G的每个结点一次，且仅一次的通路(回路)，就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图。

利用深度优先：O（k ** N）（N是棋盘格数）

改进：启发式规则：预先知道下一步的格子中的选择有多少种，优先选择下一个格子的选择少的那个格子。

5 拓扑排序

处理一个DAG，输出顶点的线性序列。广泛应用于依赖事件的排期上。（有先后顺序的多个事件）。

利用 dfs_visit 从某点出发遍历后续事件，得到事件一个列表。

6 并查集

并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的Kruskal算法和求最近公共祖先（LCA）等。

结构：

init：初始化，让每个结点的父亲都指向自己。

find：递归寻找指向自己的结点，该结点则为传入结点的最终父亲。

union：修改结点指向，合并结点。

find路径压缩：将链表转化成树，每个结点直接指向最终的父亲，不需要再一个个遍历。

例题：

2316. 统计无向图中无法互相到达点对数

# 初始化init（指向祖先，也就是自己）
fa = [0 for i in range(n + 1)]
def init(n:int)->None:
    for i in range(1,n + 1):
        fa[i] = i

# 查询find（递归找祖先）
find(i:int)->int:
    if fa[i] == i:
        return i
    else:
        return find(fa[i])

# 合并union（修改祖先进行合并）
def union(i:int,j:int)->None:
    i_fa = find(i)
    j_fa = find(j)
    fa[i_fa] = j_fa # i的祖先指向j的祖先
    
# 查询find优化（路径压缩）
int find(i:int):
    if fa[i] == i:
        return i
   	else:
        fa[i] = find(fa[i]) # 路径压缩
        return fa[i]

7 最小生成树

Prim算法：

Kruskal算法：

# Prim算法（AI生成）
import heapq

def prim(graph):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, 0)]  # 存储边的权重和结束节点的索引
    min_cost = 0

    while min_heap:
        cost, node = heapq.heappop(min_heap)  # 弹出当前最小权重的边
        if visited[node]:
            continue
        visited[node] = True
        min_cost += cost

        for neighbor, weight in graph[node]:  # 遍历与当前节点相邻的节点
            if not visited[neighbor]:
                heapq.heappush(min_heap, (weight, neighbor))

    return min_cost

# Kruskal算法（AI生成）
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return False
        
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        return True


def kruskal(graph):
    edges = []
    n = len(graph)
    
    for i in range(n):
        for j, weight in graph[i]:
            edges.append((weight, i, j))
    
    edges.sort()

    uf = UnionFind(n)
    min_cost = 0
    num_edges = 0

    for weight, u, v in edges:
        if uf.union(u, v):
            min_cost += weight
            num_edges += 1
            if num_edges == n - 1:  # 已经找到了n-1条边，形成了最小生成树
                break
    
    return min_cost

八、python算法

1 最大公约数

欧几里得算法 / 辗转相除法：

# 案例
def gcd(num1,num2):
    while num2 != 0:
        temp = num1
        num1 = num2
        num2 = temp % num2
    return num1

2 递归

模拟树

数量统计递归，可以从上到下传递一个值，也可以从下到上返回一个值。同时维护一个全局变量，每次更新值就更新全局变量。（最大或最小）

递归三要素：

递归算法必须有一个基本结束条件。（最小规模问题的直接解决）

递归算法必须能改变状态向基本结束条件演进。（减小问题规模）

递归算法必须调用自身。（解决减小了规模的相同问题）

master主定理

mast主定理的递归公式：$T(n)=a*T(n/b)+n^d$，其中 a > 1 , b > 1 , d > 0。

$a < b^d $||$log_ba < d$，$T(n) = O(n^d)$

$a = b^d$ || $log_ba = d$，$T(n) = O(n^{log_ba}*log n)$

$a > b^d$ || $log_ba > d$，$T(n)=O(n^{log_ba})$

例题：

104. 二叉树的最大深度

100. 相同的树

101. 对称二叉树

110. 平衡二叉树

199. 二叉树的右视图

# 获得最大递归层数
sys.getrecursionlimit()
# 设置最大递归层数
sys.setrecursionlimit(num)


# 递归求和
def add(nums:list)->int:
    if len(nums) == 1:
        return nums[0]
    else:
        return nums[0] + add(nums[1:])

# 进制转化
def convertNum(num:int,base:int=2)->str:
    dic = {1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9', 10: 'A', 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F'}
    if num < base:
        return dic[num]
    else:
        a,b = divmod(num,base)
        return convertNum(a,base) + str(b)

# 二叉树
import turtle
def tree(t:turtle.Turtle,brance_len:int):
    # 树干太短不画，即递归结束条件
    if brance_len > 5:
        # 画树干
        t.forward(brance_len)
        # 右倾斜20度
        t.right(20)
        # 递归调用，画右边的小数，树干减15
        tree(t,brance_len-15)
        # 向左回40度，即左倾斜20度
        t.left(40)
        # 递归调用，画左边的小数，树干减15
        tree(t,brance_len-15)
        # 向右回20度，即回正
        t.right(20)
        # 海龟回到原位置
        t.backward(brance_len)
if __name__ == '__main__':
    t = turtle.Turtle()
    t.left(90)
    t.penup()
    t.backward(100)
    t.pendown()
    t.pencolor('green')
    t.pensize(2)
    tree(t,75)
    t.hideturtle()
    turtle.done()

# 谢尔宾斯基三角形：
import turtle
#  points表示当前绘制的大三角形的三个顶点，degree表示当前的度，或者级别，必须大于0，才继续绘制，myTurtle是还会作图对象
def sierpinski(points, degree, myTurtle):
    colormap = ['blue', 'red', 'green', 'yellow', 'white', 'orange']
    # 绘制大三角形，从颜色列表中根据degree选择一种颜色
    draw_triangle(points, colormap[degree - 1], myTurtle)
    if degree > 0:
        # 绘制左下角三角形
        sierpinski([points[0], get_middle(points[0], points[1]), get_middle(points[0], points[2])], degree - 1,
                   myTurtle)
        # 绘制上方的三角形
        sierpinski([points[1], get_middle(points[0], points[1]), get_middle(points[1], points[2])], degree - 1,
                   myTurtle)
        # 绘制右下角三角形
        sierpinski([points[2], get_middle(points[2], points[1]), get_middle(points[0], points[2])], degree - 1,
                   myTurtle)
# 绘制一个三角形
def draw_triangle(points, color,myTurtle):
    myTurtle.fillcolor(color)
    myTurtle.up()
    myTurtle.goto(points[0][0],points[0][1])
    myTurtle.down()
    myTurtle.begin_fill()
    # 绘制左边
    myTurtle.goto(points[1][0],points[1][1])
    # 绘制右边
    myTurtle.goto(points[2][0], points[2][1])
    # 绘制底边
    myTurtle.goto(points[0][0], points[0][1])
    myTurtle.end_fill()
# 用于获取两个点的中间点
def get_middle(p1,p2):
    return ((p1[0] + p2[0])/2,(p1[1] + p2[1])/2)
if __name__ == '__main__':
    # 调用代码
    myTurtle = turtle.Turtle()
    window = turtle.Screen()
    # 最大三角形的3个顶点坐标
    points = [[-200,-100],[0,200],[200,-100]]
    # 开始绘制三角形，其实degree为5，直到减小到0为止
    sierpinski(points,5,myTurtle)
    # 将海龟画笔抬起，否则移动海龟画笔会一直绘制直线。
    myTurtle.up()
    # 将海龟画笔移动到200，200的位置，以便原理绘制好的三角形
    myTurtle.setpos(200,200)
    # 显示海龟绘图窗口，绘制完后，单击关闭窗口
    window.exitonclick()

3 回溯

3.1 普通回溯

同理于递归。

思路：当前操作？子问题？下一子问题？

时间复杂度为指数级别 $O(a^n)$，易超时。

例题：

17. 电话号码的字母组合

3.2 子集型回溯

每个元素选或不选，也可以是选列表之间逗号，而非元素。

例题：

78. 子集

131. 分割回文串

3.3 组合型回溯

组合问题。

剪枝：后续不存在满足条件的值将直接返回，不再递归。

例题：

77. 组合

216. 组合总和 III

4 分治

将问题分为若干更小规模的部分。通过解决每个小规模部分问题，最后解决大问题。

4.1 优化问题与贪心算法

贪心：每次都试图解决问题尽量大的一部分。（从顶到底依次最优）

例题：

1798. 你能构造出连续值的最大数目

1605. 给定行和列的和求可行矩阵

# 找零问题：找钱
# 未改进，存在重复计算
def recMC(coinValueList:list,change:int)->int:
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC((coinValueList),change - i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

# 改进，最优解存到列表中
def recDC(coinValueList:list,change:int,knownResults:list)->int:
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1
        return 1
    elif knownResults[change] > 0:
        return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recDC((coinValueList),change - i,knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins
    return minCoins

print(recDC([1,5,10,21,25],63,[0]*64))

4.2 KMP算法

解决了字符串中找子串的问题。

时间复杂度： $O(n+m)$

author::KMP算法代码

def build_next(patt):
    next = [0]
    prefix_len = 0
    i = 1
    while i < len(patt):
        if patt[prefix_len] == patt[i]:
            prefix_len += 1
            next.append(prefix_len)
            i += 1
        else:
            if prefix_len == 0:
                next.append(0)
                i += 1
            else:
                prefix_len = next[prefix_len - 1]
    return next

def kmp_search(string,patt):
    next = build_next(patt)
    
    i = 0
    j = 0
    while i < len(string):
        if string[i] == patt[j]:
            i += 1
            j += 1
        elif j > 0:
            j = next[j - 1]
        else:
            i += 1
        if j == len(patt):
            return i - j
    return -1

4.3 动态规划 [dp]

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。（从底到顶依次最优）

同理于回溯：当前操作？子问题？下一子问题？

例题：

198. 打家劫舍

1027. 最长等差数列

322. 零钱兑换 - 力扣（LeetCode）

# 案例：找零
# 找零问题：找钱
# 未改进，只知道个数
def dpMakeChange(coinValueList:list,change:int,minCoins:list)->int:
    for cents in range(1,change + 1):
        coinCount = cents
        for j in [c for c in coinValueList if c <= cents ]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
        minCoins[cents] = coinCount
    return minCoins[change]
print(dpMakeChange([1,5,10,21,25],63,[0]*64))

# 改进，可以知道找的硬币
def exdpMakeChange(coinValueList:list,change:int,minCoins:list,coinsUsed:list)->int:
    for cents in range(1,change + 1):
        coinCount = cents
        newCoin = 1
        for j in [c for c in coinValueList if c <= cents ]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newCoin = j
        minCoins[cents] = coinCount
        coinsUsed[cents] = newCoin
    return minCoins[change]
def printCoins(coinsUsed,change):
    coin = change
    while coin > 0:
        thisCoin = coinsUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin
amnt = 63
clist = [1,5,10,21,25]
coinsUsed = [0] * (amnt + 1)
coinCount = [0] * (amnt + 1)
print("Making change for",amnt,"requires")
print(exdpMakeChange(clist,amnt,coinCount,coinsUsed),"coins")
print("They are:")
printCoins(coinsUsed,amnt)
print("The used list is as follows:")
print(coinsUsed)

4.4 区间dp

从小区间转移到大区间。

例题：

1000. 合并石头的最低成本 - 力扣（LeetCode）

516. 最长回文子序列

1039. 多边形三角剖分的最低得分

4.5 数位dp

题型：给定一个闭区间 [ L , R ]，求这个区间中满足 “某种条件” 的数的总量。

思路：$Ans[L,R] = Ans[1,R] - Ans[1,L-1]$（求出全部后减去下界）

5 查找

5.1 二分查找

bisect库

求最小中的最大值或者最大值中的最小值，一般可以考虑二分查找。

有序列表，中间开始找，然后依次缩小一半。

注意：明确 lp 和 rp 指向的区间是开还是闭区间，否则容易死循环。

例题：

34. 在排序数组中查找元素的第一个和最后一个位置

162. 寻找峰值

153. 寻找旋转排序数组中的最小值

33. 搜索旋转排序数组

# 直接调库
import bisect
bisect(ls,x) # 同right
bisect_left(ls,x) # 最左边的
bisec_right(ls,x) # 最右边的并且结果idx加一

# 手写
def binary_search(arr, low, high, x):
    arr.sort()

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

5.2 二叉搜索树

对一个节点来说，左子树的值都小于它，右子树的值都大于它。

前序遍历：根左右。

中序遍历：左根右。

后序遍历：左右根。

例题：

98. 验证二叉搜索树

5.3 二叉树的最近公共祖先

获得左右值是否等于目标值，判断值存在以此判断祖先。

例题：

236. 二叉树的最近公共祖先

235. 二叉搜索树的最近公共祖先

5.4 BFS

广度优先搜索。

时间：$O( |V| + |E| )$（节点数 + 边数）

为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加3个属性：

distance：从起始顶点到此顶点路径长度

predecessor：可反向追溯到起点

color：标识了此顶点是尚未发现（白色)、已经发现（灰色)、还是已经完成探索（黑色）

还需要用一个队列 Queue 来对已发现的顶点进行排列：
决定下一个要探索的顶点（队首顶点）

从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列，接下来是个循环迭代过程：

从队首取出一个顶点作为当前顶点。

遍历当前顶点的邻接顶点，如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中。

遍历完成后，将当前顶点设置为黑色(已探索过)，循环回到步骤1的队首取当前顶点。

例题：

102. 二叉树的层序遍历

103. 二叉树的锯齿形层序遍历

513. 找树左下角的值

5.5 DFS

深度优先搜索。

添加属性同理于BFS，过程是从顶点开始一直向下搜索，直到没有路径可以走且结束条件为满足时返回上一层，继续搜索。
还需要用一个栈 Stack 来记录探索过的顶点。（用于返回上一顶点）

有时候深度优先搜索会创建多棵树，称为 “深度优先森林”
时间：$O( |V| + |E| )$（dfs + dfsvisit）

6 排序

可视化排序

6.1 冒泡排序

冒泡排序：每次将最大或最小项置顶，不断交换位置，直到完成遍历。

改进：加一个exchanges = False，如果一趟循环未发生任何排序则保持False表示已经排好了序。

时间：$O(n^2)$

for i in range(len):
    for j in range(i,len):
        if lst[i] > lst[j]:
            lst[i],lst[j] = lst[j],lst[i]

6.2 选择排序

同理冒泡，但是一开始不做交换，只记录位置，到单次循环的最后一次才进行交换。就是每次选一个最大或最小的值放到最前面。

时间：$O(n^2)$

def selection_sort(arr):
    n = len(arr)
    for i in range(n-1):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

6.3 插入排序

维持一个已经排好序的子列表，位置一直在列表前部，然后逐步扩大到这个子列表直到全表，例如抓牌。

时间：$O(n^2)$

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

6.4 希尔排序

因为列表越有序，插入排序比对次数越少，所以希尔排序就是分块的插入排序。间隔一般为n / 2，例：选1,4,7项。

时间：$O(n^{\frac{2}{3}})$

6.5 归并排序

递归算法，将数据表持续分裂成两半，对两半分别进行归并排序。（稳定）

时间分裂：$O(logn)$，归并：$O(n)$，总：$O(nlogn)$，会牺牲空间

def merge_Sort(lst:list)->list:
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left = merge_Sort(lst[:mid])
    right = merge_Sort(lst[mid:])
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else left)
    return merged
print(merge_Sort([93,54,12,74,21,5,78,22,94,34]))

6.6 快速排序

递归算法，依据一个”中值”数据项把数据表分为两半：小于中值的一半和大于中值的一半，然后再分别进行快速排序。（不稳定）

时间总能分裂：$O(logn)$，移动：$O(n)$，总：$O(nlogn)$

若中值偏离中部，时间：$O(n^2)$，因为递归会导致其不如冒泡，

def quickSort(lst:list):
    quickSortHelper(lst,0,len(lst)-1)

def quickSortHelper(lst:list,first:int,last:int)->None:
    if first < last:
        splitpoint = partition(lst,first,last)
        quickSortHelper(lst,first,splitpoint-1)
        quickSortHelper(lst,splitpoint+1,last)
    return None

def partition(lst:list,first:int,last:int)->int:
    pivotvalue = lst[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and lst[leftmark] <= pivotvalue:
            leftmark = leftmark + 1
        while lst[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark - 1
        if rightmark < leftmark:
            done = True
        else:
            lst[leftmark],lst[rightmark] = lst[rightmark],lst[leftmark]
    lst[first],lst[rightmark] = lst[rightmark],lst[first]
    return rightmark

lst = [54,26,93,17,77,31,44,55,20]
quickSort(lst)
print(lst)

6.7 堆排序

二叉堆的排序。

时间：$O(nlogn)$

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

6.8 桶排序

def bucket_sort(arr, num_buckets):
    max_val = max(arr)
    min_val = min(arr)
    bucket_range = (max_val - min_val) / num_buckets

    buckets = [[] for _ in range(num_buckets)]
    for num in arr:
        index = int((num - min_val) // bucket_range)
        if index == num_buckets:
            index -= 1
        buckets[index].append(num)

    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    return sorted_arr

6.9 基数排序

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    return arr

def counting_sort_by_digit(arr, exp):
    count = [0] * 10
    sorted_arr = [0] * len(arr)
    
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1
        
    for i in range(1, 10):
        count[i] += count[i-1]
        
    for i in range(len(arr)-1, -1, -1):
        index = (arr[i] // exp) % 10
        sorted_arr[count[index]-1] = arr[i]
        count[index] -= 1
        
    for i in range(len(arr)):
        arr[i] = sorted_arr[i]

6.10 计数排序

流程：

找出待排序数组中的最大值 maxVal 和最小值 minVal。

创建一个长度为 maxVal - minVal + 1 的计数数组 countArray，用于统计每个元素的出现次数。

遍历待排序数组，统计每个元素出现的次数并存储到 countArray 中。

计算每个元素在排序后的数组中的起始位置（前缀和），修改 countArray 使其表示元素应该放置的位置。

创建一个与待排序数组相同大小的结果数组 resultArray。

遍历待排序数组，根据元素的值和 countArray 中记录的位置信息，将元素放入 resultArray 的正确位置。

返回 resultArray 即为排序后的数组。

时间： $O(n + k)$

空间： $O(n + k)$

def countingSort(arr):
    maxVal = max(arr)
    minVal = min(arr)
    countArray = [0] * (maxVal - minVal + 1)

    for num in arr:
        countArray[num - minVal] += 1

    for i in range(1, len(countArray)):
        countArray[i] += countArray[i - 1]

    resultArray = [0] * len(arr)
    for num in arr:
        index = countArray[num - minVal] - 1
        resultArray[index] = num
        countArray[num - minVal] -= 1

    return resultArray

7 条件

7.1 单调栈

场景：前值小于后值的最小索引位。

例子：

901. 股票价格跨度

1019. 链表中的下一个更大节点

7.2 双指针

同向双指针：

又称为滑动窗口。

场景：找主串中的子串，满足条件时移动右指针，不满足条件时移动左指针。

方法：设置两个索引找到字符串中的两个位置。

同向双指针例题：

209. 长度最小的子数组

713. 乘积小于 K 的子数组

3. 无重复字符的最长子串

同向双指针习题：

481. 神奇字符串

904. 水果成篮

——————————————————————

相向双指针：

场景：有序列表中找两数之和，中间围成的面积。

方法：双指针，但是从头尾开始。

相向双指针例题：

167. 两数之和 II - 输入有序数组

15. 三数之和

11. 盛最多水的容器

42. 接雨水