排序算法

排序算法是计算机科学中一类用于将一组数据按照特定顺序排列的算法。常见的排序算法可以根据其复杂度、稳定性以及适用的数据规模等因素进行分类。以下是一些常用的排序算法：

冒泡排序

时间复杂度：

  1. 冒泡排序（Bubble Sort）：通过重复地遍历列表，比较相邻元素并交换顺序不对的元素。每一轮遍历后最大的元素会像气泡一样“浮”到列表的末尾。

  2. 选择排序（Selection Sort）：每次从未排序部分选出最小（或最大）的一个元素，存放到已排序序列的末尾。

  3. 插入排序（Insertion Sort）：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  4. 希尔排序（Shell Sort）：基于插入排序，改进了其移动只能一步一移的缺点，先将整个待排序列分割成若干子序列分别进行直接插入排序，然后依次缩减增量再进行排序，最后使所有元素都是基本有序的，最后再对全体进行一次插入排序。

  5. 归并排序（Merge Sort）：采用分治法的一种非常典型的排序算法。首先把长度为n的输入序列分成两个长度为n/2的子序列，然后对这两个子序列分别采用归并排序，最后将两个排序好的子序列合并成一个最终的排序序列。

  6. 快速排序（Quick Sort）：也是一种分治的算法。它选择一个基准元素，将数组分为两部分，一部分比基准元素小，另一部分大于等于基准元素，然后再递归地对这两部分继续进行排序。

  7. 堆排序（Heap Sort）：利用堆这种数据结构来设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点。

  8. 计数排序（Counting Sort）：适用于一定范围内的整数排序。以额外空间换取时间效率，通过计算每个数值出现次数，然后按序分布回原数组。

  9. 桶排序（Bucket Sort）：工作的原理是将数组分到有限数量的桶里面，然后对每个桶分别进行排序，最后将各个桶中的数据有序合并起来。

  10. 基数排序（Radix Sort）：一种非比较型排序算法，主要用于处理较大的数字排序问题。它通过对每一位数字进行排序，从而达到整体排序的效果。

最短路径算法

弗洛伊德算法

用于求从所有顶点对之间的最短路径，可以处理有向图或负边权，但不能处理含有负边环的情况。

1
2
3
4
5
6
for (int k = 0; k < N; ++k) // 定义中转节点k
	for (int i = 0; i < N; ++i) // 定义起点i
		for (int j = 0; j < N; ++j) // 定义终点j
			//若通过中转节点到终点的距离小于直接从起点到终点的距离，更新最小距离
			if (dist[i][k] + dist[k][j] < dist[i][j])
				dist[i][j] = dist[i][k] + dist[k][j];

迪杰斯特拉算法

适用于单源最短，即从一个点到其他所有点的最短路径，要求不含负边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dijkstra(int src, const vector<vector<Edge>>& graph, vector<int>& dist) {
    int vertices = graph.size();
    // 初始化距离向量和优先队列
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    dist[src] = 0;
    pq.push(make_pair(src, dist[src]));

    while (!pq.empty()) {
        int u = pq.top().first;
        pq.pop();

        for (auto& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(v, dist[v]));
            }
        }
    }
}

最小生成树算法

Prim算法

普里姆算法（Prim算法）是一种用于在加权连通图中寻找最小生成树的贪心算法。最小生成树是一棵包含图中所有顶点的树，其边的权重之和最小。

算法步骤

  1. 初始化：选择一个起始顶点，将其加入集合$V_{new}$中，集合$E_{new}$为空，用于存储最小生成树的边。
  2. 选择边：从集合$E$中选择一条边$<u, v>$，其中$u$是$V_{new}$中的顶点，$v$不在$V_{new}$中，且边的权值最小。
  3. 加入集合：将顶点$v$加入$V_{new}$，边$<u, v>$加入$E_{new}$。
  4. 重复操作：重复步骤2和步骤3，直到$V_{new}$包含图中的所有顶点。
  5. 输出结果：集合$V_{new}$和$E_{new}$构成了图的最小生成树。

代码示例（C++）

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <vector>
#include <queue>
#include <climits> // 为了使用 INT_MAX

using namespace std;

// 定义边结构体
struct Edge {
    int to; // 目标节点
    int weight; // 权重
};

// 定义优先队列使用的比较类，使得可以按权重从小到大排序
struct Compare {
    bool operator()(const Edge& a, const Edge& b) {
        return a.weight > b.weight;
    }
};

void prim(const vector<vector<Edge>>& graph, int start) {
    int vertices = graph.size();
    vector<bool> visited(vertices, false); // 标记顶点是否已访问
    vector<Edge> mst; // 存储最小生成树的边

    // 将起始顶点的所有边加入优先队列
    priority_queue<Edge, vector<Edge>, Compare> pq;
    for (const auto& edge : graph[start]) {
        pq.push(edge);
    }

    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        int u = start;
        int v = e.to;
        if (visited[v]) {
            continue; // 如果顶点已访问，跳过
        }

        // 将顶点加入最小生成树
        visited[v] = true;
        mst.push_back(e);
        start = v;

        // 将新顶点的所有边加入优先队列
        for (const auto& edge : graph[v]) {
            pq.push(edge);
        }
    }

    // 输出最小生成树的边
    cout << "最小生成树的边：" << endl;
    for (const auto& edge : mst) {
        cout << edge.to << " - " << edge.weight << endl;
    }
}

int main() {
    // 示例图的邻接表表示
    vector<vector<Edge>> graph = {
        {{1, 4}, {2, 1}}, // 节点0连接到节点1(权重4)和节点2(权重1)
        {{3, 1}},         // 节点1连接到节点3(权重1)
        {{1, 2}, {3, 5}}, // 节点2连接到节点1(权重2)和节点3(权重5)
        {}                // 节点3没有出边
    };

    int startNode = 0; // 起始节点

    prim(graph, startNode);

    return 0;
}

说明

  • 上述代码使用邻接表表示图，通过优先队列实现边的选择。
  • 算法从起始节点开始，逐步选择权重最小的边，将其加入最小生成树，直到所有顶点都被访问。
  • 输出最小生成树的边，显示构成最小生成树的各条边及其权重。

克鲁斯卡尔算法

克鲁斯卡尔算法（Kruskal算法）是一种用于在加权连通图中寻找最小生成树的贪心算法。该算法通过不断选择权重最小的边，确保这些边不会形成环，直到生成树包含图中的所有顶点。

算法步骤

  1. 初始化：将图中的所有边按权重从小到大排序。创建一个并查集数据结构，用于判断两个顶点是否属于同一个连通分量。
  2. 选择边：从排序后的边列表中选择权重最小的边。
  3. 判断连通性：使用并查集判断该边的两个顶点是否属于同一个连通分量。
  4. 加入集合：如果两个顶点不在同一个连通分量，将该边加入最小生成树，并将这两个连通分量合并。
  5. 重复操作：重复步骤2到步骤4，直到最小生成树包含图中的所有顶点。
  6. 输出结果：得到的最小生成树即为图的权重最小的生成树。

代码示例（C++）

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义边结构体
struct Edge {
    int from; // 起始顶点
    int to; // 目标顶点
    int weight; // 权重
};

// 定义并查集类
class DisjointSet {
public:
    DisjointSet(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false; // 已经在同一个集合中
        }
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
        return true;
    }

private:
    vector<int> parent;
    vector<int> rank;
};

void kruskal(const vector<Edge>& edges, int vertices) {
    // 按权重排序边
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    // 创建并查集
    DisjointSet ds(vertices);

    vector<Edge> mst; // 存储最小生成树的边
    for (const auto& edge : edges) {
        int u = edge.from;
        int v = edge.to;
        if (ds.unite(u, v)) {
            mst.push_back(edge);
        }
    }

    // 输出最小生成树的边
    cout << "最小生成树的边：" << endl;
    for (const auto& edge : mst) {
        cout << edge.from << " - " << edge.to << " : " << edge.weight << endl;
    }
}

int main() {
    // 示例图的边列表
    vector<Edge> edges = {
        {0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 1}, {2, 3, 5}
    };
    int vertices = 4; // 图中的顶点数

    kruskal(edges, vertices);

    return 0;
}

说明

  • 上述代码使用边列表表示图，通过排序和并查集实现克鲁斯卡尔算法。
  • 算法首先对边按权重排序，然后依次选择边，使用并查集判断边的两个顶点是否属于同一个连通分量。
  • 如果不在同一个连通分量，将该边加入最小生成树，并合并这两个连通分量。
  • 输出最小生成树的边，显示构成最小生成树的各条边及其权重。

拓扑排序

拓扑排序是一种对有向无环图（DAG, Directed Acyclic Graph）进行排序的算法，它可以将图中的顶点排成一个线性序列，使得对于图中的任意一条有向边$u \rightarrow v$，$u$在序列中出现在$v$的前面。拓扑排序在任务调度、依赖关系分析等领域有广泛的应用。

算法步骤

  1. 初始化：计算每个顶点的入度（即指向该顶点的边的数量），并将入度为0的顶点加入一个队列。
  2. 选择顶点：从队列中取出一个顶点，并将其输出到排序结果中。
  3. 更新入度：对于该顶点指向的所有顶点，将其入度减1。如果某个顶点的入度变为0，则将该顶点加入队列。
  4. 重复操作：重复步骤2和步骤3，直到队列为空。
  5. 检查终止条件：如果所有顶点都被输出，则拓扑排序成功；否则，如果图中有环，拓扑排序将失败。

代码示例（C++）

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void topologicalSort(const vector<vector<int>>& graph) {
    int vertices = graph.size();
    vector<int> inDegree(vertices, 0); // 记录每个顶点的入度

    // 计算入度
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < graph[i].size(); ++j) {
            inDegree[graph[i][j]]++;
        }
    }

    queue<int> q; // 存储入度为0的顶点
    for (int i = 0; i < vertices; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> result; // 存储拓扑排序的结果
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        // 更新邻接顶点的入度
        for (int v : graph[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 检查是否有环
    if (result.size() != vertices) {
        cout << "图中有环，拓扑排序失败！" << endl;
    } else {
        cout << "拓扑排序结果：";
        for (int i : result) {
            cout << i << " ";
        }
        cout << endl;
    }
}

int main() {
    // 示例图，邻接表表示
    vector<vector<int>> graph = {
        {1, 2}, // 节点0指向节点1和节点2
        {3},    // 节点1指向节点3
        {3},    // 节点2指向节点3
        {}      // 节点3没有出边
    };

    topologicalSort(graph);

    return 0;
}

说明

  • 上述代码使用邻接表表示图，通过队列实现拓扑排序。
  • 算法首先计算每个顶点的入度，并将入度为0的顶点加入队列。
  • 然后依次从队列中取出顶点，将其加入排序结果，并更新其邻接顶点的入度。
  • 如果某个顶点的入度变为0，则将该顶点加入队列。
  • 最后，检查排序结果的顶点数量是否等于图中的顶点数量，以确定是否存在环。