【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（一）https://developer.aliyun.com/article/1467831
第三部分：二叉树操作
3.1 二叉链表存储结构
二叉链表（Binary Linked List）是一种特殊的链表结构，用于表示二叉树（Binary Trees）。在这种结构中，每个节点都有两个指针：一个指向其左子节点（Left Child），另一个指向其右子节点（Right Child）。
3.1.1 二叉树的建立
建立二叉树是第一步，通常有多种方法可以实现，比如通过数组、通过递归方法或者通过用户输入等。在C++中，我们可以定义一个结构来表示二叉树的节点：
struct TreeNode { int value; TreeNode *left; TreeNode *right; };
例如，我们可以通过递归方法来实现二叉树的建立。假设我们有一个数组，该数组通过某种遍历算法（通常是先序或中序遍历）表示了二叉树：
int arr[] = {1, 2, 3, 4, 5, 6, 7};
我们可以通过以下递归函数来从这个数组中建立二叉树：
TreeNode* buildTree(int arr[], int start, int end) { if (start > end) return nullptr; int mid = (start + end) / 2; TreeNode* node = new TreeNode(); node->value = arr[mid]; node->left = buildTree(arr, start, mid - 1); node->right = buildTree(arr, mid + 1, end); return node; }
3.1.2 先序、中序和后序遍历
一旦我们建立了二叉树，下一步是学习如何遍历它。遍历二叉树有多种方法，但最常见的是先序（Pre-order）、中序（In-order）和后序（Post-order）遍历。
- 先序遍历：在先序遍历中，我们先访问根节点，然后递归地遍历左子树，最后遍历右子树。
- 中序遍历：在中序遍历中，我们首先递归地遍历左子树，然后访问根节点，最后遍历右子树。
- 后序遍历：在后序遍历中，我们首先递归地遍历左子树，然后遍历右子树，最后访问根节点。
3.1.3 按层次遍历
除了先序、中序和后序遍历外，还有一种常用的遍历方法，即按层次遍历（Level-order Traversal）或广度优先搜索（Breadth-First Search, BFS）。在这种遍历方法中，我们首先访问根节点，然后依次访问所有的子节点，再访问子节点的子节点，依此类推。
在C++中，我们可以使用队列（Queue）数据结构来实现按层次遍历。每次从队列中取出一个节点，并将其子节点（如果有的话）加入到队列中。
3.1.4 求所有叶子和结点个数
求二叉树的所有叶子节点（Leaf Nodes）和总节点数（Total Nodes）是二叉树操作中的常见任务。这两个任务都可以通过递归来简单实现。
- 求所有叶子节点：遍历整个二叉树，每当遇到一个没有左子节点和右子节点的节点时，就认为它是一个叶子节点。
- 求总节点数：遍历整个二叉树，每访问一个节点就将计数器加一。
这些基础操作为我们提供了处理二叉树的强大工具，接下来的章节中，我们将进一步探讨如何利用这些工具来解决实际问题。希望这些内容能够帮助你更好地理解二叉树和其相关操作。
3.1.5 示例代码与注意事项
在进行二叉树的操作时，有几点需要特别注意：
- 内存管理：在C++中，当你使用
new操作符创建新的节点时，务必记得在不再需要这些节点时使用delete操作符释放内存。 - 边界条件：在进行递归操作时，如遍历或构建树，务必考虑边界条件。例如，在构建树的递归函数中，当
start > end时，应返回nullptr。 - 复杂度分析：了解每个操作（如遍历、查找、插入、删除等）的时间复杂度和空间复杂度是非常重要的，这会影响到你代码的性能。
- 代码可读性：为变量和函数选择有意义的名称，并添加必要的注释，这不仅有助于他人理解你的代码，也有助于你自己在未来更容易地理解和维护代码。
下面是一些在C++中进行二叉树操作的示例代码：
创建二叉树
TreeNode* buildTree(int arr[], int start, int end) { if (start > end) return nullptr; int mid = (start + end) / 2; TreeNode* node = new TreeNode(); node->value = arr[mid]; node->left = buildTree(arr, start, mid - 1); node->right = buildTree(arr, mid + 1, end); return node; }
先序遍历
void preOrder(TreeNode* root) { if (root == nullptr) return; cout << root->value << " "; preOrder(root->left); preOrder(root->right); }
按层次遍历
void levelOrder(TreeNode* root) { if (root == nullptr) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); cout << current->value << " "; if (current->left != nullptr) q.push(current->left); if (current->right != nullptr) q.push(current->right); } }
求所有叶子节点和总节点数
int countLeaves(TreeNode* root) { if (root == nullptr) return 0; if (root->left == nullptr && root->right == nullptr) return 1; return countLeaves(root->left) + countLeaves(root->right); } int countNodes(TreeNode* root) { if (root == nullptr) return 0; return 1 + countNodes(root->left) + countNodes(root->right); }
通过以上的示例代码和注意事项，希望你能够更加深入地理解二叉树和其相关操作，在实际应用或考试中能更加得心应手。
第四部分：图的遍历操作
4.1 邻接矩阵与邻接表
图（Graph）在计算机科学中有着广泛的应用，包括但不限于社交网络分析、地图路由和网络设计等。在本节中，我们将重点介绍图的两种常用存储结构——邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）——以及如何使用这两种结构完成有向图（Directed Graph）和无向图（Undirected Graph）的深度优先搜索（DFS）和广度优先搜索（BFS）。
4.1.1 有向图的DFS
深度优先搜索（DFS, Depth-First Search）是一种用于遍历或搜索树或图的算法。在有向图中，DFS从一个初始节点（或多个初始节点）开始，尽可能沿着图的分支前进，直到找不到未访问过的节点为止，然后回溯。
使用邻接矩阵实现DFS
如果使用邻接矩阵来存储图，DFS可以用以下的C++代码来实现：
void DFS_Matrix(int vertex, bool visited[], int **adjMatrix, int numVertices) { visited[vertex] = true; std::cout << vertex << " "; for (int i = 0; i < numVertices; i++) { if (adjMatrix[vertex][i] == 1 && !visited[i]) { DFS_Matrix(i, visited, adjMatrix, numVertices); } } }
使用邻接表实现DFS
如果使用邻接表来存储图，DFS的实现会稍有不同：
void DFS_List(int vertex, bool visited[], std::vector<std::vector<int>> &adjList) { visited[vertex] = true; std::cout << vertex << " "; for (int i : adjList[vertex]) { if (!visited[i]) { DFS_List(i, visited, adjList); } } }
4.1.2 无向图的DFS
在无向图中，DFS的基本思想和在有向图中基本相同，但由于无向图的边没有方向，因此在实现上会有些许不同。
使用邻接矩阵实现DFS
在无向图中，邻接矩阵是对称的。DFS的C++实现代码与有向图基本相同，只是邻接矩阵会有所不同。
使用邻接表实现DFS
在无向图中使用邻接表进行DFS的代码实现与有向图也非常相似，关键是在构建邻接表时需要注意图的无向性。
4.1.3 有向图和无向图的BFS
广度优先搜索（BFS, Breadth-First Search）是另一种用于遍历或搜索树和图的重要算法。与DFS不同，BFS是层次遍历，从根节点开始，然后是所有相邻的节点，然后是这些节点的相邻节点，以此类推。
使用邻接矩阵实现BFS
下面是使用邻接矩阵实现BFS的C++代码：
void BFS_Matrix(int startVertex, int **adjMatrix, int numVertices) { std::queue<int> q; bool visited[numVertices]; memset(visited, false, sizeof(visited)); visited[startVertex] = true; q.push(startVertex); while (!q.empty()) { int currentVertex = q.front(); std::cout << currentVertex << " "; q.pop(); for (int i = 0; i < numVertices; i++) { if (adjMatrix[currentVertex][i] == 1 && !visited[i]) { q.push(i); visited[i] = true; } } } }
使用邻接表实现BFS
使用邻接表进行BFS的C++代码如下：
void BFS_List(int startVertex, std::vector<std::vector<int>> &adjList) { std::queue<int> q; std::vector<bool> visited(adjList.size(), false); visited[startVertex] = true; q.push(startVertex); while (!q.empty()) { int currentVertex = q.front(); std::cout << currentVertex << " "; q.pop(); for (int i : adjList[currentVertex]) { if (!visited[i]) { q.push(i); visited[i] = true; } } } }
以上代码片段展示了如何使用邻接矩阵和邻接表来实现有向图和无向图的DFS和BFS。在接下来的章节中，我们将进一步讨论这些代码的优缺点以及使用场景。希望这些信息能帮助你更好地掌握图的遍历操作。
4.1.4 示例代码与注意事项
在实现图的DFS和BFS时，有几点需要特别注意：
- 初始化访问数组：无论是DFS还是BFS，都需要一个
visited数组（或向量）来跟踪哪些节点已经被访问过。这个数组应在算法开始前初始化为false。 - 选择合适的数据结构：邻接矩阵更适用于稠密图（Dense Graphs），而邻接表更适用于稀疏图（Sparse Graphs）。选择哪种结构取决于你的具体应用。
- 处理连通分量：在非连通图（Disconnected Graphs）中，你可能需要从多个节点开始遍历，以确保访问图中的所有节点。
C++完整示例代码
下面是一个使用邻接矩阵和邻接表实现DFS和BFS的完整C++示例代码：
#include <iostream> #include <vector> #include <queue> #include <cstring> // DFS using adjacency matrix void DFS_Matrix(int vertex, bool visited[], int **adjMatrix, int numVertices) { visited[vertex] = true; std::cout << vertex << " "; for (int i = 0; i < numVertices; i++) { if (adjMatrix[vertex][i] == 1 && !visited[i]) { DFS_Matrix(i, visited, adjMatrix, numVertices); } } } // DFS using adjacency list void DFS_List(int vertex, bool visited[], std::vector<std::vector<int>> &adjList) { visited[vertex] = true; std::cout << vertex << " "; for (int i : adjList[vertex]) { if (!visited[i]) { DFS_List(i, visited, adjList); } } } // BFS using adjacency matrix void BFS_Matrix(int startVertex, int **adjMatrix, int numVertices) { std::queue<int> q; bool visited[numVertices]; memset(visited, false, sizeof(visited)); visited[startVertex] = true; q.push(startVertex); while (!q.empty()) { int currentVertex = q.front(); std::cout << currentVertex << " "; q.pop(); for (int i = 0; i < numVertices; i++) { if (adjMatrix[currentVertex][i] == 1 && !visited[i]) { q.push(i); visited[i] = true; } } } } // BFS using adjacency list void BFS_List(int startVertex, std::vector<std::vector<int>> &adjList) { std::queue<int> q; std::vector<bool> visited(adjList.size(), false); visited[startVertex] = true; q.push(startVertex); while (!q.empty()) { int currentVertex = q.front(); std::cout << currentVertex << " "; q.pop(); for (int i : adjList[currentVertex]) { if (!visited[i]) { q.push(i); visited[i] = true; } } } } int main() { // TODO: Initialize adjacency matrix and adjacency list // TODO: Call DFS_Matrix, DFS_List, BFS_Matrix, BFS_List functions return 0; }
这个示例代码提供了一个基础框架，你可以根据自己的需要进行相应的调整和扩展。希望这些代码和注意事项能帮助你更深入地理解图的遍历操作。
第五部分：数据查找
5.1 顺序查找
5.1.1 顺序查找（Sequential Search）概述
顺序查找（Sequential Search）是最基础的查找算法之一。这种算法在数组或列表中从第一个元素开始，逐一比较直至找到目标元素或达到数据结构的末尾。因为这种查找方式不依赖于数据结构的特定排列方式，因此它可以应用于任何类型的数据结构。
顺序查找的主要优点是实现简单，但缺点是效率相对较低，特别是在数据量大的情况下。时间复杂度在最坏的情况下是 (O(n))。
5.1.2 C++实现示例
接下来我们将展示一个使用C++实现的顺序查找示例。假设我们有一个整数数组，并且需要找到特定的目标整数。
#include <iostream> #include <vector> // 顺序查找函数 int sequentialSearch(const std::vector<int>& arr, int target) { for (int i = 0; i < arr.size(); ++i) { if (arr[i] == target) { return i; // 返回目标元素的索引 } } return -1; // 如果没有找到目标元素，则返回-1 } int main() { std::vector<int> arr = {10, 20, 30, 40, 50}; int target = 30; int result = sequentialSearch(arr, target); if (result != -1) { std::cout << "Element found at index: " << result << std::endl; } else { std::cout << "Element not found" << std::endl; } return 0; }
在这个示例中，我们定义了一个名为 sequentialSearch 的函数，该函数接受一个整数数组和一个目标整数作为参数。函数通过遍历数组并比较每个元素与目标元素来执行查找。如果找到目标元素，函数会返回其在数组中的索引；否则，返回-1。
5.1.3 注意事项和优化
虽然顺序查找是一个相对简单和直接的算法，但在实际应用中还是有几点需要注意：
- 数据大小：由于顺序查找的时间复杂度为 (O(n))，在数据集非常大时可能会导致效率低下。
- 多次查找：如果你需要对相同的数据集进行多次查找，可能需要考虑使用更高效的查找算法或数据结构（如哈希表、二分查找树等）。
- 数据类型：这个算法不仅仅适用于整数，也可以轻易地扩展到其他数据类型，包括字符串、自定义对象等。
总的来说，顺序查找是一种非常基础但也非常有用的查找算法，特别适用于数据量小或不需要频繁查找的场景。如果你发现顺序查找不能满足你的需求，那么接下来的章节将介绍一些更高效的查找算法。
5.2 折半查找
5.2.1 折半查找（Binary Search）概述
折半查找，也被称为二分查找（Binary Search），是一种在排序数组中查找特定元素的算法。与顺序查找相比，折半查找的效率更高，时间复杂度为 (O(\log n))。
该算法工作原理如下：
- 选择数组中间的元素。
- 如果选中的元素等于目标值，则查找成功。
- 如果选中的元素大于目标值，则在数组的左半部分继续查找。
- 如果选中的元素小于目标值，则在数组的右半部分继续查找。
- 重复上述步骤，直到找到目标元素或者搜索范围为空。
需要注意的是，折半查找只适用于已排序的数组。
5.2.2 C++实现示例
下面是一个使用C++实现的折半查找示例：
#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; // 如果没有找到目标元素，则返回-1 } int main() { std::vector<int> arr = {10, 20, 30, 40, 50}; int target = 30; int result = binarySearch(arr, target); if (result != -1) { std::cout << "Element found at index: " << result << std::endl; } else { std::cout << "Element not found" << std::endl; } return 0; }
在这个示例中，我们定义了一个名为 binarySearch 的函数，该函数接受一个排序好的整数数组和一个目标整数作为参数。函数用两个指针 left 和 right 来追踪待搜索的数组范围，并通过不断缩小这个范围来找到目标元素。
5.2.3 注意事项和优化
- 已排序的数据：折半查找要求数据集必须是预先排序的。如果你的数据集没有排序，那么你需要先进行排序，这会增加额外的时间复杂度。
- 返回值：如果有多个相同的目标元素，该算法通常返回第一个找到的元素的位置。如果你需要找到所有出现的位置，那么你需要对算法进行额外的修改。
- 递归与迭代：折半查找可以通过递归或迭代的方式来实现。上面的示例代码使用的是迭代方法。
- 数据类型：和顺序查找一样，折半查找也可以应用于除整数之外的其他数据类型，只要这些数据类型可以进行有效的比较和排序。
折半查找是一种非常高效的查找算法，特别适用于数据量大和需要频繁查找的场景。然而，它也有其局限性，主要是需要预先排序的数据集。在接下来的章节里，我们将介绍更多不同类型和效率的查找算法。
5.3 二叉排序查找
5.3.1 二叉排序查找（Binary Search Tree, BST）概述
二叉排序查找是基于二叉排序树（Binary Search Tree, 简称BST）进行的。二叉排序树是一种特殊的二叉树，它满足以下性质：
- 任意节点的左子树只包含小于当前节点的元素。
- 任意节点的右子树只包含大于当前节点的元素。
- 左、右子树也分别为二叉排序树。
由于这些性质，二叉排序查找可以在平均时间复杂度为 (O(\log n)) 的情况下快速地找到目标元素。然而，需要注意的是，在最坏情况下（即当二叉排序树退化为链表时），查找的时间复杂度会变为 (O(n))。
5.3.2 C++实现示例
下面是一个使用C++实现的二叉排序查找示例：
#include <iostream> struct Node { int data; Node* left; Node* right; }; // 创建新节点 Node* createNode(int data) { Node* newNode = new Node(); newNode->data = data; newNode->left = nullptr; newNode->right = nullptr; return newNode; } // 在BST中查找元素 Node* searchInBST(Node* root, int target) { if (root == nullptr) { return nullptr; // 元素未找到 } if (root->data == target) { return root; // 元素找到 } else if (root->data > target) { return searchInBST(root->left, target); // 在左子树中查找 } else { return searchInBST(root->right, target); // 在右子树中查找 } } int main() { // 创建一个简单的BST Node* root = createNode(30); root->left = createNode(20); root->right = createNode(40); root->left->left = createNode(10); root->left->right = createNode(25); int target = 25; Node* result = searchInBST(root, target); if (result != nullptr) { std::cout << "Element found: " << result->data << std::endl; } else { std::cout << "Element not found" << std::endl; } return 0; }
在这个示例中，我们首先创建了一个简单的二叉排序树，并使用了一个递归函数 searchInBST 来进行查找。这个函数接受一个树的根节点和一个目标值作为参数，并返回找到的节点（如果存在）。
5.3.3 注意事项和优化
- 平衡问题：为了保证高效的查找，二叉排序树应该是“平衡”的。不平衡的树会导致查找效率降低。这也是为什么在实际应用中，通常会使用一些自平衡的二叉查找树变种，如AVL树或红黑树。
- 重复元素：在处理包含重复元素的数据集时，你需要决定如何处理这些重复值。一种常见的做法是让每个节点存储一个额外的计数器，以记录相同元素出现的次数。
- 动态操作：二叉排序树除了用于查找外，还可以方便地进行插入和删除操作，这些都可以在 (O(\log n)) 的时间内完成。
二叉排序查找在许多应用场景下都是非常高效和实用的。然而，与其他数据结构和算法一样，它也有其局限和需要注意的地方。在接下来的章节里，我们将继续探讨其他类型的查找算法。
5.4 查找速度比较
5.4.1 时间复杂度分析
在本章中，我们已经介绍了三种不同类型的查找算法：顺序查找（Sequential Search）、折半查找（Binary Search）和二叉排序查找（Binary Search Tree）。下面是这些算法的时间复杂度比较：
- 顺序查找（Sequential Search）: (O(n))
- 折半查找（Binary Search）: (O(\log n))（前提是数组已排序）
- 二叉排序查找（Binary Search Tree）: 平均时间复杂度 (O(\log n))，但最坏情况为 (O(n))
5.4.2 实际应用场景
不同的查找算法在不同的应用场景中有各自的优势和劣势：
- 顺序查找：适用于数据量较小或无法预排序的场景。实现简单，但在大数据集上效率低下。
- 折半查找：适用于已排序的数组，并且需要进行多次查找的场景。查找效率高，但不适用于动态变化的数据集。
- 二叉排序查找：适用于需要进行频繁查找、插入和删除操作的动态数据集。查找效率通常很高，但需要额外的内存来存储树结构。
5.4.3 综合考虑
在选择查找算法时，除了考虑基本的时间复杂度外，还需要考虑以下几点：
- 数据预处理：某些算法（如折半查找）需要预先排序的数据集，这会增加额外的时间和空间开销。
- 额外内存需求：像二叉排序树这样的数据结构需要额外的内存来存储节点和链接，这可能在内存受限的系统中成为问题。
- 实际数据分布：实际应用中数据可能不是均匀分布的，这会影响查找算法的实际性能。
综合考虑这些因素，你可以更加明智地选择适合你应用场景的查找算法。
在这一章节中，我们对顺序查找、折半查找和二叉排序查找进行了详细的讨论和比较。希望这能帮助你在实际应用中做出更加合适的选择。
第六部分：排序
6.1 直接插入排序 (Insertion Sort)
6.1.1 理论介绍
直接插入排序（Insertion Sort）是一种简单易懂，但在特定情况下非常高效的排序算法。基本思想是，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
该算法适用于少量数据的排序，是稳定的排序算法（Stable Sorting Algorithm），并且当元素基本有序时效率较高。
6.1.2 算法步骤
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
6.1.3 C++ 实现示例
下面是直接插入排序在C++中的一个基础实现。
#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; // Move elements of arr[0..i-1], that are greater than key, // to one position ahead of their current position while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } int main() { std::vector<int> arr = {12, 11, 13, 5, 6}; insertionSort(arr); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.1.4 性能分析
- 时间复杂度（Time Complexity）:
- 最佳情况：(O(n))，当数据已经是部分排序的。
- 平均情况和最差情况：(O(n^2))，每次添加一个新的元素都需要与前面所有元素进行比较。
- 空间复杂度（Space Complexity）:
(O(1))，因为我们只用了常数级别的额外空间。 - 稳定性（Stability）:
是一个稳定的排序算法。
通过这个章节，你应该对直接插入排序有了全面的了解，包括它的工作原理、如何在C++中实现它，以及其性能特点。这种排序算法在处理小型或部分排序的数据集时表现出色，是每个C++程序员都应该掌握的基础排序算法之一。
6.2 冒泡排序 (Bubble Sort)
6.2.1 理论介绍
冒泡排序（Bubble Sort）是最简单的排序算法之一，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这是一个非常直观的排序算法，但也是一个在实际应用中效率相对较低的算法。它是一个稳定的排序算法（Stable Sorting Algorithm）。
6.2.2 算法步骤
- 比较相邻的两个元素，如果前一个比后一个大，则交换它们。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样最后的元素就是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
6.2.3 C++ 实现示例
下面是冒泡排序在C++中的一个基础实现。
#include <iostream> #include <vector> void bubbleSort(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { // swap arr[j] and arr[j + 1] std::swap(arr[j], arr[j + 1]); } } } } int main() { std::vector<int> arr = {64, 25, 12, 22, 11}; bubbleSort(arr); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.2.4 性能分析
- 时间复杂度（Time Complexity）:
- 最佳情况：(O(n))，当数据已经是部分排序的。
- 平均情况和最差情况：(O(n^2))，每次添加一个新的元素都需要与前面所有元素进行比较。
- 空间复杂度（Space Complexity）:
(O(1))，因为我们只用了常数级别的额外空间。 - 稳定性（Stability）:
是一个稳定的排序算法。
通过这个章节，你应该对冒泡排序有了全面的了解，包括它的工作原理、如何在C++中实现它，以及其性能特点。尽管冒泡排序在效率上不是最优的选择，但由于其实现简单，因此在某些简单应用或教学场合仍有一席之地。这也是C++程序员需要了解的基础排序算法之一。
6.3 直接选择排序 (Selection Sort)
6.3.1 理论介绍
直接选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是不断地选择剩余元素中的最小（或最大）一个，然后将其放到序列的起始（或末尾）位置。
这种算法不是稳定的排序算法（Unstable Sorting Algorithm），因为它可能会改变相等元素的相对顺序。
6.3.2 算法步骤
- 在未排序的序列中找到最小（或最大）元素，存放到排序序列的起始（或末尾）位置。
- 从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
- 重复步骤2，直到所有元素均排序完毕。
6.3.3 C++ 实现示例
下面是直接选择排序在C++中的一个基础实现。
#include <iostream> #include <vector> void selectionSort(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; ++i) { // Find the minimum element in remaining unsorted array int min_idx = i; for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[min_idx]) { min_idx = j; } } // Swap the found minimum element with the first element std::swap(arr[min_idx], arr[i]); } } int main() { std::vector<int> arr = {64, 25, 12, 22, 11}; selectionSort(arr); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.3.4 性能分析
- 时间复杂度（Time Complexity）:
- 最佳、平均和最差情况：(O(n^2))，每次需要找出未排序中的最小（或最大）元素。
- 空间复杂度（Space Complexity）:
(O(1))，因为我们只用了常数级别的额外空间。 - 稳定性（Stability）:
不是一个稳定的排序算法。
通过这个章节，你应该对直接选择排序有了全面的了解，包括它的工作原理、如何在C++中实现它，以及其性能特点。虽然直接选择排序在大型数据集上并不高效，但它的代码实现简单明了，是学习排序算法或处理小型数据集时的一个不错的选择。这也是C++程序员需要了解的基础排序算法之一。
6.4 快速排序 (Quick Sort)
6.4.1 理论介绍
快速排序（Quick Sort）是一种使用分治（Divide-and-Conquer）策略来获得较高效率的排序算法，由英国计算机科学家Tony Hoare在1960年首次提出。其主要思想是通过一个基准元素将数组分为两个子数组，左子数组都比基准元素小，右子数组都比基准元素大，然后递归地排序两个子数组。
快速排序在最坏情况下的时间复杂度是 (O(n^2))，但在平均和最优情况下具有 (O(n \log n)) 的时间复杂度，且实际应用中通常比其他 (O(n \log n)) 的排序算法更快。
6.4.2 算法步骤
- 选择一个元素作为“基准”（pivot）。
- 重新排列数组，所有比基准小的元素摆放在基准前面，所有比基准大的元素摆在基准的后面（与基准值相等的数可以到任何一边）。在这个分区退出之后，该基准就处于数列的中间位置。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.4.3 C++ 实现示例
下面是快速排序在C++中的一个基础实现。
#include <iostream> #include <vector> int partition(std::vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = (low - 1); for (int j = low; j <= high - 1; ++j) { if (arr[j] < pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return (i + 1); } void quickSort(std::vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } int main() { std::vector<int> arr = {10, 7, 8, 9, 1, 5}; int n = arr.size(); quickSort(arr, 0, n - 1); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.4.4 性能分析
- 时间复杂度（Time Complexity）:
- 最佳和平均情况：(O(n \log n))
- 最差情况：(O(n^2))，当数组已经排序或逆序。
- 空间复杂度（Space Complexity）:
(O(\log n))，这是因为递归栈的深度。 - 稳定性（Stability）:
不是一个稳定的排序算法。
通过这个章节，你应该对快速排序有了全面的了解，包括它的工作原理、如何在C++中实现它，以及其性能特点。由于其高效的平均情况性能，快速排序在实际应用中是非常常用的，特别是在大数据集上。这也是每个C++程序员都应该掌握的高级排序算法之一。
6.5 堆排序 (Heap Sort)
6.5.1 理论介绍
堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的排序算法。它可以视为一个改进的选择排序，通过利用堆这种数据结构的性质，达到更高的效率。堆排序的时间复杂度为 (O(n \log n))。
堆排序分为两个主要步骤：建堆（Build Heap）和堆调整（Heapify）。建堆过程将原始数据重新组织为一个二叉堆结构；堆调整过程则从最大堆中不断提取最大元素并调整堆，直到堆为空。
6.5.2 算法步骤
- 将输入数组构建成一个最大堆（Max-Heap）。
- 将堆顶元素（即当前未排序部分的最大元素）与最后一个元素交换。
- 通过“堆调整”将剩下的 (n-1) 元素重新调整为最大堆。
- 重复步骤 2 和 3，直到堆中只有一个元素。
6.5.3 C++ 实现示例
下面是堆排序在C++中的一个基础实现。
#include <iostream> #include <vector> void heapify(std::vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(std::vector<int>& arr) { int n = arr.size(); // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i = n - 1; i > 0; i--) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } } int main() { std::vector<int> arr = {12, 11, 13, 5, 6, 7}; heapSort(arr); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.5.4 性能分析
- 时间复杂度（Time Complexity）:
- 在所有情况（最好、平均、最差）下：(O(n \log n))
- 空间复杂度（Space Complexity）:
(O(1))，因为我们只用了常数级别的额外空间。 - 稳定性（Stability）:
不是一个稳定的排序算法。
通过这个章节，你应该对堆排序有了全面的了解，包括它的工作原理、如何在C++中实现它，以及其性能特点。由于堆排序能够在几乎所有情况下都保持 (O(n \log n)) 的时间复杂度，它是一种非常可靠和高效的排序算法，值得所有C++程序员掌握。
6.6 归并排序 (Merge Sort)
6.6.1 理论介绍
归并排序（Merge Sort）是一种采用分治（Divide-and-Conquer）策略的排序算法。它将原始数组分成两个或更多的小组，然后对每个小组进行排序，最后将各个已排序的小组合并成一个新的有序数组。
归并排序是一种稳定的排序算法（Stable Sorting Algorithm），并且在所有情况下都具有 (O(n \log n)) 的时间复杂度。
6.6.2 算法步骤
- 将数组分为两个（或更多）的子数组。
- 对每个子数组进行排序。
- 将已排序的子数组合并为一个新的有序数组。
6.6.3 C++ 实现示例
下面是归并排序在C++中的一个基础实现。
#include <iostream> #include <vector> void merge(std::vector<int>& arr, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; std::vector<int> L(n1), R(n2); for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0; int j = 0; int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(std::vector<int>& arr, int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } int main() { std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; int arr_size = arr.size(); mergeSort(arr, 0, arr_size - 1); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.6.4 性能分析
- 时间复杂度（Time Complexity）:
- 在所有情况（最好、平均、最差）下：(O(n \log n))
- 空间复杂度（Space Complexity）:
(O(n))，这是因为归并过程需要一个与原数组同样大小的辅助数组。 - 稳定性（Stability）:
是一个稳定的排序算法。
6.7 希尔排序 (Shell Sort)
6.7.1 理论介绍
希尔排序（Shell Sort）是插入排序（Insertion Sort）的一种改进版本，由 Donald Shell 在1959年提出。与插入排序不同，希尔排序首先对元素进行分组，然后对每个组进行插入排序，最后进行一次全体元素的插入排序。
由于在初次分组后，各组内已经基本有序，因此最后一次全体元素的插入排序会变得非常快。希尔排序的性能因其步长（gap）选择而异，但在一些场景下能提供相当高的效率。
6.7.2 算法步骤
- 选择一个增量序列 ( t_1, t_2, \ldots, t_k )，其中 ( t_k = 1 )。
- 按增量序列个数 ( k )，对序列进行 ( k ) 趟排序。
- 每趟排序，根据对应的增量 ( t_i )，将待排序列分割成若干长度为 ( m ) 的子序列，分别对各子表进行直接插入排序。
6.7.3 C++ 实现示例
下面是希尔排序在C++中的一个基础实现。
#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}; shellSort(arr); for (const auto& num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }
6.7.4 性能分析
- 时间复杂度（Time Complexity）:
- 最佳情况：(O(n \log^2 n))
- 最差情况：(O(n^2))
- 空间复杂度（Space Complexity）:
(O(1))，因为我们只用了常数级别的额外空间。 - 稳定性（Stability）:
不是一个稳定的排序算法。
通过这个章节，你应该对希尔排序有了全面的了解，包括它的工作原理、如何在C++中实现它，以及其性能特点。希尔排序是一种相对高效的基于插入排序的算法，适用于中等大小的数据集，并且在某些特定的场景下能提供优于其他算法的性能。这也是C++程序员需要了解的一种高级排序算法。
6.8 排序算法速度比较
6.8.1 为什么需要比较排序算法速度
理解各种排序算法的性能特点是非常重要的，特别是在需要处理大量数据或对时间敏感的应用中。通过比较不同算法的速度，你可以选择最适合特定需求的排序算法。
6.8.2 比较的主要指标
- 时间复杂度（Time Complexity）: 描述算法随数据规模增长的时间需求。
- 空间复杂度（Space Complexity）: 描述算法需要的额外内存空间。
- 稳定性（Stability）: 稳定排序算法会保留相等元素的相对顺序。
- 适用场景（Applicability）: 一些排序算法在特定类型的数据集上表现更好。
6.8.3 排序算法比较表
| 排序算法 | 最好情况时间复杂度 | 平均情况时间复杂度 | 最差情况时间复杂度 | 空间复杂度 | 稳定性 |
| 冒泡排序 | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 |
| 选择排序 | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(1)) | 不稳定 |
| 插入排序 | (O(n)) | (O(n^2)) | (O(n^2)) | (O(1)) | 稳定 |
| 快速排序 | (O(n \log n)) | (O(n \log n)) | (O(n^2)) | (O(\log n)) | 不稳定 |
| 堆排序 | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | (O(1)) | 不稳定 |
| 归并排序 | (O(n \log n)) | (O(n \log n)) | (O(n \log n)) | (O(n)) | 稳定 |
| 希尔排序 | (O(n \log^2 n)) | - | (O(n^2)) | (O(1)) | 不稳定 |
6.8.4 实际应用建议
- 对于小规模或基本有序的数据，插入排序或冒泡排序是可接受的。
- 对于大规模数据，快速排序、堆排序或归并排序通常更有效。
- 当内存空间有限时，可以优先考虑使用空间复杂度为 (O(1)) 的排序算法，如堆排序。
- 当需要稳定排序时，归并排序是一个非常好的选择。
通过这一章节，你应该能够根据自己的具体需求，更加明智地选择适合的排序算法。这不仅可以帮助你在实际项目中提高效率，还是每个C++程序员都应该掌握的基础知识。
结语
在我们的编程学习之旅中，理解是我们迈向更高层次的重要一步。然而，掌握新技能、新理念，始终需要时间和坚持。从心理学的角度看，学习往往伴随着不断的试错和调整，这就像是我们的大脑在逐渐优化其解决问题的“算法”。
这就是为什么当我们遇到错误，我们应该将其视为学习和进步的机会，而不仅仅是困扰。通过理解和解决这些问题，我们不仅可以修复当前的代码，更可以提升我们的编程能力，防止在未来的项目中犯相同的错误。
我鼓励大家积极参与进来，不断提升自己的编程技术。无论你是初学者还是有经验的开发者，我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用，不妨点击收藏，或者留下你的评论分享你的见解和经验，也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持，也是对我持续分享和创作的动力。
