查找、排序与算法

本文整理查找、排序及相关算法的核心知识。

顺序查找

typedef struct{
Elwmtype *elem;
int Tablelen;
}SSTable;

int Search_Seq(SSTable ST,Elemtype key){
    int i=0;
    for(i=0;i<ST.Tablelen&& ST.elem[i]!=key;i++);
    //查找成功，返回元素下表；查找失败，返回-1.
    return i==ST.Tablelen?-1:i;
    //对比完所有元素之后i=len-1，此刻还会加一得到的是len，数组元素里面不会有下标为len的元素，查找失败返回-1.
}

条件表达式 ? 表达式1 : 表达式2;
//逻辑规则：
//先判断 条件表达式 是否成立（为真）；
//成立 → 执行并返回 表达式1；
//不成立 → 执行并返回 表达式2。

折半查找-有序的顺序表

折半查找代码

typedef struct{
Elwmtype *elem;
int Tablelen;
}SSTable;

int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.Tablelen-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]=key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}

折半查找判定树

判定树结点关键字：左 < 中 < 右，满足二叉排序树的定义

失败结点：n+1 个（等于成功结点的空链域数量）

折半查找的判定树一定是平衡二叉树

折半查找的判定树中，只有最下面一层是不满的

因此，元素个数为n时树高(h=上取整【log_2(n+1)】 )

分块代码-选择

二叉排序树-BST

定义

查找

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

 BTSNode *BST_Search(BSTree T,int key){
     while(T!=NULL&&key!=T->key){
         if(key<T->lchild) 
             T=T->lchild;
         else
             T=T->rchild;
     }
     return T;
 }

//使用递归实现
 BTSNode *BST_Search(BSTree T,int key){
    if(T==NULL)
        return NULL;
     if(key==T->key)
         return T;
     else if(key< T->key)
         return BSTSearch(T->lchild,key);
     else
         return BSTSearch(T->rchild,key);
     
 }

插入

int BST_Insert(BSTree *T, int k) {
    // 情况1：原树为空，新插入的节点为根节点
    if (*T == NULL) {
        // 分配新节点空间
        *T = (BSTree)malloc(sizeof(BSTNode));
        //分配新节点的同时，也会将当前分配空间的地址赋值到*T，也就是当前NULL的位置
        //实现了新节点的链接。
        (*T)->key = k;
        // 新节点一定是叶子，左右孩子初始化为空
        (*T)->lchild = (*T)->rchild = NULL;
        // 插入成功
        return 1;
    }
    // 情况2：树中已存在相同关键字，插入失败（BST不允许重复值）
    else if (k == (*T)->key) {
        return 0;
    }
    // 情况3：k < 当前节点值，递归插入到左子树
    else if (k < (*T)->key) {
        return BST_Insert(&(*T)->lchild, k);
    }
    // 情况4：k > 当前节点值，递归插入到右子树
    else {
        return BST_Insert(&(*T)->rchild, k);
    }
}



int BST_Insert_NonRecur(BSTree *T, int k) {
    // 树为空，直接创建根节点
    if (*T == NULL) {
        *T = (BSTree)malloc(sizeof(BSTNode));
        (*T)->key = k;
        (*T)->lchild = (*T)->rchild = NULL;
        return 1;
    }

    BSTNode *p = *T;
    // 记录父节点，方便最后插入
    BSTNode *parent = NULL;

    // 查找插入位置
    while (p != NULL) {
        parent = p;
        // 找到重复值，插入失败
        if (k == p->key) {
            return 0;
        }
        // 往左子树找
        else if (k < p->key) {
            p = p->lchild;
        }
        // 往右子树找
        else {
            p = p->rchild;
        }
    }

    // 创建新节点
    BSTNode *newNode = (BSTNode)malloc(sizeof(BSTNode));
    newNode->key = k;
    newNode->lchild = newNode->rchild = NULL;

    // 插入到父节点的左/右孩子
    if (k < parent->key) {
        parent->lchild = newNode;
    } else {
        parent->rchild = newNode;
    }
    return 1;
}

删除

二叉排序树删除只分 3 种情况，按复杂度从低到高：

1. 叶子节点（无左、右孩子）：直接删除
2. 只有一个子树（左 / 右）：用子树顶替当前节点
3. 左右子树都有：找 前驱节点（左子树最大值）左子树最右下、后继结点（右子树最小值）右子树最左下 替换，再删前驱。中序遍历的待删除值的左右两个值

//代码是先将替换节点值刷新到原来节点，再释放替换节点源内存。
// 二叉排序树删除节点（递归 + 二级指针，和插入配套）
int BST_Delete(BSTree *T, int key) {
    if (*T == NULL) return 0; // 空树，删除失败

    // 1. 找到要删除的节点
    if (key == (*T)->key) {
        BSTree p = *T; // 暂存待删除节点

        // ========== 情况1：叶子节点（无左右孩子） ==========
        if ((*T)->lchild == NULL && (*T)->rchild == NULL) {
            *T = NULL; // 二级指针直接置空，自动断开父节点链接
        }

        // ========== 情况2：只有右子树 ==========
        else if ((*T)->lchild == NULL) {
            *T = (*T)->rchild; // 右子树顶替当前节点
        }

        // ========== 情况2：只有左子树 ==========
        else if ((*T)->rchild == NULL) {
            *T = (*T)->lchild; // 左子树顶替当前节点
        }

        // ========== 情况3：左右子树都存在（核心） ==========
        else {
            // 找【前驱节点】：左子树的最大值（最右节点）
            BSTree pre = (*T)->lchild;
            while (pre->rchild != NULL) {
                pre = pre->rchild;
            }
            // 用前驱的值替换当前节点的值
            (*T)->key = pre->key;
            // 递归删除前驱节点
            BST_Delete(&(*T)->lchild, pre->key);
            return 1;
        }

        free(p); // 释放节点内存
        return 1;
    }

    // 2. 比当前节点小，递归左子树
    else if (key < (*T)->key) {
        return BST_Delete(&(*T)->lchild, key);
    }

    // 3. 比当前节点大，递归右子树
    else {
        return BST_Delete(&(*T)->rchild, key);
    }
}

构造

查找效率

平衡二叉树-AVL

定义

不平衡二叉树的插入-调整

查找效率

平衡二叉树删除-调整

红黑树-RBT-频繁调整少改变

红黑树基本操作

红黑树的插入

红黑数删除

B树

B树的定义

选择判断

B树的高度

B树的插入

结论：如图

B树的删除

结论一：非终端节点的删除一定可以转化为终端借点的删除

结论二：删除终端节点导致关键字少于标准，向兄弟节点借，后继的后继顶替后继，后继顶替删除；前驱的前驱顶替前驱，前驱顶替删除。

结论三：兄弟不够的时候，合并左兄弟和左子树关键子；合并右兄弟和右子树关键字。双亲合并减少，递归合并直到符合特性。

B+树

散列技术

基本概念

散列表构造

1. 数字选择法
2. 除留余数法–选择接近散列表长度的最大质数
3. 平方取中法
4. 折叠法
5. 基数转换法
6. 随机数法

除留余数法

为什么选择不大于表长m的最大质数？

直接定值法

数字分析法

平法取中法

解决冲突的办法

开放定址法

开放定址法-四种探测方法

​ 当发什冲突的时候，使用某种方法在散列表中形成一个探查序列，沿着这个序列逐个单元查找，直到找到一个空的单元将新的节点放入为止。因此造表开始之前，表应该被置空。

查找、插入、删除

查找过程依次对比目标关键字，初始散列地址+后续寻址，最后如果是空地址就查找失败，关键字对比成功则查找成功。

在探测到空时都返回查找失败吗？

注意在实际探测过成功若是直接删除原有元素，会导致探测链的断开，导致部分元素查找失败。故在实际过程中只能逻辑删除而不是直接物理删除。

在删除元素过程中应当先注意待删除元素，设置flag表示逻辑删除而不是物理删除，这样不会在查找过程中出现断表的情况。

但是会出现大量无效存储，故在插入的时候可以根据flag直接覆盖已删除元素并修改flag值。

实际应用：使用移位寄存器序列代替随机数序列。

注意-平方探测表长、双散列特殊要求

平方探测法会出现不容易探测整个散列空间，但是如果表长是m=4j+3的素数，的话就可以全部探测到；

双散列法，让has2(key)计算得到的值与散列表的长m互相为质数，就可以保证双散列探测到全部元素。

拉链法

类似树的孩子表示法(数组+链表)

冲突的元素依次存入链表当中，数组每个元素都是一个冲突链表的头节点。

散列性能分析

线性探测—-注意查找失败和删除元素后查找

平均查找长度（ASL）

就是查找一个元素时，平均需要比较的次数。

• 成功查找：找的是表里已经存在的元素
• 不成功查找：找的是表里不存在的元素，要找到空位置才知道不存在

装填因子

解释：装填因子 α 是什么？

公式：α=表中元素个数 n/表的总长度 m

它反映了散列表的 “拥挤程度”：α 越大，表越挤，冲突越多，查找越慢；α 越小，表越空，冲突越少，但空间浪费越多

散列表一般会把 α 控制在 0.7 左右（比如 Java 的 HashMap 默认阈值就是 0.75），超过了就会扩容，降低 α 来保证性能。

线性探测会出现堆积问题

PPT相关内容

王道说明情况

总结

排序

插入排序

算法思想：每次都将一个待排序的记录按关键字大小插入到前面已经拍好的子序列当中，直到全部记录插入完成。

void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=0;i<n;i++){
        if(A[i]<A[i-1]){
            temp=A[i];
            for(j=i-1;j>=0&&A[j]>temp;--j){
                A[j+1]=A[j];
            A[j+1]=temp;
            }
        }
    }
}

void InsertSort(int A[],int n){
    int i,j;
    for(i=2;i<=n;i++){//依次将A[2]~A[N]插入
        if(A[i]<A[i-1]){
            A[0]=A[i];//复制哨兵，A[0]不放元素
            for(j=i-1;A[0]<A[j];--j){
                A[j+1]=A[j];//向后挪威，最后都会回到A[0]的位置。
            A[j+1]=A[0];//
            }
        }
    }
}

算法效率：时间：O(n^2)，空间：O(1),稳定

优化-折半查找插入

void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){//依次将A[2]~A[N]插入
        A[0]=A[i];//复制哨兵，A[0]不放元素
        low=1;high=i-1;
        while(low<=high){
            mid=(high+low)/2;
            if(A[mid]>A[0]) high=mid-1;
			else low=mid+1;
        }
		for(j=i-1;j>=high+1;--j){
            A[j+1]=A[j];
        A[high+1]=A[0];
        }
  	}
}

希尔排序

//希尔排序
void ShellSort(int A[],int n){
    int d, i, j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d= n/2; d>=1; d=d/2)        //步长变化
        for(i=d+1; i<=n; ++i)
            if(A[i]<A[i-d]){        //需将A[i]插入有序增量子表
                A[0]=A[i];         //暂存在A[0]
                for(j= i-d; j>0 && A[0]<A[j]; j-=d)
                    A[j+d]=A[j];   //记录后移，查找插入的位置
                A[j+d]=A[0];       //插入
            }//if
}

时间复杂度：平均复杂度：O(N^1.3),最坏O(n^2),不稳定，只能顺序表实现。

冒泡排序-交换排序一种

//交换函数
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//冒泡排序（优化版，带提前终止标记flag）
void BubbleSort(int A[],int n){
    for(int i=0;i<n-1;i++){
        bool flag=false;        //标记本趟是否发生交换
        for(int j=n-1;j>i;j--)  //一趟冒泡，从后往前遍历
            if(A[j-1]>A[j]){   //逆序则交换
                swap(A[j-1],A[j]);
                flag=true;
            }
        if(flag==false)        //本趟无交换，数组已有序，直接退出
            return;
    }
}

最好时间（数组已有序）：(O(n))，仅 1 趟遍历

最坏 / 平均时间：(O(n^2))

空间复杂度：(O(1))，原地排序

稳定性：稳定

快速排序—分治递归*-手写

核心算法思想：

1. 选枢轴：在待排序区间任选一个元素作为枢轴 pivot（常规取区间首元素）。

2. 一趟划分：将区间分割为两部分

   • 左半区间：所有元素 < pivot

   • 右半区间：所有元素 ≥ pivot

     划分完成后，pivot 落到它最终的有序下标位置L[k]

3. 递归分治：对左、右两个子区间重复划分操作，直到子区间长度≤1（天然有序）。

时间复杂度：平均情况：(O(n\log n))，所有内部排序里平均性能最优，最好情况：(O(n\log n))，每次划分左右区间长度均衡最坏情况：(O(n^2))，数组本身有序 / 逆序，每次划分仅分出 1 个元素，递归深度为n

空间复杂度：递归调用栈开销：平均：(O(\log n))；最坏：(O(n)) 稳定性：不稳定排序

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];        //第一个元素作为枢轴
    //用low、high搜索枢轴的最终位置
    while(low<high){
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high];     //比枢轴小的元素移动到左端
        while(low<high&&A[low]<=pivot) ++low;
        A[high]=A[low];     //比枢轴大的元素移动到右端
    }
    A[low]=pivot;            //枢轴元素存放到最终位置
    return low;              //返回存放枢轴的最终位置
}

//快速排序
void QuickSort(int A[],int low,int high){
    if(low<high){               //递归跳出的条件
        int pivotpos=Partition(A, low,high); //划分
        QuickSort(A, low,pivotpos-1);        //划分左子表
        QuickSort(A,pivotpos+1,high);        //划分右子表
    }
}

简单选择排序

将数组划分为有序区（左侧） 和无序区（右侧）：

1. 第 i 轮排序，在 [i, n-1] 无序区间找到最小元素下标 min；
2. 把最小元素 A[min] 和无序区第一个元素 A[i] 交换；
3. 有序区长度 + 1，无序区起点后移一位；重复直到全部有序。

核心特点：每轮只交换 1 次，比较次数固定不变。

间复杂度:最好 / 平均 / 最坏：O(n^2)

空间复杂度:仅用临时变量 i,j,min，原地排序：O(1)

堆排序

大根堆的建立

思路：把所有非终端节点都检查一遍，是否满足大根堆的要求，如果不满足进行调整。

若检查当前节点是否满足根>=左，右，若不满足，将当前结点与更大的一个孩子交换

若元素交换破坏了下一级的堆，采用相同的方法继续向下调整。

//将以 k 为根的子树调整为大根堆
void HeapAdjust(int A[],int k,int len){
    A[0]=A[k];                //A[0]暂存子树的根结点
    for(int i=2*k;i<=len;i*=2){  //沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1])
            i++;               //取key较大的子结点的下标
        if(A[0]>=A[i]) break; //筛选结束
        else{
            A[k]=A[i];        //将A[i]调整到双亲结点上
            k=i;              //修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];                //被筛选结点的值放入最终位置
}

//建立大根堆
void BuildMaxHeap(int A[],int len){
    //从后往前调整所有非终端结点
    for(int i=len/2;i>0;i--)
        HeapAdjust(A,i,len);
}

建堆时间复杂度：(O(n))；单次调整堆 (O(log n))；整体堆排序 (O(nlog n))，关键字对比次数不大于4n

空间复杂度：(O(1))，原地排序

稳定性：不稳定排序

堆的插入和删除

堆的插入（上浮 sift up）：新元素先放到数组末尾（二叉树最后一层最右空位），再不断和父节点比较，不符合堆序就交换，一路向上冒泡，直到满足堆性质。

步骤（以小顶堆举例）

1. 把新元素追加到数组尾部（完全二叉树最后一个位置）；
2. 取当前节点下标 i，父节点下标 parent = (i-1)//2；
3. 如果当前值 < 父值（破坏小顶堆），交换两者，令 i=parent；
4. 循环重复步骤 2、3，直到 i=0（到达根节点）或符合堆序停止。

堆的删除（删除堆顶元素，下沉 sift down）堆默认只删除堆顶（最值），不随意删中间节点（代价高）：用数组最后一个元素覆盖堆顶，删掉数组最后一位；再让新堆顶不断和左右孩子比较，和更小 / 更大的孩子交换，一路向下调整，恢复堆序。

步骤（小顶堆举例）

1. 取出堆顶元素（要删除的最值）；
2. 将数组最后一个元素覆盖到根节点位置；数组长度 - 1，丢弃末尾；
3. 当前下标 i=0，计算左孩子 l=2i+1、右孩子 r=2i+2；
4. 找出左右孩子里更小的那个；
5. 如果当前节点 > 最小孩子，交换两者，i 切换到被交换孩子下标；
6. 循环 3~5，直到没有孩子、或当前节点小于所有孩子。

归并排序*-递归、分治

什么是归并merge

把多个有序数组，或者链表合成一个新的有序数组或者链表。

多路归并：m路归并，每次都会同时对比m个首元素，找到最小的填入队首。

归并排序-分治、递归

int *B=(int *)malloc(n*sizeof(int)); //辅助数组B
//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    //把[low,high]区间全部复制到辅助数组B备份
    for(k=low;k<=high;k++)
        B[k]=A[k];      //将A中区间元素复制到B中
    //双指针合并两个有序子区间
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])
            A[k]=B[i++];    //取左段较小值放回原数组A
        else
            A[k]=B[j++];    //取右段较小值放回原数组A
    }//for
    //处理左半段剩余未复制元素
    while(i<=mid)  
        A[k++]=B[i++];
    //处理右半段剩余未复制元素
    while(j<=high)  
        A[k++]=B[j++];
}
void MergeSort(int A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;       //从中间划分区间
        MergeSort(A,low,mid);       //对左半部分递归归并排序
        MergeSort(A,mid+1,high);    //对右半部分递归归并排序
        Merge(A,low,mid,high);      //合并左右两个有序区间
    }//if
}

归并排序分为分、合两步：

1. 分：每次把区间对半拆分，递归深度是 (\log_2 n)；
2. 合（Merge）：每层递归的合并操作都要遍历全部 n 个元素，每层总代价 (O(n))。

总层数 × 每层代价 = (O(nlog n))

• 最好情况：(T(n)=O(nlog n))
• 最坏情况：(T(n)=O(nlog n))
• 平均情况：(T(n)=O(nlog n))

特点：唯一不受原始数组有序度影响的稳定 (nlog n) 排序，哪怕数组完全逆序，时间效率不变。

基数排序-手算

计数排序

计数排序是非比较排序，不通过元素大小比较完成排序，前提：待排序元素数值范围已知且跨度小。

1. 设待排数组A最大值为max，创建计数数组count[0…max]，初始全 0；
2. 遍历原数组，count[A[i]]++，统计每个数值出现次数；
3. 对count做前缀和：count[i] = count[i] + count[i-1]，表示数值i在有序数组中最后出现的下标；
4. 倒序遍历原数组，根据count[A[i]]把元素放入结果数组，同时count[A[i]]--，保证相等元素相对顺序不变。

适用场景：元素为整数、数值区间远小于元素个数（如学生成绩 0~100）。

// A：待排序数组，n：长度，maxVal：数组中最大值
void CountSort(int A[], int n, int maxVal) {
    int *count = (int*)malloc(sizeof(int)*(maxVal+1));
    int *res = (int*)malloc(sizeof(int)*n);
    // 1. 计数数组初始化清零
    for(int i = 0; i <= maxVal; i++)
        count[i] = 0;
    // 2. 统计每个数字出现次数
    for(int i = 0; i < n; i++)
        count[A[i]]++;
    // 3. 前缀和，确定每个数的右边界下标
    for(int i = 1; i <= maxVal; i++)
        count[i] += count[i-1];
    // 4. 倒序遍历，输出有序数组（保证稳定）
    for(int i = n - 1; i >= 0; i--) {
        res[count[A[i]] - 1] = A[i];
        count[A[i]]--;
    }
    // 5. 结果复制回原数组
    for(int i = 0; i < n; i++)
        A[i] = res[i];
    free(count);
    free(res);
}

设：数组长度n，数值区间范围k（0-maxVal)）

1. 时间复杂度

   • 最好 / 平均 / 最坏：O(n+k)
   • 四段循环分别为(O(k)+O(n)+O(k)+O(n))，线性时间；
   • 若(k≈n)，复杂度接近(O(n))，远快于(O(nlog n))的比较排序。

2. 空间复杂度

   O(n+k)，需要辅助计数数组count、结果数组res；非原地排序。

稳定性

稳定排序

关键原因：倒序遍历原数组，相同数值会按原数组从后到前的顺序填入结果数组，相等元素相对先后不颠倒；

如果正序遍历，会变成不稳定。

外部排序

外存、内存如何交换数据

败者树

置换选择排序

最佳归并树

缩小规模算法-分治、递归、贪心

分治与递归

分治的思想是什么？

分治的核心是分而治之，是一种解决复杂问题的通用思路：

将一个规模大、难以直接求解的问题，分解为若干个规模更小、结构与原问题完全相同的子问题；递归求解这些子问题后，再将子问题的解进行合并，最终得到原问题的解。

整个过程分为三步：分解 → 求解 → 合并。

递归算法是什么？

递归算法指：一个函数 / 过程在定义中直接或间接地调用自身的算法。

它将大规模的原问题，转化为规模更小、性质相同的子问题来求解，必须满足两个核心要素：

1. 递归边界（基准条件）：问题规模缩小到一定程度时，可以直接得到解，不再继续递归，避免无限调用；
2. 递归关系式（递推公式）：描述原问题与子问题之间的转化关系。

递归的优点是代码简洁、逻辑清晰，缺点是可能存在重复计算、栈溢出风险。

递归算法设计

排列问题

排列问题通常指n 个不同元素的全排列问题：给定 n 个互不相同的元素，输出所有可能的排列方案总数 / 所有排列结果。

例如元素 {1,2,3} 的全排列共 6 种：123、132、213、231、312、321。

分治 / 递归求解思路：

1. 固定第 1 个位置的元素：将第 1 个元素，依次和第 1、2、…、n 个元素交换；

2. 递归求解：对剩下的 n-1 个元素，递归求全排列；

3. 回溯恢复：递归返回后，交换回元素位置，保证下一轮交换的正确性。

   边界条件：当子序列只剩 1 个元素时，当前序列就是一个完整排列。

//类似于树的探索，每次都找到m叉树的最小分支。
void Perm(DataType R[], int k, int m){
    if (k > m) {
        // 输出当前排列
        //只有当递归到最后一层的时候才会输出序列
        //也就是排列树的最小分支
        for (i = 0; i <= m; i++)
            output(R[i]);}
    else {
    for (i = k; i <= m; i++) {
        swap(R[k], R[i]);   // 第1步：交换，把R[i]放到第k位
        					//同时此处会分多次，每次递归都会交换下一个位置和当前位置
        					//直到最后交换自己交换不了的时候
        Perm(R, k+1, m);    // 第2步：递归，生成剩余k+1~m位的全排列
        					//递归的核心，只要还有元素没有使用就递归
        swap(R[k], R[i]);   // 第3步：回溯，交换回来，恢复现场
        					//关键，每次递归调用结束都要返回上次递归的状态，保证下一次从不同的选择开始。
   		 }}    
}
    

函数 Perm(R, k, m) 的完整功能就是：

生成数组 R 中，下标从 k 到 m 的这一段连续元素的全排列。

举个对应例子：

数组 R = [a, b, c]，下标 0、1、2，初始调用 Perm(R, 0, 2)，代表生成整个数组的全排列；

递归深入时调用 Perm(R, 1, 2)，代表生成第 1~2 位元素的全排列；

直到 k=3、m=2，k 超过 m，输出完整排列。

整数的划分问题

整数划分问题：给定正整数 n，将 n 拆分为若干个正整数之和（不考虑拆分顺序），求一共有多少种不同的拆分方案。

例如 n=4 时，共有 5 种划分：4、3+1、2+2、2+1+1、1+1+1+1。

递归 / 动态规划定义：

设 f(n, m) 表示将 n 拆分为最大数不超过 m的划分方案数，递推关系如下：

1. 当 n=1 或 m=1：只有 1 种划分（全拆成 1），f(n,m)=1；
2. 当 m > n：最大数不可能超过 n，f(n,m)=f(n,n)；
3. 当 m = n：划分分为「包含 n 本身」和「不包含 n」，f(n,m)=1 + f(n, m-1)；
4. 当 m < n：划分分为「包含 m」和「不包含 m」，f(n,m)=f(n-m, m) + f(n, m-1)。

分治算法设计

分治算法设计思想

分治算法的设计围绕「分解 - 求解 - 合并」三步展开，核心设计原则如下：

1. 分解（Divide）：将原问题拆解为若干个规模更小、相互独立、结构与原问题完全一致的子问题；
2. 求解（Conquer）：若子问题规模足够小、可直接求解，则直接得出答案；否则继续递归分解子问题；
3. 合并（Combine）：将所有子问题的解进行整合，得到原问题的最终解。

适用前提：

• 问题可分解为结构相同的子问题；
• 子问题的解可以合并为原问题的解；
• 子问题之间相互独立，不存在重叠（若有重叠则更适合动态规划）。

二分搜索技术 (二分查找)

二分查找是分治思想的典型应用，是针对有序顺序表的高效查找算法。

核心前提：

查找表必须是有序的顺序存储结构（如有序数组）。

算法步骤：

1. 取当前查找区间的中间位置元素，与待查目标值比较；
2. 若相等：查找成功，返回位置；
3. 若目标值更小：说明目标在左半区间，缩小右边界，继续二分；
4. 若目标值更大：说明目标在右半区间，扩大左边界，继续二分；
5. 当区间左边界超过右边界时，查找失败。

复杂度：

• 时间复杂度：O(logn)（每次区间缩小一半）；
• 空间复杂度：迭代实现为O(1)，递归实现为O(logn)。

堆排序

堆排序是基于大根堆 / 小根堆数据结构实现的选择类排序算法，利用堆的特性高效选取极值。

核心概念：

• 大根堆：每个节点的值都 ≥ 其子节点的值，堆顶为全局最大值；
• 小根堆：每个节点的值都 ≤ 其子节点的值，堆顶为全局最小值。

算法步骤（升序排序，用大根堆）：

1. 建堆：将待排序数组调整为大根堆，此时堆顶为最大值；
2. 交换：将堆顶元素与数组末尾元素交换，最大值进入有序区；
3. 调整堆：将剩余未排序元素重新调整为大根堆，得到新的堆顶最大值；
4. 重复「交换 - 调整堆」，直到所有元素都进入有序区。

复杂度与特性：

• 时间复杂度：建堆O(n)，调整堆O(nlogn)，整体O(nlogn)；
• 空间复杂度：O(1)（原地排序）；
• 不稳定排序，适合数据量大的场景，不受数据有序性影响。

快速排序

快速排序是分治思想最经典的排序应用，也是实际中性能最优的通用排序算法之一。

核心思路：

通过「分区」操作将序列拆分为两部分，递归排序子区间，最终整体有序。

1. 选基准：从序列中选取一个元素作为基准值（pivot）；
2. 分区（Partition）：遍历序列，将小于等于基准的元素放到左边，大于等于基准的放到右边，最终基准元素落到它的最终排序位置上；
3. 递归排序：对基准左右两个子区间，递归执行快速排序。

复杂度与特性：

• 平均时间复杂度：O(nlogn)；
• 最坏时间复杂度：O(n²)（如有序数组选首尾元素为基准，分区极不均匀）；
• 空间复杂度：平均O(logn)（递归栈），最坏O(n)；
• 不稳定排序，原地排序，平均性能优于堆排序、归并排序。

动态规划

动态规划算法的三个基本要素

1. 最优子结构

   原问题的最优解，一定包含了其所有子问题的最优解。这是动态规划的前提，只有满足该性质，才能通过子问题的最优解推导原问题的最优解。

   例：矩阵连乘的最优解拆分后，左右子链也一定是各自的最优连乘次序。

2. 重叠子问题

   用递归方式求解原问题时，会反复计算相同的子问题，而不是每次生成全新的子问题。

   动态规划通过「填表保存子问题的解」，避免了重复计算，大幅提升效率，这是动态规划相比朴素递归的核心优势。

3. 备忘录方法

   也叫记忆化搜索，是动态规划的「自顶向下」实现方式：

   为每个子问题的解建立备忘录，递归求解时先查备忘录：如果子问题已经计算过，直接取出结果；如果没计算过，再递归计算并保存结果。

   它和常规自底向上动态规划的区别是：只计算实际会用到的子问题，适合子问题无需全部计算的场景。

动态规划算法设计四步骤

标准动态规划问题的求解分为 4 个核心步骤：

1. 刻画最优子结构：分析问题的最优解的结构特征，证明「原问题的最优解，包含了其子问题的最优解」，确定状态的含义；
2. 定义最优值的递归关系：写出状态转移方程，用子问题的最优值，推导原问题的最优值；
3. 自底向上计算最优值：从最小的子问题开始，逐步计算更大规模子问题的最优值，保存到表格中，避免重复计算；
4. 构造最优解：根据计算最优值时记录的决策信息，回溯还原出具体的最优方案（如分段方式、路径、选择结果等）。

矩阵连乘问题

矩阵连乘问题是动态规划的经典入门问题：

给定 n 个可连续相乘的矩阵A₁,A₂,…,Aₙ（其中Aᵢ的维度为p[i-1]×p[i]），矩阵乘法满足结合律，不同的加括号计算次序，总乘法运算次数差异极大。

问题目标：找到一种最优的计算次序，使得矩阵连乘的总乘法运算次数最少。

例如A₁(10×100)、A₂(100×5)、A₃(5×50)：

• 按(A₁A₂)A₃计算：总次数10×100×5 + 10×5×50 = 7500；
• 按A₁(A₂A₃)计算：总次数100×5×50 + 10×100×50 = 75000，性能相差 10 倍。

矩阵连乘积的计算次序

矩阵连乘的动态规划解法

图像压缩

最优二叉搜索树

贪心算法

贪心算法是一种每一步都做出当前局部最优选择的算法设计思想：

在问题的每一个决策阶段，都选择当下看起来最优的方案，期望通过一系列局部最优的决策，最终得到问题的全局最优解。

两个核心适用条件：

1. 最优子结构：全局最优解包含子问题的最优解（和动态规划一致）；
2. 贪心选择性质：全局最优解可以通过一系列局部最优的选择逐步构造出来；每一步的选择只依赖当前状态，不依赖未来的选择，也不需要回溯。

特点：

• 算法逻辑简单、运行效率高，通常时间复杂度较低；
• 不是所有问题都能得到全局最优解，必须证明问题满足贪心选择性质后，才能保证结果正确。

贪心和动态规划的差异

对比维度	贪心算法	动态规划
决策方式	每一步做局部最优选择，决策后不回溯，只关注当前状态	综合所有子问题的最优解，通过状态转移推导当前最优，支持回溯构造方案
核心条件	需要满足贪心选择性质+ 最优子结构	只需要满足最优子结构 + 重叠子问题
子问题关系	子问题相互独立，当前选择不影响后续子问题	子问题可存在依赖关系，通过状态转移关联
求解方向	通常自顶向下，逐步决策缩小问题规模	多为自底向上填表，也可自顶向下备忘录
结果保证	不一定得到全局最优，需证明贪心性质	只要状态定义正确，一定能得到全局最优解
时空开销	通常更低，无需保存所有子问题状态	更高，需要存储所有子问题的最优值

典型例子：0-1 背包只能用动态规划求解，不能用贪心；而可分割的部分背包问题，可以用贪心得到最优解。

哈弗曼编码

哈夫曼编码是最优前缀编码，是贪心算法在数据压缩领域的经典应用。

问题背景

给定字符集和每个字符的出现频率，构造一种二进制前缀编码（任意字符的编码都不是其他字符编码的前缀，解码无歧义），使得所有字符的总编码长度（带权路径长度）最小。

贪心构造思路（哈夫曼树）

1. 将每个字符看作一个独立节点，权值为字符的出现频率；
2. 每次从所有节点中，选出权值最小的两个节点，合并为一个新的父节点，父节点的权值等于两个子节点权值之和；
3. 将新节点放回节点集合中，重复步骤 2，直到集合中只剩一个根节点，最终形成的二叉树就是哈夫曼树。

编码规则

从哈夫曼树的根节点出发，到每个叶子节点（对应一个字符）的路径：左分支记为0，右分支记为1，路径上的 0/1 序列就是该字符的哈夫曼编码。

正确性

哈夫曼编码满足贪心选择性质和最优子结构，每次选两个频率最小的节点合并，最终得到的总带权路径长度一定最小，是最优前缀编码。

单源最短路径

单源最短路径问题：给定一个带权图（有向 / 无向）和一个源点，求从源点出发，到图中所有其他顶点的最短路径长度。

经典算法：Dijkstra 算法（贪心思想实现）

适用于不含负权边的带权图，是贪心算法的典型应用。

核心思路

1. 将图中顶点分为两个集合：
   • S 集合：已经确定最短路径长度的顶点；
   • U 集合：尚未确定最短路径的顶点。
2. 初始化：源点加入 S，最短距离为 0；其他顶点距离初始化为无穷大。
3. 贪心选择：每次从 U 集合中，选出距离源点最近的顶点 u，加入 S 集合；
4. 松弛操作：用顶点 u 的最短距离，更新 u 所有邻接顶点的当前最短距离；
5. 重复「选顶点 - 松弛」步骤，直到所有顶点都加入 S 集合。

复杂度

• 邻接矩阵实现：时间复杂度O(n²)；
• 堆优化（优先队列）实现：时间复杂度O(mlogn)（m 为边数，n 为顶点数）。

注意

Dijkstra 算法不能处理负权边，因为负权边会破坏「每次选距离最小的顶点，其最短路径已确定」的贪心选择性质；含负权边的单源最短路径需用 Bellman-Ford 或 SPFA 算法。

背包和0-1背包问题