【算法】常见数据结构算法总结
in 博客目录
本文介绍了常见的数据结构和算法
八大数据结构
数组
数组是一种线性表数据结构，它使用一组连续的内存空间，来存储一组具有相同类型的数据。
C++举例：
#include <iostream>
int main() {
// 定义一个整型数组，大小为5
int arr[5] = {1, 2, 3, 4, 5};
// 访问数组元素
std::cout << "第一个元素: " << arr[0] << std::endl;
std::cout << "第二个元素: " << arr[1] << std::endl;
// 修改数组元素
arr[2] = 10;
std::cout << "修改后的第三个元素: " << arr[2] << std::endl;
return 0;
}
数组的优点
- 随机访问：由于数组在内存中是连续存储的，因此可以通过索引快速访问任何元素，时间复杂度为O(1)。
- 缓存友好：连续的内存空间使得数组在缓存中更容易被加载和访问，提高了访问效率。
- 简单易用：数组的定义和使用非常简单，易于理解和实现。
数组的缺点
- 大小固定：数组的大小在定义时就确定了，无法动态扩展或缩小。如果需要存储更多的元素，就需要重新定义一个更大的数组，并将原数组的元素复制到新数组中。
- 插入和删除效率低：在数组中插入或删除元素时，需要移动大量的元素，时间复杂度为O(n)。
- 内存浪费：如果数组的大小定义得过大，可能会导致内存浪费；如果定义得过小，可能会导致数据溢出。
数组是一种简单而高效的数据结构，适用于需要快速随机访问元素的场景。然而，由于其 大小固定和插入删除效率低 的缺点，在需要动态调整大小或频繁插入删除元素的场景中，可能需要使用其他数据结构，如 链表 、 动态数组 （如C++中的std::vector）等。
动态数组原理
在C++中，动态数组的实现是基于其 内存管理机制 的，刚刚写到的静态数组由于其大小固定，使用上有诸多不便。
动态数组的实现原理是通过 内存分配 和 内存释放 来实现的。当需要添加元素时，如果当前数组已满，就需要重新分配一块更大的内存空间，并 将原数组的元素复制到新数组 中。当需要删除元素时，如果当前数组的元素较少，就需要释放内存空间，并将原数组的元素复制到新数组中。
动态数组的实现方式有很多种，其中最常见的是使用 指针 和 内存分配函数 来实现。在C++中，可以使用 new 运算符来分配内存，使用 delete 运算符来释放内存。
#include <iostream>
int main() {
// 定义一个动态数组，初始大小为5
int* arr = new int[5];
// 向数组中添加元素
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
arr[4] = 5;
// 输出数组元素
for (int i = 0; i < 5; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
// 重新分配内存，大小为10
int* newArr = new int[10];
// 将原数组的元素复制到新数组中
for (int i = 0; i < 5; i++) {
newArr[i] = arr[i];
}
// 释放原数组的内存
delete[] arr;
// 将旧的数组指针指向新申请的大数组
arr = newArr;
// 向数组中添加元素
arr[5] = 6;
arr[6] = 7;
arr[7] = 8;
arr[8] = 9;
arr[9] = 10;
// 输出数组元素
for (int i = 0; i < 10; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
// 释放新数组的内存
delete[] newArr;
return 0;
}
链表
链表是一种非连续存储的线性结构，每个元素包含 数据 和指向下一个元素的指针。链表的优点是插入和删除操作高效，但访问速度较慢。
单向链表每个节点包含数据和指向下一个节点的指针。双向链表每个节点包含数据和 指向前一个节点和后一个节点 的指针。
#include <iostream>
// 定义链表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
int main() {
// 创建链表
ListNode* head = new ListNode(1);
ListNode* second = new ListNode(2);
ListNode* third = new ListNode(3);
head->next = second;
second->next = third;
// 访问链表元素
ListNode* current = head;
while (current != NULL) {
std::cout << current->val << " ";
current = current->next;
}
return 0;
}
链表的优点
- 动态大小：链表的大小可以动态增长或缩小，不需要预先分配固定大小的内存。
- 插入和删除高效：在链表中插入或删除元素时，只需要修改指针，不需要移动大量的元素，时间复杂度为O(1)。
链表的缺点
- 随机访问效率低：由于链表的元素不是连续存储的，因此无法通过索引快速访问元素，需要从头开始遍历链表，时间复杂度为O(n)。
- 额外的内存开销：链表的每个节点需要额外的指针来指向下一个节点，增加了内存开销。
链表是一种灵活的数据结构，适用于需要 频繁插入和删除元素 的场景。然而，由于其随机访问效率低的缺点，在需要快速随机访问元素的场景中，可能需要使用其他数据结构，如数组、动态数组（如C++中的std::vector）等。
栈
栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，它只允许在一端进行插入和删除操作。这一端通常被称为栈顶。栈的操作主要有两种：压入（push）和弹出（pop）。压入操作将元素添加到栈顶，弹出操作则从栈顶移除元素。
#include <iostream>
#include <stack>
int main() {
// 创建一个栈
std::stack<int> myStack;
// 压入元素
myStack.push(1);
myStack.push(2);
myStack.push(3);
// 访问栈顶元素
std::cout << "栈顶元素: " << myStack.top() << std::endl;
// 弹出栈顶元素
myStack.pop();
// 再次访问栈顶元素
std::cout << "弹出一个元素后，栈顶元素: " << myStack.top() << std::endl;
return 0;
}
栈的优点
- 简单高效：栈的操作非常简单，只需要在栈顶进行插入和删除操作，时间复杂度为O(1)。
- 内存管理方便：栈的内存管理由系统自动完成，不需要手动分配和释放内存。
- 支持递归：栈在递归算法中非常有用，因为递归调用的返回地址和局部变量都存储在栈中。
栈的缺点
- 大小固定：栈的大小通常是固定的，如果栈满了，再进行压入操作就会导致栈溢出。
- 不支持随机访问：栈不支持随机访问，只能访问栈顶元素。
栈是一种简单而高效的数据结构，适用于需要 后进先出 操作的场景，如函数调用、表达式求值等。然而，由于其 大小固定和不支持随机访问 ，在需要动态调整大小或随机访问元素的场景中，可能需要如动态数组（如C++中的std::vector）等的数据结构。
队列
队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，它只允许在一端进行插入操作（队尾），在另一端进行删除操作（队头）。队列常用于广度优先搜索和任务调度等场景。
#include <iostream>
#include <queue>
int main() {
// 创建一个队列
std::queue<int> myQueue;
// 入队操作
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
// 访问队头元素
std::cout << "队头元素: " << myQueue.front() << std::endl;
// 出队操作
myQueue.pop();
// 再次访问队头元素
std::cout << "出队一个元素后，队头元素: " << myQueue.front() << std::endl;
return 0;
}
队列的优点
- 简单高效：队列的操作非常简单，只需要在队尾进行插入操作，在队头进行删除操作，时间复杂度为O(1)。
- 顺序性：队列能够保持元素的顺序，先进入队列的元素先被处理，这对于需要按照顺序处理数据的场景非常有用。
- 支持并发：在多线程环境中，队列可以用于实现线程安全的数据共享，例如生产者-消费者模型。
队列的缺点
- 大小固定：队列的大小通常是固定的，如果队列满了，再进行插入操作就会导致队列溢出。
- 不支持随机访问：队列不支持随机访问，只能访问队头和队尾的元素。
树
树（Tree）是一种非线性的数据结构，它由 节点（Node）和边（Edge） 组成。每个节点可以有 零个或多个 子节点，而每个子节点又可以有零个或多个子节点，以此类推。树的顶部节点称为根节点（Root），没有子节点的节点称为叶子节点（Leaf）。树结构常用于表示 层次关系 的数据，如文件系统。
二叉树（Binary Tree）是一种特殊的树结构，它的每个节点 最多有两个 子节点，通常称为左子节点和右子节点。
二叉树的特点
- 每个节点最多有两个子节点：这是二叉树的定义，也是它与其他树结构的主要区别。
- 子节点的顺序：左子节点和右子节点是有顺序的，不能随意交换。即二叉树是有序树
- 递归定义：二叉树可以递归地定义为一个节点，该节点有一个数据元素和两个指向子二叉树的指针。
二叉树的类型
- 满二叉树：除了叶子节点外， 每个节点都有两个子节点 ，并且所有叶子节点都在同一层。
- 完全二叉树：除了最后一层外，其他层的节点数都是满的，并且最后一层的节点都靠左排列。
- 平衡二叉树：树上的每个节点，其左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的遍历
- 前序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。
- 中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
- 后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。
- 层序遍历：从根节点开始，按照从上到下、从左到右的顺序依次访问每个节点。
前三种称为深度优先遍历（DFS），层序遍历为广度优先遍历（BFS）。
#include <iostream>
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
std::cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
std::cout << root->val << " ";
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->val << " ";
}
// 层序遍历
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
std::cout << node->val << " ";
if (node->left != NULL) q.push(node->left);
if (node->right != NULL) q.push(node->right);
}
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 前序遍历二叉树
std::cout << "前序遍历结果: ";
preorderTraversal(root);
std::cout << std::endl;
// 中序遍历二叉树
std::cout << "中序遍历结果: ";
inorderTraversal(root);
std::cout << std::endl;
// 后序遍历二叉树
std::cout << "后序遍历结果: ";
postorderTraversal(root);
std::cout << std::endl;
// 层序遍历二叉树
std::cout << "层序遍历结果: ";
levelOrderTraversal(root);
std::cout << std::endl;
return 0;
}
树的优点
- 层次结构清晰：树结构能够清晰地表示数据之间的层次关系，例如文件系统、组织结构等。
- 高效的搜索和插入操作：对于平衡树（如二叉搜索树），搜索、插入和删除操作的平均时间复杂度为O(log n)，其中n是树中节点的数量。
- 动态数据结构：树的大小可以动态增长或缩小，不需要预先分配固定大小的内存。
树的缺点
- 实现复杂：相比于线性数据结构（如数组、链表），树的实现通常更加复杂，需要更多的代码和逻辑。
- 空间开销较大：树的每个节点需要额外的指针来指向其子节点，这增加了内存开销。
- 不支持随机访问：树不支持像数组那样的随机访问，访问特定节点需要从根节点开始遍历。
树是一种非常有用的数据结构，适用于表示 层次关系和需要高效搜索、插入操作 的场景。然而，由于其 实现复杂和空间开销较大 的缺点，在简单的线性数据结构能够满足需求的情况下，可能不需要使用树。
哈希表
哈希表（Hash Table）是一种根据关键码值（Key value）而直接进行访问的数据结构。它通过哈希函数 将键映射到数组 中的位置，从而实现快速查找。。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。哈希表的优点是查找速度快，但需要处理哈希冲突。
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 创建一个哈希表
std::unordered_map<std::string, int> hashTable;
// 插入键值对
hashTable["apple"] = 1;
hashTable["banana"] = 2;
hashTable["cherry"] = 3;
// 查找键值对
std::cout << "The value of 'apple' is: " << hashTable["apple"] << std::endl;
// 删除键值对
hashTable.erase("banana");
// 遍历哈希表
for (const auto& pair : hashTable) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
哈希表的优点
- 快速查找：哈希表的查找、插入和删除操作的平均时间复杂度为O(1)，这使得它在处理大量数据时非常高效。
- 灵活性：哈希表可以存储不同类型的数据，并且可以动态调整大小以适应数据的增长或减少。
- 高效的内存使用：哈希表通常比其他数据结构（如树）更节省内存，因为它们不需要维护复杂的指针结构。
哈希表的缺点
- 哈希冲突：不同的关键码值可能映射到相同的哈希表位置，这称为哈希冲突。解决哈希冲突需要额外的处理，这可能会增加时间和空间复杂度。
- 不支持顺序访问：哈希表不支持像数组或链表那样的顺序访问，因此在需要按顺序遍历数据的场景中可能不太适用。
- 哈希函数的选择：哈希表的性能很大程度上取决于哈希函数的选择。一个好的哈希函数应该能够均匀地分布关键码值，以减少哈希冲突的可能性。
哈希表是一种非常有用的数据结构，适用于需要快速查找和插入操作的场景。然而，由于其 哈希冲突和灵活性，不保证顺序 的缺点，在需要 顺序访问 或需要 维护复杂指针结构 的场景中，可能需要使用其他数据结构，如树或数组等。
堆
堆（Heap）是一种特殊的树结构，通常是一个 完全二叉树 。堆分为最大堆和最小堆，其中最大堆的每个节点的值都大于或等于其子节点的值，最小堆的每个节点的值都小于或等于其子节点的值。堆常用于实现优先队列，其中最大堆用于实现最大优先队列，最小堆用于实现最小优先队列。
#include <iostream>
#include <queue>
int main() {
// 创建一个最大堆
std::priority_queue<int> maxHeap;
// 插入元素
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
maxHeap.push(1);
maxHeap.push(5);
// 访问最大元素
std::cout << "最大元素: " << maxHeap.top() << std::endl;
// 删除最大元素
maxHeap.pop();
// 再次访问最大元素
std::cout << "删除最大元素后，最大元素: " << maxHeap.top() << std::endl;
return 0;
}
堆的优点
- 高效的插入和删除操作：在堆中插入和删除元素的时间复杂度为O(log n)，其中n是堆中元素的数量。这使得堆在处理大量数据时非常高效。
- 快速访问最大或最小元素：在最大堆中，根节点始终是最大元素；在最小堆中，根节点始终是最小元素。因此，可以在O(1)时间内访问最大或最小元素。
- 动态调整大小：堆可以动态调整大小，以适应数据的增长或减少。
堆的缺点
- 不支持随机访问：堆不支持像数组那样的随机访问，因此在需要按顺序遍历数据的场景中可能不太适用。
- 不保证元素的顺序：堆只保证根节点是最大或最小元素，而不保证其他元素的顺序。
- 空间开销：堆的每个节点需要额外的空间来存储其子节点的指针，这增加了内存开销。
堆是一种非常有用的数据结构，适用于需要快速访问最大或最小元素的场景，如优先队列。然而，由于其不支持随机访问和不保证元素顺序的特点，在某些特定场景下可能需要考虑其他数据结构。
图
图（Graph）是一种非线性的数据结构，由顶点（Vertex）和边（Edge）组成。顶点表示对象，边表示对象之间的关系。图分为有向图和无向图。图可以用来表示各种复杂的关系，如社交网络、交通网络、计算机网络等。
#include <iostream>
#include <vector>
#include <list>
class Graph {
private:
int numVertices;
std::vector<std::list<int>> adjLists;
public:
Graph(int vertices) : numVertices(vertices) {
adjLists.resize(numVertices);
}
void addEdge(int src, int dest) {
adjLists[src].push_back(dest);
// 如果是无向图，需要添加反向边
// adjLists[dest].push_back(src);
}
void printGraph() {
for (int i = 0; i < numVertices; ++i) {
std::cout << "Vertex " << i << ": ";
for (int neighbor : adjLists[i]) {
std::cout << neighbor << " ";
}
std::cout << std::endl;
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
return 0;
}
图的优点
- 强大的表示能力：图可以表示各种复杂的关系，如社交网络中的朋友关系、交通网络中的道路连接等。
- 灵活性：图可以是有向的（边有方向）或无向的（边无方向），可以是加权的（边有权重）或无权的（边无权重）。
- 广泛的应用领域：图在许多领域都有广泛的应用，如计算机科学、数学、物理学、生物学、社会学等。
图的缺点
- 实现复杂：图的实现通常比其他数据结构更复杂，需要更多的代码和逻辑。
- 空间开销大：图的存储通常需要更多的空间，尤其是在处理大规模图时。
- 算法复杂度高：许多图算法的时间复杂度较高，如最短路径算法、最小生成树算法等。
图是一种非常强大的数据结构，适用于表示各种复杂的关系。然而，由于其实现复杂和空间开销大的缺点，在处理小规模数据或简单关系时，可能不需要使用图。
算法
算法思想
递归
递归是一种解决问题的方法，它将问题分解为更小的子问题，直到问题足够简单可以直接解决。递归的基本思想是将一个大问题分解为一个或多个相似的子问题，然后通过解决这些子问题来解决原始问题。
递归的基本步骤如下：
- 定义基本情况：确定递归的终止条件，即当问题足够简单时，不需要再分解为子问题，直接解决。
- 分解问题：将原始问题分解为一个或多个相似的子问题。
- 解决子问题：递归地解决子问题，得到子问题的解。
- 合并子问题：将子问题的解合并为原始问题的解。
#include <iostream>
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int n = 5;
int result = factorial(n);
std::cout << "Factorial of " << n << " is " << result << std::endl;
return 0;
}
递归的优点
- 简洁性：递归可以使代码更加简洁，因为它可以将复杂的问题分解为简单的子问题。
- 可扩展性：递归可以使算法更易于扩展，因为它可以将问题分解为更小的子问题，从而更容易地解决更大的问题。
递归的缺点
- 效率较低：递归的实现通常比迭代的实现效率较低，因为递归需要保存函数调用的状态，并且可能会导致栈溢出。
- 可读性较差：递归的实现可能会使代码变得难以理解，特别是当递归深度较大时。
递归是一种强大的算法思想，适用于解决许多问题。然而，递归的实现可能会导致效率较低，并且代码变得难以理解。在选择使用递归时，需要权衡其优点和缺点，并根据具体情况进行选择。
回溯
回溯是一种通过尝试不同的可能来解决问题的算法思想。它通常用于解决组合优化问题，如旅行商问题、子集和问题等。回溯的基本思想是从一个初始状态开始，尝试所有可能的选择，直到找到一个解或确定问题无解。
回溯的基本步骤如下：
- 定义初始状态：确定问题的初始状态，即问题的初始状态。
- 定义选择列表：确定在当前状态下可以进行的选择列表。
- 尝试选择：对于每个选择，尝试将其应用于当前状态，得到一个新的状态。
- 检查是否满足条件：检查新状态是否满足问题的条件，如果满足条件，则找到了一个解。
- 回溯：如果新状态不满足条件，则需要回溯到上一个状态，并尝试其他选择。
#include <iostream>
#include <vector>
void backtrack(std::vector<int>& nums, std::vector<int>& path, std::vector<std::vector<int>>& result) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int num : nums) {
if (std::find(path.begin(), path.end(), num) == path.end()) {
path.push_back(num);
backtrack(nums, path, result);
path.pop_back();
}
}
}
int main() {
std::vector<int> nums = {1, 2, 3};
std::vector<int> path;
std::vector<std::vector<int>> result;
backtrack(nums, path, result);
for (const auto& permutation : result) {
for (int num : permutation) {
std::cout << num << " ";
}
std::cout << std::endl;
}
return 0;
}
回溯的优点
- 灵活性：回溯可以使算法更灵活，因为它可以处理各种不同的问题。
- 易于理解：回溯的实现通常比其他算法更易于理解，因为它可以将问题分解为更小的子问题。
回溯的缺点
- 效率较低：回溯的实现通常比其他算法效率较低，因为它需要尝试所有可能的选择。
- 可读性较差：回溯的实现可能会使代码变得难以理解，特别是当递归深度较大时。
回溯是一种强大的算法思想，适用于解决组合优化问题。然而，回溯的实现可能会导致效率较低，并且代码变得难以理解。在选择使用回溯时，需要权衡其优点和缺点，并根据具体情况进行选择。
深度广度优先
深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的图遍历算法，用于在图中搜索特定的节点或路径。 深度优先搜索（DFS）是一种沿着树的深度遍历树的节点，尽可能深的搜索树的分支。它从根节点开始，沿着一条路径尽可能深入地搜索，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径。 广度优先搜索（BFS）是一种沿着树的宽度遍历树的节点。它从根节点开始，沿着树的宽度遍历节点，直到所有节点都被访问为止。
深度优先搜索（DFS）的基本步骤如下：
- 从起始节点开始，将其标记为已访问。
- 访问起始节点的所有未访问邻居节点，并将它们标记为已访问。
- 对于每个已访问的邻居节点，重复步骤2和3，直到所有节点都被访问。
广度优先搜索（BFS）的基本步骤如下：
- 从起始节点开始，将其标记为已访问，并将其加入队列。
- 从队列中取出一个节点，并访问它的所有未访问邻居节点，并将它们标记为已访问，并将它们加入队列。
- 重复步骤2和3，直到队列为空。
#include <iostream>
#include <vector>
#include <queue>
// 定义图的邻接表表示
std::vector<std::vector<int>> graph = {
{1, 2}, // 节点0的邻居节点为1和2
{0, 2, 3}, // 节点1的邻居节点为0、2和3
{0, 1, 3}, // 节点2的邻居节点为0、1和3
{1, 2} // 节点3的邻居节点为1和2
};
// 深度优先搜索
void dfs(int start, std::vector<bool>& visited) {
visited[start] = true;
std::cout << start << " ";
for (int neighbor : graph[start]) {
if (!visited[neighbor]) {
dfs(neighbor, visited);
}
}
}
// 广度优先搜索
void bfs(int start, std::vector<bool>& visited) {
std::queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
std::cout << current << " ";
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
int startNode = 0;
std::vector<bool> visited(graph.size(), false);
std::cout << "深度优先搜索结果: ";
dfs(startNode, visited);
std::cout << std::endl;
visited.assign(graph.size(), false);
std::cout << "广度优先搜索结果: ";
bfs(startNode, visited);
std::cout << std::endl;
return 0;
}
深度优先搜索（DFS）的优点
- 内存效率高：深度优先搜索（DFS）不需要额外的空间来存储节点，因此在内存使用上比广度优先搜索（BFS）更高效。
- 易于实现：深度优先搜索（DFS）的实现相对简单，因为它只需要递归地遍历图即可。
深度优先搜索（DFS）的缺点
- 可能陷入无限循环：深度优先搜索（DFS）可能会陷入无限循环，特别是在图中存在环的情况下。
- 可能无法找到最短路径：深度优先搜索（DFS）可能无法找到最短路径，特别 是在图中存在环的情况下。
广度优先搜索（BFS）的优点
- 找到最短路径：广度优先搜索（BFS）可以找到最短路径，因为它是一种按层次遍历的算法。
- 内存效率低：广度优先搜索（BFS）需要额外的空间来存储节点，因此在内存使用上比深度优先搜索（DFS）更差。
广度优先搜索（BFS）的缺点
- 可能无法找到最优解：广度优先搜索（BFS）可能无法找到最优解，特别是在图中存在环的情况下。
深度优先搜索（DFS）和广度优先搜索（BFS）都是图遍历算法，它们在不同的场景下有不同的应用。在选择使用深度优先搜索（DFS）还是广度优先搜索（BFS）时，需要根据具体情况进行选择。
动态规划
动态规划（Dynamic Programming）是一种解决复杂问题的算法思想，它通过将问题分解为子问题，并将子问题的解存储起来，以避免重复计算，从而提高算法的效率。动态规划通常用于优化问题，如最长公共子序列、最短路径等。
动态规划的基本步骤如下：
- 定义子问题：将原始问题分解为若干个子问题。
- 确定状态：确定子问题的状态，即子问题的输入和输出。
- 确定状态转移方程：确定子问题之间的状态转移关系。
- 确定初始状态：确定子问题的初始状态。
#include <iostream>
#include <vector>
int fibonacci(int n) {
if (n <= 1) {
return n;
}
std::vector<int> dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int n = 10;
int result = fibonacci(n);
std::cout << "Fibonacci(" << n << ") = " << result << std::endl;
return 0;
}
动态规划的优点
- 高效性：动态规划可以避免重复计算，从而提高算法的效率。
- 可扩展性：动态规划可以方便地扩展到其他问题。
动态规划的缺点
- 空间复杂度高：动态规划需要存储子问题的解，因此在空间使用上可能较高。
- 可读性较差：动态规划的实现可能会使代码变得难以理解，特别是在状态转移方程比较复杂的情况下。
动态规划是一种强大的算法思想，适用于解决复杂问题。然而，动态规划的实现可能会导致效率较低，并且代码变得难以理解。在选择使用动态规划时，需要根据具体情况进行选择。
贪婪算法
贪婪算法（Greedy Algorithm）是一种近似解决问题的算法思想，它在每一步选择中都采取当前最优的选择，从而希望最终能够得到全局最优解。贪婪算法通常用于优化问题，如最短路径、背包问题等。
贪婪算法的基本步骤如下：
- 定义问题：确定要解决的问题。
- 确定贪心策略：确定每一步选择的贪心策略。
- 确定初始状态：确定子问题的初始状态。
#include <iostream>
#include <vector>
// 定义商品结构体
struct Item {
int weight; // 商品重量
int value; // 商品价值
};
// 贪婪算法求解背包问题
void knapsackGreedy(std::vector<Item>& items, int capacity) {
int n = items.size();
std::vector<bool> selected(n, false); // 记录每个商品是否被选中
int totalWeight = 0; // 记录当前背包的总重量
for (int i = 0; i < n; ++i) {
if (totalWeight + items[i].weight <= capacity) {
selected[i] = true;
totalWeight += items[i].weight;
} else {
break; // 背包已满，停止选择
}
}
// 输出结果
std::cout << "Selected items: ";
for (int i = 0; i < n; ++i) {
if (selected[i]) {
std::cout << "(" << items[i].weight << ", " << items[i].value << ") ";
}
}
std::cout << std::endl;
}
int main() {
std::vector<Item> items = { {10, 60}, {20, 100}, {30, 120} };
int capacity = 50;
knapsackGreedy(items, capacity);
return 0;
}
贪婪算法的优点
- 高效性：贪婪算法可以在多项式时间内找到近似最优解。
贪婪算法的缺点
- 不保证最优解：贪婪算法可能无法找到全局最优解，只能找到近似最优解。
- 不适用范围广：贪婪算法通常只适用于特定类型的问题，不适用于所有问题。
贪婪算法是一种简单但高效的算法思想，适用于解决优化问题。然而，贪婪算法可能无法找到全局最优解，只能找到近似最优解。在选择使用贪婪算法时，需要根据具体情况进行选择。
排序算法
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
每一轮，从原乱序的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
// 将比较大的元素往后移动
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
冒泡排序的优点
- 简单易懂：冒泡排序的实现非常简单，易于理解和实现，适合初学者学习排序算法的基本概念。
- 稳定性：冒泡排序是一种稳定的排序算法，即相等元素的相对顺序在排序后不会改变。
冒泡排序的缺点
- 效率较低：冒泡排序的时间复杂度为O(n^2)，其中n是要排序的元素数量。这意味着当处理大量数据时，冒泡排序的效率会非常低。
- 不适合大规模数据：由于其时间复杂度较高，冒泡排序不适合用于大规模数据的排序。
冒泡排序是一种简单但效率较低的排序算法，适用于小规模数据的排序或作为学习排序算法的入门示例。在实际应用中，对于大规模数据的排序，通常会使用更高效的排序算法，如快速排序、归并排序等。
插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是通过从前往后构建有序序列，对于当前检查的未排序数据，在前面已排序序列中从后向前扫描，找到相应位置并插入。
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// 将大于key的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
前两次循环的过程图：
插入排序的优点
- 简单易懂：插入排序的实现非常简单，易于理解和实现，适合初学者学习排序算法的基本概念。
- 稳定性：插入排序是一种稳定的排序算法，即相等元素的相对顺序在排序后不会改变。
插入排序的缺点
- 效率较低：插入排序的时间复杂度为O(n^2)，其中n是要排序的元素数量。这意味着当处理大量数据时，插入排序的效率会非常低。
- 不适合大规模数据：由于其时间复杂度较高，插入排序不适合用于大规模数据的排序。
插入排序是一种简单但效率较低的排序算法，适用于 小规模数据的排序 或作为学习排序算法的入门示例。在实际应用中，对于大规模数据的排序，通常会使用更高效的排序算法，如快速排序、归并排序等。
快速排序
快速排序（Quick Sort）是一种高效的排序算法，它基于分治的策略来对数组进行排序。快速排序的基本思想是选择一个基准元素，将数组分为两部分，一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大，然后对这两部分分别进行排序。
#include <iostream>
#include <vector>
// 划分函数，选取一个基准元素，将数组分为两部分，走完之后，基准元素插入到其该在的位置，其右侧所有元素都比基准元素大，左侧所有元素都比基准元素小
int partition(std::vector<int>& arr, int low, int high){
int base = arr[high];
int baseIndex = low;
// 遍历数组，将所有小于基准元素的元素都移动到基准元素的左侧
for(int i=low;i<=high;i++){
if(arr[i]<base){
std::swap(arr[i], arr[baseIndex]);
baseIndex++;
}
}
// 将基准元素插入到其该在的位置
std::swap(arr[high], arr[baseIndex]);
return baseIndex;
}
// 递归快速排序，只要目标区域包含两个及以上的元素，就继续排序
void quickSort(std::vector<int>& arr, int low, int high){
if(low<high){
int baseIndex = partition(arr, low, high);
quickSort(arr, low, baseIndex-1);
quickSort(arr, baseIndex+1, high);
}
}
int main() {
std::vector<int> arr = {90, 34, 25, 12, 22, 11, 64};
int n = arr.size();
quickSort(arr, 0, n - 1);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
partition函数：选择一个基准元素（通常是数组的最后一个元素），将数组分为两部分，左边的元素都小于基准元素，右边的元素都大于基准元素。 quickSort函数：递归地对划分后的子数组进行排序。 main函数：在main函数中，我们创建了一个包含一些整数的向量，并调用quickSort函数对其进行排序。最后，我们输出排序后的数组。
首次调用的结果：
快速排序的优点
- 高效性：快速排序的平均时间复杂度为O(n log n)，在大多数情况下比其他排序算法（如冒泡排序、插入排序等）更快。
- 原地排序：快速排序是一种原地排序算法，它不需要额外的存储空间来存储临时数据。
- 适应性：快速排序可以根据数据的分布情况进行自适应调整，对于已经部分有序的数据也能表现出较好的性能。
快速排序的缺点
- 不稳定性：快速排序是一种不稳定的排序算法，即相等元素的相对顺序在排序后可能会改变。
- 最坏情况性能：在最坏情况下，快速排序的时间复杂度为O(n^2)，这种情况发生在数组已经有序或接近有序时。
- 递归深度：快速排序是一种递归算法，在处理大规模数据时，可能会导致栈溢出的问题。
快速排序是一种高效的排序算法，适用于大规模数据的排序。然而，在最坏情况下，快速排序的性能可能会受到影响，因此在实际应用中，通常会使用更稳定的排序算法，如归并排序。
归并排序
归并排序（Merge Sort）是一种分治算法，它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将它们合并成一个有序的数组。归并排序的基本思想是将数组分成两半，对每一半进行排序，然后将排序好的两半合并起来。
#include <iostream>
#include <vector>
// 归并函数，将两个有序的子数组合并成一个有序的数组
void merge(std::vector<int>& arr, int left, int mid, int right){
int leftSize = mid-left+1;
int rightSize = right-mid;
std::vector<int> leftArr(leftSize);
std::vector<int> rightArr(rightSize);
// 将左右两个子数组分别复制到临时数组中
for(int i=0;i<leftSize;i++){
leftArr[i] = arr[left+i];
}
for(int j=0;j<rightSize;j++){
rightArr[j] = arr[mid+1+j];
}
// 合并两个有序的子数组
int i=0;
int j=0;
int k=left;
while(i<leftSize && j<rightSize){
if(leftArr[i]<=rightArr[j]){
arr[k] = leftArr[i];
i++;
}else{
arr[k] = rightArr[j];
j++;
}
k++;
}
// 将剩余的元素复制到数组中
while(i<leftSize){
arr[k] = leftArr[i];
i++;
k++;
}
while(j<rightSize){
arr[k] = rightArr[j];
j++;
k++;
}
}
// 递归归并排序，只要目标区域包含两个及以上的元素，就继续排序
void mergeSort(std::vector<int>& arr, int left, int right){
if(left<right){
int mid = left + (right-left)/2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {90, 34, 25, 12, 22, 11, 64};
int n = arr.size();
mergeSort(arr, 0, n - 1);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
归并排序的优点
- 稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序后不会改变。
- 高效性：归并排序的平均时间复杂度为O(n log n)，在大多数情况下比其他排序算法（如冒泡排序、插入排序等）更快。
- 适应性：归并排序可以根据数据的分布情况进行自适应调整，对于已经部分有序的数据也能表现出较好的性能。
归并排序的缺点
- 空间开销：归并排序需要额外的空间来存储临时数据，这可能会导致空间开销较大。
- 递归深度：归并排序是一种递归算法，在处理大规模数据时，可能会导致栈溢出的问题。
归并排序是一种高效的排序算法，适用于小规模数据的排序。然而，在空间开销和递归深度方面，归并排序可能会受到限制。
选择排序
选择排序是一种简单直观的排序算法，它的工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置（末尾），然后再从剩余未排序元素中继续寻找，换位。以此类推，直到全部待排序的数据元素排完。
#include <iostream>
#include <vector>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11, 90};
selectionSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
选择排序的优点
- 简单易懂：选择排序的实现非常简单，易于理解和实现，适合初学者学习排序算法的基本概念。
选择排序的缺点
- 效率较低：选择排序的时间复杂度为O(n^2)，其中n是要排序的元素数量。这意味着当处理大量数据时，选择排序的效率会非常低。
选择排序是一种简单但效率较低的排序算法，适用于小规模数据的排序或作为学习排序算法的入门示例。
堆排序
堆排序是一种高效的排序算法，它基于堆数据结构来实现。堆排序的基本思想是将待排序的数组构建成一个最大堆（或最小堆），然后将堆顶元素（最大或最小）与堆的最后一个元素交换，然后将堆的大小减1，再调整堆，重复上述过程，直到堆的大小为1。
#include <iostream>
#include <vector>
// 调整堆，将以index为根节点的子树调整为最大堆
void heapify(std::vector<int>& arr, int n, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != index) {
std::swap(arr[index], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; --i) {
heapify(arr, n, i);
}
// 依次取出堆顶元素，并调整堆
for (int i = n - 1; i >= 0; --i) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11, 90};
heapSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
堆排序的优点
- 高效性：堆排序的平均时间复杂度为O(n log n)，在大多数情况下比其他排序算法（如冒泡排序、插入排序等）更快。
堆排序的缺点
- 不稳定性：堆排序是一种不稳定的排序算法，即相等元素的相对顺序在排序后可能会改变。
堆排序是一种高效的排序算法，适用于大规模数据的排序。然而，在最坏情况下，堆排序的性能可能会受到影响。
希尔排序
希尔排序是一种高效的排序算法，它基于插入排序的思想来实现。希尔排序的基本思想是将待排序的数组分成若干个子序列，对每个子序列进行插入排序，然后逐渐缩小子序列的间隔，直到间隔为1时，对整个数组进行一次插入排序。
#include <iostream>
#include <vector>
void shellSort(std::vector<int>& arr) {
int n = arr.size();
// 初始间隔为数组长度的一半
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个子序列进行插入排序
for (int i = gap; i < n; ++i) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11, 90};
shellSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
希尔排序的优点
- 效率较高：希尔排序的时间复杂度优于普通的插入排序（O(n²)），尤其是在中等规模的数据集上表现较好。其时间复杂度通常在O(n log² n)到O(n²)之间，具体取决于步长序列的选择。
- 原地排序：希尔排序不需要额外的存储空间，是一种原地排序算法。
- 简单易实现：希尔排序的实现相对简单，尤其是对于已经熟悉插入排序的开发者来说。
- 适用于中等规模数据：对于中等规模的数据集，希尔排序的性能通常优于冒泡排序和选择排序等简单排序算法。
希尔排序的缺点
- 时间复杂度不稳定：希尔排序的时间复杂度依赖于步长序列的选择，最坏情况下可能退化为O(n²)，无法保证在所有情况下都表现良好。
- 不适合大规模数据：对于大规模数据集，希尔排序的效率不如快速排序、归并排序或堆排序等更高效的算法。
- 步长序列选择复杂：步长序列的选择对希尔排序的性能影响很大，但如何选择最优的步长序列仍然是一个研究课题，没有统一的标准。
适用场景：
- 中等规模的数据集。
- 对内存使用有严格限制的场景（因为它是原地排序）。
- 作为其他更复杂排序算法的初步优化步骤。
希尔排序是一种简单且有效的排序算法，尤其适用于中等规模的数据集。虽然它在最坏情况下的时间复杂度较高，但通过选择合适的步长序列，可以在实际应用中取得较好的性能。对于大规模数据集，更高效的排序算法（如快速排序或归并排序）通常是更好的选择。
计数排序
计数排序是一种非比较排序算法，它的基本思想是利用数组的下标来确定元素的正确位置。计数排序的步骤如下：
- 找出待排序数组中的最大值和最小值。
- 创建一个计数数组，数组的大小为最大值减去最小值加1。
- 遍历待排序数组，将每个元素出现的次数记录在计数数组中。
- 对计数数组进行累加，得到每个元素在排序后的数组中的正确位置。
- 遍历待排序数组，根据计数数组将元素放置到正确的位置上。
#include <iostream>
#include <vector>
void countingSort(std::vector<int>& arr) {
int n = arr.size();
if (n <= 1) {
return;
}
// 找出最大值和最小值
int maxVal = arr[0];
int minVal = arr[0];
for (int i = 1; i < n; ++i) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
if (arr[i] < minVal) {
minVal = arr[i];
}
}
// 创建计数数组
int range = maxVal - minVal + 1;
std::vector<int> count(range, 0);
// 统计每个元素出现的次数
for (int i = 0; i < n; ++i) {
count[arr[i] - minVal]++;
}
// 对计数数组进行累加，得到每个元素在排序后的数组中的正确位置
for (int i = 1; i < range; ++i) {
count[i] += count[i - 1];
}
// 遍历待排序数组，将元素放置到正确的位置上
std::vector<int> sortedArr(n);
for (int i = n - 1; i >= 0; --i) {
sortedArr[count[arr[i] - minVal] - 1] = arr[i];
count[arr[i] - minVal]--;
}
// 将排序后的数组复制回原数组
for (int i = 0; i < n; ++i) {
arr[i] = sortedArr[i];
}
}
int main() {
std::vector<int> arr = {64, 25, 12, 22, 11, 90};
countingSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
计数排序的优点
- 高效性：计数排序的时间复杂度为O(n + k)，其中n是待排序数组的长度，k是待排序数组中元素的范围。当k不是很大时，计数排序的性能非常好。
- 稳定性：计数排序是一种稳定的排序算法，即相等元素的相对顺序在排序后不会改变。
计数排序的缺点
- 空间开销：计数排序需要额外的空间来存储计数数组，其空间复杂度为O(k)，其中k是待排序数组中元素的范围。当k很大时，计数排序的空间开销可能会很大。
计数排序是一种简单且高效的排序算法，尤其适用于待排序数组中元素的范围较小的情况。它的时间复杂度为O(n + k)，其中n是待排序数组的长度，k是待排序数组中元素的范围。当k不是很大时，计数排序的性能非常好。然而，计数排序的空间开销可能会很大，特别是当k很大时。
横向比较
下面是这八种排序算法时间复杂度和空间复杂度的横向比较：
查找算法
基本查找
基本查找（Linear Search）是一种简单的查找算法，它的基本思想是遍历数组，逐个比较数组元素与目标元素是否相等。如果找到相等的元素，则返回其索引；如果遍历完整个数组都没有找到相等的元素，则返回-1。
#include <iostream>
#include <vector>
// 基本查找函数
int linearSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
for (int i = 0; i < n; ++i) {
if (arr[i] == target) {
return i; // 找到目标元素，返回索引
}
}
return -1; // 目标元素不存在
}
int main() {
std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = linearSearch(arr, target);
if (result != -1) {
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
} else {
std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
}
return 0;
}
基本查找的优点
- 简单易懂：基本查找的实现非常简单，易于理解和实现，适合初学者学习查找算法的基本概念。
基本查找的缺点
- 效率较低：基本查找的时间复杂度为O(n)，其中n是数组的长度。这意味着当数组的长度较大时，基本查找的效率会非常低。
基本查找是一种简单的查找算法，适用于小规模数据的查找或作为学习查找算法的入门示例。在实际应用中，对于大规模数据的查找，通常会使用更高效的查找算法，如二分查找、哈希查找等。
二分查找
二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两部分，然后比较目标元素与中间元素的大小，如果目标元素小于中间元素，则在左半部分继续查找，否则在右半部分继续查找。重复这个过程，直到找到目标元素或者确定目标元素不存在。
#include <iostream>
#include <vector>
// 二分查找函数
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 找到目标元素，返回索引
} else if (arr[mid] < target) {
left = mid + 1; // 目标元素在右半部分
} else {
right = mid - 1; // 目标元素在左半部分
}
}
return -1; // 目标元素不存在
}
int main() {
std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = binarySearch(arr, target);
if (result != -1) {
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
} else {
std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
}
return 0;
}
binarySearch函数：实现了二分查找算法。它接受一个有序数组和一个目标元素作为参数，并返回目标元素在数组中的索引，如果目标元素不存在，则返回-1。 main函数：在main函数中，我们创建了一个有序数组，并调用binarySearch函数查找目标元素。最后，根据返回结果输出相应的信息。
二分查找的优点
- 高效性：二分查找的时间复杂度为O(log n)，其中n是数组的长度。这使得它在处理大规模数据时非常高效。
- 简单易懂：二分查找的实现相对简单，易于理解和实现。
二分查找的缺点
- 要求有序：二分查找要求数组必须是有序的，如果数组无序，则需要先进行排序，这会增加时间复杂度。
- 不适合动态数据：如果数组中的元素经常发生变化，那么每次查找前都需要重新排序，这会导致效率低下。
二分查找是一种高效的查找算法，适用于有序数组。它的时间复杂度为O(log n)，在处理大规模数据时非常高效。然而，它要求数组必须是有序的，并且不适合动态数据。
插值查找
插值查找（Interpolation Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是根据目标元素与数组中元素的大小关系，通过 插值公式 来确定目标元素可能存在的位置，然后在该位置附近进行查找。
#include <iostream>
#include <vector>
// 插值查找函数
int interpolationSearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right && target >= arr[left] && target <= arr[right]) {
if (left == right) {
if (arr[left] == target) {
return left; // 找到目标元素，返回索引
}
return -1; // 目标元素不存在
}
// 计算目标元素可能存在的位置
int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);
if (arr[pos] == target) {
return pos; // 找到目标元素，返回索引
} else if (arr[pos] < target) {
left = pos + 1; // 目标元素在右半部分
} else {
right = pos - 1; // 目标元素在左半部分
}
}
return -1; // 目标元素不存在
}
int main() {
std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = interpolationSearch(arr, target);
if (result!= -1) {
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
} else {
std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
}
return 0;
}
插值查找的优点
- 高效性：插值查找的时间复杂度为O(log log n)，其中n是数组的长度。这使得它在处理大规模数据时非常高效。
- 适用于均匀分布的数据：插值查找适用于均匀分布的数据，因为它根据目标元素与数组中元素的大小关系来确定目标元素可能存在的位置，从而提高了查找效率。
插值查找的缺点
- 要求有序：插值查找要求数组必须是有序的，如果数组无序，则需要先进行排序，这会增加时间复杂度。
插值查找是一种高效的查找算法，适用于有序数组。它的时间复杂度为O(log log n)，在处理大规模数据时非常高效。然而，它要求数组必须是有序的，并且不适合动态数据。
斐波那契查找
斐波那契查找（Fibonacci Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是利用斐波那契数列来确定目标元素可能存在的位置，然后在该位置附近进行查找。
#include <iostream>
#include <vector>
// 斐波那契查找函数
int fibonacciSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
int fib2 = 0; // （Fibonacci(n)-1）
int fib1 = 1; // Fibonacci(n)
int fib = fib2 + fib1;
// 找到大于等于数组长度的最小斐波那契数
while (fib < n) {
fib2 = fib1;
fib1 = fib;
fib = fib2 + fib1;
}
int offset = -1;
while (fib > 1) {
int i = std::min(offset + fib2, n - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i; // 找到目标元素，返回索引
}
}
if (fib1 && arr[offset + 1] == target) {
return offset + 1; // 找到目标元素，返回索引
}
return -1; // 目标元素不存在
}
int main() {
std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = fibonacciSearch(arr, target);
if (result!= -1) {
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
} else {
std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
}
return 0;
}
斐波那契查找的优点
- 高效性：斐波那契查找的时间复杂度为O(log n)，其中n是数组的长度。这使得它在处理大规模数据时非常高效。
斐波那契查找的缺点
- 要求有序：斐波那契查找要求数组必须是有序的，如果数组无序，则需要先进行排序，这会增加时间复杂度。
斐波那契查找是一种高效的查找算法，适用于有序数组。它的时间复杂度为O(log n)，在处理大规模数据时非常高效。然而，它要求数组必须是有序的，并且不适合动态数据。
分块查找
分块查找（Block Search）是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成若干个块，每个块内部有序，但块之间无序。然后根据目标元素与块的边界值进行比较，确定目标元素可能存在的块，然后在该块内进行查找。
#include <iostream>
#include <vector>
// 分块查找函数
int blockSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
int blockSize = std::sqrt(n); // 块的大小
int numBlocks = (n + blockSize - 1) / blockSize; // 块的数量
std::vector<int> blockMax(numBlocks); // 存储每个块的最大值
// 找到每个块的最大值
for (int i = 0; i < numBlocks; ++i) {
int blockStart = i * blockSize;
int blockEnd = std::min((i + 1) * blockSize, n);
blockMax[i] = arr[blockStart];
for (int j = blockStart + 1; j < blockEnd; ++j) {
if (arr[j] > blockMax[i]) {
blockMax[i] = arr[j];
}
}
}
// 确定目标元素可能存在的块
int blockIndex = 0;
while (blockIndex < numBlocks && target > blockMax[blockIndex]) {
++blockIndex;
}
// 在目标块内进行查找
int blockStart = blockIndex * blockSize;
int blockEnd = std::min((blockIndex + 1) * blockSize, n);
for (int i = blockStart; i < blockEnd; ++i) {
if (arr[i] == target) {
return i; // 找到目标元素，返回索引
}
}
return -1; // 目标元素不存在
}
int main() {
std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = blockSearch(arr, target);
if (result!= -1) {
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
} else {
std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
}
return 0;
}
分块查找的优点
- 高效性：分块查找的时间复杂度为O(sqrt(n))，其中n是数组的长度。这使得它在处理大规模数据时非常高效。
分块查找的缺点
- 要求有序：分块查找要求数组必须是有序的，如果数组无序，则需要先进行排序，这会增加时间复杂度。
分块查找是一种高效的查找算法，适用于有序数组。它的时间复杂度为O(sqrt(n))，在处理大规模数据时非常高效。然而，它要求数组必须是有序的，并且不适合动态数据。
哈希查找
哈希查找（Hash Search）是一种在无序数组中查找特定元素的搜索算法。它的基本思想是利用哈希函数将数组中的元素映射到一个哈希表中，然后根据目标元素的哈希值在哈希表中查找。
#include <iostream>
#include <vector>
// 哈希查找函数
int hashSearch(const std::vector<int>& arr, int target) {
int n = arr.size();
std::vector<int> hashTable(n, -1); // 哈希表，初始化为-1
// 将数组中的元素映射到哈希表中
for (int i = 0; i < n; ++i) {
int hashValue = arr[i] % n;
while (hashTable[hashValue] != -1) {
++hashValue;
hashValue %= n;
}
hashTable[hashValue] = arr[i];
}
// 根据目标元素的哈希值在哈希表中查找
int hashValue = target % n;
while (hashTable[hashValue]!= -1 && hashTable[hashValue]!= target) {
++hashValue;
hashValue %= n;
}
if (hashTable[hashValue] == target) {
return hashValue; // 找到目标元素，返回索引
}
return -1; // 目标元素不存在
}
int main() {
std::vector<int> arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = hashSearch(arr, target);
if (result!= -1) {
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
} else {
std::cout << "目标元素 " << target << " 不在数组中" << std::endl;
}
return 0;
}
哈希查找的优点
- 高效性：平均时间复杂度为O(1)：在理想情况下，哈希查找的时间复杂度接近常数时间，适合处理大规模数据。
- 快速插入和删除：哈希表不仅查找快，插入和删除操作也非常高效。
- 灵活性：支持多种数据类型：哈希函数可以处理不同类型的数据，如字符串、整数等。
- 动态扩展：哈希表可以根据需求动态调整大小，保持高效性能。
- 广泛应用：数据库索引：常用于数据库中的索引结构，加速数据检索。缓存系统：如Redis、Memcached等缓存系统依赖哈希表实现快速数据访问。编译器符号表：用于管理变量和函数名。
哈希查找的缺点
- 哈希冲突：冲突不可避免：不同键可能映射到同一位置，需通过链地址法或开放地址法解决，增加了复杂度。
- 性能下降：冲突过多时，查找时间可能退化为O(n)。
- 空间消耗：空间利用率低：为避免冲突，哈希表通常需要较大的空间，导致空间浪费。负载因子影响：负载因子过高时，冲突增加；过低时，空间浪费。
- 哈希函数设计复杂：设计难度：好的哈希函数需均匀分布键，减少冲突，设计较为复杂。依赖哈希函数：性能高度依赖哈希函数的质量。
- 不支持有序操作：无法直接排序：哈希表中的数据无序，无法直接进行范围查询或排序操作。
哈希查找在平均情况下非常高效，适合需要快速查找、插入和删除的场景。然而，哈希冲突、空间消耗和哈希函数设计的复杂性是其主要缺点。在有序操作或内存有限的情况下，可能需要考虑其他数据结构。
二叉树查找
二叉树查找（Binary Tree Search）是一种在二叉搜索树中查找特定元素的搜索算法。又指二叉搜索树（BST, Binary Search Tree）。它的核心特点是每个节点的左子树包含小于该节点的值，右子树包含大于该节点的值。
#include <iostream>
using namespace std;
// 定义二叉树节点结构
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 插入节点
TreeNode* insert(TreeNode* root, int key) {
if (root == nullptr) {
return new TreeNode(key); // 如果树为空，创建新节点
}
if (key < root->val) {
root->left = insert(root->left, key); // 递归插入左子树
} else if (key > root->val) {
root->right = insert(root->right, key); // 递归插入右子树
}
return root;
}
// 查找节点
TreeNode* search(TreeNode* root, int key) {
if (root == nullptr || root->val == key) {
return root; // 找到节点或树为空
}
if (key < root->val) {
return search(root->left, key); // 递归查找左子树
} else {
return search(root->right, key); // 递归查找右子树
}
}
// 中序遍历（用于验证树的结构）
void inorderTraversal(TreeNode* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
TreeNode* root = nullptr;
// 插入节点
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// 中序遍历输出
cout << "Inorder Traversal: ";
inorderTraversal(root);
cout << endl;
// 查找节点
int key = 60;
TreeNode* result = search(root, key);
if (result != nullptr) {
cout << "Node " << key << " found in the tree." << endl;
} else {
cout << "Node " << key << " not found in the tree." << endl;
}
// 查找不存在的节点
key = 90;
result = search(root, key);
if (result != nullptr) {
cout << "Node " << key << " found in the tree." << endl;
} else {
cout << "Node " << key << " not found in the tree." << endl;
}
return 0;
}
二叉树查找的优点
- 查找效率较高：平均时间复杂度为O(log n)：在平衡的二叉搜索树中，查找、插入和删除操作的时间复杂度为O(log n)，适合中等规模的数据。
- 支持动态操作：插入和删除操作相对高效，适合需要频繁更新的数据集。
- 有序性：支持范围查询：由于二叉搜索树的中序遍历是有序的，因此可以高效地支持范围查询（如查找某个区间内的所有值）。支持排序操作：通过中序遍历可以直接得到有序数据。
- 结构简单：易于实现：二叉搜索树的基本操作（查找、插入、删除）实现相对简单，适合教学和基础应用。
- 扩展性强：可扩展为高级数据结构：二叉搜索树可以扩展为更高效的数据结构，如AVL树、红黑树、B树等，以解决平衡性问题。
缺点：
- 平衡性问题：最坏时间复杂度为O(n)：如果树不平衡（例如退化为链表），查找、插入和删除的时间复杂度会退化为O(n)。
- 需要额外维护平衡：为了保持高效性，需要使用平衡二叉树（如AVL树或红黑树），增加了实现复杂度。
- 空间开销：每个节点需要额外存储指针：二叉树需要存储左右子节点的指针，空间开销较大，尤其是在存储大量小数据时。
- 不适合大规模数据：性能受限：对于大规模数据，二叉树的深度会增加，导致查找效率下降。相比之下，哈希表或B树更适合大规模数据。
- 动态操作可能导致性能波动：频繁插入和删除可能破坏平衡：在普通二叉搜索树中，频繁的插入和删除操作可能导致树结构失衡，影响性能。
二叉树查找在数据有序性和动态操作方面表现良好，适合中等规模且需要频繁更新和范围查询的场景。然而，其性能高度依赖于树的平衡性，普通二叉搜索树在极端情况下可能退化为链表，导致性能下降。因此，在实际应用中，通常使用平衡二叉树（如AVL树或红黑树）来保证性能稳定性。对于大规模数据或需要更高性能的场景，可能需要考虑其他数据结构（如B树或哈希表）。
