一些算法知识点 - LINKONG's Blog

常见算法#

快速排序#

实现原理: 采用分治法，设置基准元素，并将原有数组划分为两个部分，一部分为小于基准元素的值，另一部分为大于基准元素的值，通过此操作将基准元素归位，随后对两个子数组递归进行相同操作，直至数组有序。

特点: 不稳定 的，平均时间复杂度 $`O(n logn)`$ ，最坏时间复杂度 $`O(n^2)`$ ，空间复杂度 $`O(logn)`$ 。

1
/*
2
    对数组进行划分操作
3
*/
4
int partition(std::vector<int>& arr, int left, int right){
5
    int i = left, j = right;    // 左右两侧循环进行扫描
6
    while(i < j){               // 条件判断
7
        /*
8
            此处设置左侧第一个元素为基准元素
9
        */
10
        // 先判断右指针，再判断左指针
11
        while(i < j && arr[left] <= arr[j])
12
            j--;
13
        while(i < j && arr[i] <= arr[left])
14
            i++;                // 逐渐缩减范围
15
        /*
16
            当左右两侧指针越界或者找到位置不合适的元素时，进行元素的交换
17
        */
18
        swap(arr[i], arr[j]);
19
    }
20
    swap(arr[i], arr[low])      // 将原来的基准元素放置到合适位置
21
    return i;                   // 返回更新后的两个数组的界限下标
22
}
23

24
/*
25
    递归操作
26
*/
27
void quick_sort(vector<int>& arr, int left, int right){
28
    if(left >= right) return;                   // 触底反弹
29
    int privot = partition(arr, left, right);   // 获取分割后的基准值
30

31
    quick_sort(arr, left, privot - 1);          // 对左数组进行分割
32
    quick_sort(arr, privot + 1, right);         // 对右数组进行分割
33
}

深度优先搜索#

实现原理: 是一种基于递归的图遍历算法，通过邻接表获取节点的相邻信息，并标记已经访问的节点，确保每个节点都被遍历。
时间复杂度: $O(V+E)$ ，只需要遍历每个节点和每条边一次便可。

1
void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited){
2
    visited[u] = true;
3

4
    for(int v: adj<u>)
5
        if(!visited[v]) dfs(v, adj, visited);
6
}

广度优先搜索#

实现原理: 利用队列的FIFO特性，确保元素的逐个访问，并标记已经访问的元素，循环遍历，直至所有元素都被标记。
时间复杂度: $O(V+E)$ ;
空间复杂度: $O(V)$ ;

1
void bfs(int start, vector<vector<int>>& adj, int numNodes){
2
    queue<int> q;
3
    vector<bool> visited(numNodes, false);
4

5
    q.push(start);
6
    visited[start] = true;
7

8
    while(!q.empty()){
9
        int u = q.front;
10
        q.pop();
11

12
        for(int v: adj[u]){
13
            if(!visited[v]){
14
                visited[v] = true;
15
                q.push(v);
16
            }
17
        }
18
    }
19
}

霍夫曼树#

构造过程: 每次从待选取队列中选取两个值最小的元素，遵循左小右大原则，进行组合生成新的元素，并添加到原有队列中，循环此步骤，直至构成一棵树。