前言
"计算机科学中的算法，是解决问题的关键工具。无论是在软件开发、数据处理还是系统优化等领域，算法都发挥着重要作用。正如建筑师需要熟悉不同类型的砖块和梁柱一样，作为程序员和计算机科学家，我们需要掌握一系列基本算法，它们是我们解决问题的基石。
在本文中，我们将介绍几种最基本、最经典的算法。这些算法不仅在计算机科学的教学课程中被广泛传授，而且在实际的软件开发中经常被使用。无论是对数组进行排序、在图结构中搜索最短路径，还是解决字符串匹配问题，这些算法都可以为我们提供有力的解决方案。
通过学习这些算法，你将能够理解计算机如何通过有限的步骤和规则来解决实际问题。你将了解算法的原理和实现，并掌握如何在实际项目中灵活应用它们。无论是在面试中展示你的算法知识，还是在日常编程工作中优化你的代码，这些基本算法都将成为你的利器。
让我们一起展开这个精彩的算法之旅，探索它们的奥秘和应用。无论你是新手还是有经验的开发者，这些基本算法都将为你打开计算机科学的大门，并且成为你编程生涯的重要基石。"
一、堆排序（Heap Sort）
堆排序（Heap Sort）是一种使用堆数据结构进行排序的算法。它基于以下原理：首先将待排序的元素构建成一个最大堆（大根堆或最小堆），然后将堆顶元素与堆的最后一个元素交换位置，并重新调整堆使其满足堆的性质，重复这个过程直到整个序列有序。下面是堆排序的原理和C++代码示例：
原理实现：
- 构建最大堆（建堆）：从最后一个非叶子节点开始，对每个节点进行堆化操作（即将当前节点与其子节点进行比较并交换，使得父节点始终大于（或小于）子节点）。
- 排序：原数组中的最大元素位于堆顶，将堆顶元素与堆的最后一个元素交换位置，并将堆的大小减1。然后再次对堆进行堆化操作，得到次大元素。重复这个过程直到堆的大小为1，即完成排序。
下面是一个图示，展示了堆排序的原理：
9 / \ 7 8 / \ / \ 5 4 6 3 堆化之后的最大堆: 9 / \ 7 8 / \ / \ 5 4 6 3 交换堆顶与最后一个元素: 3 / \ 7 8 / \ / \ 5 4 6 9 重新调整堆: 8 / \ 7 6 / \ / \ 5 4 3 9 交换堆顶与最后一个元素: 9 / \ 7 6 / \ / \ 5 4 3 8 重新调整堆: 7 / \ 5 6 / \ / \ 9 4 3 8 交换堆顶与最后一个元素: 8 / \ 5 6 / \ / \ 9 4 3 7 重新调整堆: 6 / \ 5 4 / \ / \ 9 8 3 7 交换堆顶与最后一个元素: 7 / \ 5 4 / \ / \ 9 8 3 6 重新调整堆: 5 / \ 4 3 / \ / \ 9 8 7 6 交换堆顶与最后一个元素: 6 / \ 4 3 / \ / \ 9 8 7 5 排序完成的数组: 3 4 5 6 7 8 9
下面是上图中堆排序的步骤介绍：
1. 建堆: 根据给定的数组构建一个最大堆（或最小堆）。在最大堆中，父节点的值总是大于等于其子节点的值，而在最小堆中则是小于等于。
- 将数组转换为一个完全二叉树结构，从最后一个非叶子节点开始，依次向上调整每个父节点，使得当前节点左右子树都满足堆的性质。
- 在图中，最开始的完全二叉树即为初始的最大堆，节点之间的关系满足最大堆的性质。
2. 排序: 将堆顶元素与最后一个元素交换位置，并将交换后的堆的范围缩小，再进行堆化操作。
- 将堆顶元素与堆的最后一个元素进行交换。
- 交换后，堆的最后一个元素变为有序区的一部分，堆区范围缩小。
- 在图中，交换堆顶元素和最后一个元素后得到的堆即为交换后的堆。
3. 调整堆: 对交换后的堆进行重新调整，使得剩余元素重新满足堆的性质。
- 从堆顶开始，比较左右子节点的大小，并与较大（或较小）的子节点进行交换，从而满足堆的性质。
- 重复上述步骤，直到将交换后的堆重新调整为最大堆（或最小堆）。
- 在图中，分别为交换堆顶和最后一个元素后的重新调整堆的过程。
重复以上步骤，直到最大堆（或最小堆）中的元素全部排序完成，最终得到一个有序的数组。
请注意，上述图示中的堆排序是基于最大堆的。如果想要实现最小堆排序，只需要将构建堆和调整堆的过程中的比较方式反转即可。
1.C++编写的堆排序代码示例如下
#include <iostream> using namespace std; // 交换元素 void swap(int& a, int& b) { int temp = a; a = b; b = temp; } // 最大堆调整 void maxHeapify(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) { swap(arr[i], arr[largest]); maxHeapify(arr, n, largest); } } // 堆排序 void heapSort(int arr[], int n) { // 构建最大堆（建堆） for (int i = n / 2 - 1; i >= 0; i--) maxHeapify(arr, n, i); // 排序（重复交换堆顶与最后一个元素，然后调整堆） for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); // 交换堆顶与最后一个元素 maxHeapify(arr, i, 0); // 调整堆 } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "原始数组: "; printArray(arr, n); heapSort(arr, n); cout << "排序后的数组: "; printArray(arr, n); return 0; }
这段代码实现了堆排序算法，下面是代码的详细解释：
1. 首先，我们定义了一个交换元素的函数 `swap`，用于交换两个变量的值。
2. 然后，定义了一个最大堆调整的函数 `maxHeapify`，用于调整堆结构。该函数接受三个参数：待调整的数组 `arr`，数组的大小 `n`，以及需要调整的根节点的索引 `i`。函数的目的是将以索引 `i` 为根节点的子树调整为最大堆。在函数中，首先判断左子节点和右子节点的值，然后将最大值的索引存储在变量 `largest` 中。接下来，如果根节点不是最大值，则将根节点与最大值交换，并继续递归调用 `maxHeapify` 函数来调整已交换的子节点。
3. 接下来，定义了堆排序的函数 `heapSort`。该函数接受两个参数：待排序的数组 `arr` 和数组的大小 `n`。堆排序的过程分为两个主要步骤：建堆和排序。在建堆阶段，我们从最后一个非叶子节点开始，依次调用 `maxHeapify` 函数来构建最大堆。在排序阶段，我们交换堆顶元素与末尾元素，并调用 `maxHeapify` 函数来调整剩余元素，重复执行这个过程直到整个数组有序。
4. 最后，定义了一个打印数组的函数 `printArray`，用于打印数组的元素。
原始数组: 12 11 13 5 6 7
排序后的数组: 5 6 7 11 12 13
总结起来，这段代码通过构建最大堆和重复调整堆的操作实现了堆排序算法。堆排序具有较好的时间复杂度和稳定性，可以有效地对数组进行排序。
2.以下是C和Python的堆排序代码示例！
#include <stdio.h> // 交换数组中两个元素的位置 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // 调整堆结构 void heapify(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) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } } // 堆排序主函数 void heapSort(int arr[], int n) { // 构建最大堆（从最后一个非叶子节点开始） for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 一个个从堆顶取出元素，重新构建堆 for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); heapify(arr, i, 0); } } // 打印数组 void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); heapSort(arr, n); printf("排序后的数组: "); printArray(arr, n); return 0; }
def heapify(arr, n, i): largest = i # 初始化最大值为根节点的索引 left = 2 * i + 1 right = 2 * i + 2 # 若左子节点大于根节点，则更新最大值 if left < n and arr[left] > arr[largest]: largest = left # 若右子节点大于根节点，则更新最大值 if right < n and arr[right] > arr[largest]: largest = right # 若最大值不是根节点，则交换根节点和最大值，并递归调整堆结构 if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heapSort(arr): n = len(arr) # 构建最大堆（从最后一个非叶子节点开始） for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 一个个从堆顶取出元素，重新构建堆 for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] heapify(arr, i, 0) return arr arr = [12, 11, 13, 5, 6, 7] print("原始数组:", arr) sorted_arr = heapSort(arr) print("排序后的数组:", sorted_arr)
二、希尔排序（Shell Sort）
希尔排序（Shell Sort）是一种插入排序的改进算法，它通过将数组元素按照一定间隔（称为增量）进行分组，分组后对每个分组进行插入排序，不断缩小增量直到增量为1，最后进行最后一次插入排序。这个增量序列可以是任意的，常用的增量序列为希尔增量序列。
下面通过图示来介绍希尔排序的原理和步骤：
假设有一个待排序的数组 [8, 3, 5, 1, 4, 2, 7, 6]。
1. 首先，选择一个增量（比如是数组长度的一半），这里的增量为4。
- 分成4个分组，并对每个分组应用插入排序。
- 数组分组后的样子：
[8, 2] [3, 7] [5, 6] [1, 4]
- 分别对每个分组进行插入排序：
[2, 8] [3, 7] [5, 6] [1, 4]
[2, 3, 7, 8] [1, 4, 5, 6]
2. 减小增量为2，并对分组进行插入排序。
- 数组分组后的样子：
[2, 3, 7, 8, 1, 4, 5, 6]
- 对每个分组进行插入排序：
[1, 2, 4, 7] [3, 5, 6, 8]
- 组合两个分组后得到一个有序序列：
[1, 2, 3, 4, 5, 6, 7, 8]
3. 最后，对整个数组进行最后一次插入排序（增量为1）即可得到最终排序结果：
[1, 2, 3, 4, 5, 6, 7, 8]
通过不断缩小增量，希尔排序可以使整体更趋于有序，从而减少插入排序的比较和移动次数，提高排序效率。
需要注意的是，希尔排序的增量选择和步骤会影响最终排序的效果，选择不同的增量序列可能会得到不同的排序性能。
希尔排序的原理和步骤可以用以下图示进行更直观的展示：
初始： [8, 3, 5, 1, 4, 2, 7, 6] 增量4： [2, 8] [3, 7] [5, 6] [1, 4] ↓ ↓ ↓ ↓ [2, 3, 7, 8] [1, 4, 5, 6] 增量2： [2, 3, 7, 8, 1, 4, 5, 6] ↓ ↓ [1, 2, 4, 7] [3, 5, 6, 8] 增量1： [1, 2, 3, 4, 5, 6, 7, 8]
通过图示，你可以看到希尔排序的工作原理和具体步骤。随着增量的减小，数组逐渐趋于有序，最终达到完全有序的状态。这样可以减少插入排序的比较和移动次数，提高整体排序的效率。
1.C++ 编写的希尔排序算法
#include <iostream> using namespace std; void shellSort(int arr[], int n) { // 定义增量（间隔）序列的初始值 int gap = n / 2; // 不断缩小增量直到 gap = 1 while (gap > 0) { // 对每个增量进行插入排序 for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; // 将 arr[j-gap]、arr[j-2*gap]、...依次与 temp 进行比较，若比 temp 大，则向后移动元素 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } // 将 temp 插入到正确位置 arr[j] = temp; } // 缩小增量 gap /= 2; } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; } int main() { int arr[] = {8, 4, 1, 9, 5, 7, 3}; int n = sizeof(arr) / sizeof(arr[0]); cout << "原始数组: "; printArray(arr, n); shellSort(arr, n); cout << "排序后的数组: "; printArray(arr, n); return 0; }
希尔排序（Shell Sort）是一种改进的插入排序算法，它通过将待排序的元素分组后进行插入排序，逐步缩小增量（间隔）来达到排序的目的。
希尔排序的实现步骤如下：
1. 首先定义一个增量（间隔）序列，一般选择 n/2，然后不断缩小增量，直到增量为 1。
2. 按增量序列对数组进行分组，将每个分组使用插入排序的方式进行排序。注意，每个分组内的元素并不一定相邻，而是相隔一个增量。
3. 缩小增量，重复第2步，直到增量为 1。最后一次增量为 1 的排序即为最后的完全排序。
希尔排序的关键在于选择合适的增量序列，不同的增量序列会影响到排序的效率。希尔排序的时间复杂度不是上界为 O(n^2) 的比较排序算法，但其时间复杂度的界论至今仍然是未解决的问题。
上述代码以数组 {8, 4, 1, 9, 5, 7, 3} 为例，展示了希尔排序的具体实现过程。排序过程依次按照增量序列为 7、3、1 来进行分组和插入排序，最终得到排序后的数组。
2.以下是C和Python的希尔排序代码示例！
#include <stdio.h> void shellSort(int arr[], int n) { int i, j, gap, temp; // 定义增量（间隔）序列的初始值 gap = n / 2; // 不断缩小增量直到 gap = 1 while (gap > 0) { // 对每个增量进行插入排序 for (i = gap; i < n; i++) { temp = arr[i]; j = i; // 将 arr[j-gap]、arr[j-2*gap]、...依次与 temp 进行比较，若比 temp 大，则向后移动元素 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } // 将 temp 插入到正确位置 arr[j] = temp; } // 缩小增量 gap /= 2; } } void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {8, 4, 1, 9, 5, 7, 3}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); printArray(arr, n); shellSort(arr, n); printf("排序后的数组: "); printArray(arr, n); return 0; }
三、计数排序（Counting Sort）
计数排序是一种线性时间复杂度的排序算法，适用于对一定范围内的整数进行排序。它的原理是通过统计每个元素出现的次数，然后根据统计信息对元素进行排序。
下面是计数排序的原理步骤：
- 统计数组中每个元素的出现次数，并创建一个计数数组。计数数组的长度应该等于待排序数组中最大元素的值加上 1。
- 遍历计数数组，累计每个元素出现的次数，并将累加后的值更新到计数数组中。
- 创建一个临时数组，长度与待排序数组相同。
- 从待排序数组的最后一个元素开始向前遍历，根据计数数组中对应元素的值，将元素放置到临时数组中的相应位置。同时，更新计数数组中的对应元素值。
- 将临时数组中的元素复制回原始数组，完成排序。
以下是计数原理的步骤：
原始无序数组：[8, 3, 5, 2, 5, 2, 9] 初始化计数数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 统计每个元素的出现次数，更新计数数组： [0, 0, 2, 0, 0, 1, 0, 0, 1, 1] 创建临时数组，用于存放排序结果。 从待排序数组最后一个元素开始，根据计数数组中的值，将元素放置到临时数组中对应位置，并更新计数数组： 将9放入临时数组的最后一个位置，更新计数数组：[0, 0, 2, 0, 0, 1, 0, 0, 1, 0] 将5放入临时数组的第5个位置，更新计数数组：[0, 0, 2, 0, 0, 0, 0, 0, 1, 0] 将2放入临时数组的第2个位置，更新计数数组：[0, 0, 1, 0, 0, 0, 0, 0, 1, 0] 将5放入临时数组的第4个位置，更新计数数组：[0, 0, 1, 0, 0, 0, 0, 0, 0, 0] 将2放入临时数组的第1个位置，更新计数数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 将3放入临时数组的第3个位置，更新计数数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 将8放入临时数组的第8个位置，更新计数数组：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 将临时数组的元素复制回原始数组，得到有序数组：[2, 2, 3, 5, 5, 8, 9]
1.C++ 编写的计数排序算法
#include <iostream> #include <vector> using namespace std; void countSort(vector<int>& arr) { // 找到最大值 int maxVal = *max_element(arr.begin(), arr.end()); // 创建计数数组，并初始化为0 vector<int> count(maxVal + 1, 0); // 统计每个元素的出现次数 for (int num : arr) { count[num]++; } // 将计数数组累加，确定每个元素在排序后的数组中的位置 for (int i = 1; i <= maxVal; i++) { count[i] += count[i - 1]; } // 创建临时数组，用于存放排序结果 vector<int> sortedArr(arr.size()); // 从待排序数组最后一个元素开始，根据计数数组中的值，将元素放置到临时数组中对应位置 for (int i = arr.size() - 1; i >= 0; i--) { sortedArr[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // 将临时数组复制回原始数组 for (int i = 0; i < arr.size(); i++) { arr[i] = sortedArr[i]; } } int main() { vector<int> arr = {8, 3, 5, 2, 5, 2, 9}; // 调用计数排序函数 countSort(arr); // 输出排序结果 cout << "排序后的结果："; for (int num : arr) { cout << num << " "; } cout << endl; return 0; }
计数排序的实现思路相对简单明了。首先，找到待排序数组中的最大值，然后创建一个计数数组，长度为最大值加一，用于统计每个元素的出现次数。接着，通过累加计数数组中的元素，确定每个元素在排序后的数组中的位置。然后，创建一个临时数组，用于存放排序结果。最后，从待排序数组的最后一个元素开始，根据计数数组中的值，将元素放置到临时数组中对应的位置。最后，将临时数组复制回原始数组，完成排序。
2.以下是C和Python的计数排序代码示例！
#include <stdio.h> void countSort(int arr[], int n) { // 找到最大值 int maxVal = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > maxVal) { maxVal = arr[i]; } } // 创建计数数组，并初始化为0 int count[maxVal + 1]; for (int i = 0; i <= maxVal; i++) { count[i] = 0; } // 统计每个元素的出现次数 for (int i = 0; i < n; i++) { count[arr[i]]++; } // 将计数数组累加，确定每个元素在排序后的数组中的位置 for (int i = 1; i <= maxVal; i++) { count[i] += count[i - 1]; } // 创建临时数组，用于存放排序结果 int sortedArr[n]; // 从待排序数组最后一个元素开始，根据计数数组中的值，将元素放置到临时数组中对应位置 for (int i = n - 1; i >= 0; i--) { sortedArr[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // 将临时数组复制回原始数组 for (int i = 0; i < n; i++) { arr[i] = sortedArr[i]; } } int main() { int arr[] = {8, 3, 5, 2, 5, 2, 9}; int n = sizeof(arr) / sizeof(arr[0]); // 调用计数排序函数 countSort(arr, n); // 输出排序结果 printf("排序后的结果："); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
def countSort(arr): # 找到最大值 maxVal = max(arr) # 创建计数数组，并初始化为0 count = [0] * (maxVal + 1) # 统计每个元素的出现次数 for num in arr: count[num] += 1 # 将计数数组累加，确定每个元素在排序后的数组中的位置 for i in range(1, maxVal + 1): count[i] += count[i - 1] # 创建临时数组，用于存放排序结果 sortedArr = [0] * len(arr) # 从待排序数组最后一个元素开始，根据计数数组中的值，将元素放置到临时数组中对应位置 for num in reversed(arr): sortedArr[count[num] - 1] = num count[num] -= 1 # 返回排序结果 return sortedArr arr = [8, 3, 5, 2, 5, 2, 9] # 调用计数排序函数 sortedArr = countSort(arr) # 输出排序结果 print("排序后的结果：", sortedArr)
四、基数排序（Radix Sort）
基数排序（Radix Sort）是一种非比较的排序算法，它是通过将待排序的元素按照每个位上的数值进行排序的。它可以应用于整数、浮点数和字符串等数据类型。
基数排序的原理是通过多次分配和收集的过程，将待排序的元素按照个位、十位、百位等位数进行排序，直到最高位。具体实现步骤如下：
1. 首先，确定待排序元素的最大值，以确定需要进行排序的最高位数。假设最大值为 `max_val`，判断其位数为 `d`。 2. 创建 10 个桶（用数组或链表表示）来存放元素，每个桶表示一个数字（0~9）。 3. 从最低位（个位）开始，对待排序元素进行分配（也称为入桶）： - 遍历待排序元素列表，按照个位数的值将元素放入对应的桶中。 - 例如，元素为 123，个位数为 3，则将其放入桶 3 中。 - 如果某个元素的位数不够 `d` 位，则在高位补 0，例如元素 8 补成 008。 4. 对每个桶中的元素，按照入桶的顺序（从 0 到 9），依次收集起来形成一个新的序列。 5. 重复步骤 3 和步骤 4，依次考虑十位、百位、千位等位数，直到最高位。每次分配和收集都是以上一次排序结果为基础进行的。 6. 完成上述步骤后，待排序的元素就会按照从低位到高位的顺序被完全排序。
基数排序的时间复杂度为 O(d*(n+k))，其中 n 是待排序元素的个数，d 是元素的最高位数，k 是基数的范围（0~9）。
需要注意的是，基数排序只适用于非负整数排序，对于负数的排序需要进行一些额外处理。
因为基数排序是根据位数进行排序的，对负数的位数排序会存在问题。下面介绍两种常见的处理方法：
- 基于补码的处理方法：
- 将负数转换为其对应的补码表示形式。
- 对所有元素取绝对值，并进行基数排序。
- 排序完成后，再将元素转回原始的符号表示。
- 这种方法的缺点是需要进行绝对值和符号转换操作，可能会增加额外的时间和空间开销。
基于扩展位的处理方法：
- 增加一个额外的位来表示符号（0 表示正数，1 表示负数）。
- 对正数和负数分别进行基数排序。
- 正数的处理与常规基数排序相同，只需忽略符号位。
- 负数的处理也一样，但在进行排序时，需要将符号位作为最高位来考虑。
- 最后将正数序列的结果与负数序列的结果合并，得到完整的排序结果。
1.C++ 编写的计数排序算法
#include <iostream> #include <vector> // 获取数字的某一位上的值 int getDigit(int num, int digit) { int divisor = 1; for (int i = 0; i < digit; i++) { divisor *= 10; } return (num / divisor) % 10; } // 基数排序 void radixSort(std::vector<int>& arr) { // 找到最大值，以确定需要进行排序的最高位数 int maxVal = arr[0]; for (int i = 1; i < arr.size(); i++) { if (arr[i] > maxVal) { maxVal = arr[i]; } } // 计算最高位数 int maxDigit = 0; while (maxVal > 0) { maxVal /= 10; maxDigit++; } // 创建 10 个桶（用数组表示） std::vector<std::vector<int>> buckets(10); // 从个位开始，按照每一位的值进行桶排序 for (int digit = 0; digit < maxDigit; digit++) { // 分配（入桶） for (int i = 0; i < arr.size(); i++) { int num = getDigit(arr[i], digit); buckets[num].push_back(arr[i]); } // 收集（依次将桶中的元素收集起来） int index = 0; for (int i = 0; i < 10; i++) { for (int j = 0; j < buckets[i].size(); j++) { arr[index++] = buckets[i][j]; } buckets[i].clear(); } } } int main() { std::vector<int> arr = {321, 5, 91, 75, 124, 853, 42}; // 调用基数排序函数 radixSort(arr); // 输出排序结果 std::cout << "排序后的结果："; for (int i = 0; i < arr.size(); i++) { std::cout << arr[i] << " "; } std::cout << std::endl; return 0; }
这段代码中，我们首先找到待排序元素的最大值，以确定需要进行排序的最高位数。然后，我们按照每一位的值进行桶排序。
具体实现步骤如下：
- 首先，我们创建一个 `buckets` 数组，用于存放 10 个桶（0~9），每个桶是一个 `vector`。这些桶将用于分配和收集元素，以完成基数排序。
- 接下来，我们从个位开始，依次对待排序的数组进行分配和收集操作。
- 在分配（入桶）过程中，我们通过 `getDigit` 函数获取每个元素当前位上的值，并将元素放入相应的桶中。
- 在收集过程中，我们依次将每个桶中的元素收集起来，形成新的序列。
- 重复上述步骤，直到处理到最高位为止。
- 最后，排序完成后，我们得到的数组就是有序的。
基数排序的核心思想是从低位到高位依次排序，通过多次分配和收集操作，按照每一位的值将元素放置在正确的位置上，最终得到完全排序的序列。
2.以下是C和Python的基数排序代码示例！
#include <stdio.h> // 获取数字的某一位上的值 int getDigit(int num, int digit) { int divisor = 1; for (int i = 0; i < digit; i++) { divisor *= 10; } return (num / divisor) % 10; } // 基数排序 void radixSort(int arr[], int n) { // 找到最大值，以确定需要进行排序的最高位数 int maxVal = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > maxVal) { maxVal = arr[i]; } } // 计算最高位数 int maxDigit = 0; while (maxVal > 0) { maxVal /= 10; maxDigit++; } // 创建 10 个桶（用二维数组表示） int buckets[10][n]; int bucketCount[10] = {0}; // 从个位开始，按照每一位的值进行桶排序 for (int digit = 0; digit < maxDigit; digit++) { // 分配（入桶） for (int i = 0; i < n; i++) { int num = getDigit(arr[i], digit); buckets[num][bucketCount[num]++] = arr[i]; } // 收集（依次将桶中的元素收集起来） int index = 0; for (int i = 0; i < 10; i++) { for (int j = 0; j < bucketCount[i]; j++) { arr[index++] = buckets[i][j]; } bucketCount[i] = 0; // 清空桶计数 } } } int main() { int arr[] = {321, 5, 91, 75, 124, 853, 42}; int n = sizeof(arr) / sizeof(arr[0]); // 调用基数排序函数 radixSort(arr, n); // 输出排序结果 printf("排序后的结果："); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }
def getDigit(num, digit): divisor = 1 for _ in range(digit): divisor *= 10 return (num // divisor) % 10 def radixSort(arr): # 找到最大值，以确定需要进行排序的最高位数 maxVal = max(arr) maxDigit = len(str(maxVal)) # 从个位开始，按照每一位的值进行桶排序 for digit in range(maxDigit): # 创建 10 个桶 buckets = [[] for _ in range(10)] # 分配（入桶） for num in arr: digitVal = getDigit(num, digit) buckets[digitVal].append(num) # 收集（依次将桶中的元素收集起来） index = 0 for bucket in buckets: for num in bucket: arr[index] = num index += 1 arr = [321, 5, 91, 75, 124, 853, 42] # 调用基数排序函数 radixSort(arr) # 输出排序结果 print("排序后的结果：", end="") for num in arr: print(num, end=" ") print()
五、图算法（Graph Algorithms）
1.什么是图算法？
图算法是应用于图数据结构上的算法，用于解决图相关的问题。图是由一组顶点和连接这些顶点的边组成的数据结构，它可以用来表示现实世界中的各种关系和网络。
图算法的原理是基于图的遍历和搜索，以及图的相关属性和操作来解决特定问题。以下是一些常见的图算法及其原理的简要介绍：
1. 深度优先搜索（DFS）：从起始点开始，尽可能深地探索每个相邻节点，直到无法继续深入为止，然后回溯到上一个节点进行下一个分支的探索。DFS可用于图的遍历、连通性检测和寻找路径等问题。
2. 广度优先搜索（BFS）：从起始点开始，逐层地探索相邻节点，先访问最近层级的节点，再逐渐向外扩展。BFS可用于图的遍历、最短路径搜索和连通性检测等问题。
3. 最小生成树：计算一个无向图的最小生成树，即包含所有顶点且边的总和最小的树。常见的算法有Prim算法和Kruskal算法。
4. 单源最短路径：计算一个有向带权图中从一个顶点到其他所有顶点的最短路径。常用的算法有Dijkstra算法和Bellman-Ford算法。
5. 最大流最小割：在一个有向带权图中，计算从源点到汇点的最大流量，并找到能够切割图的最小权重边集合。常见的算法有Ford-Fulkerson算法和Edmonds-Karp算法。
6. 拓扑排序：对有向无环图进行排序，使得所有的边的起点在排列中都在它的终点之前。拓扑排序常用于任务调度和依赖关系分析。
7. 图的匹配：在一个二分图中找到最大的匹配或最大独立集。常见的算法有匈牙利算法和霍普克洛夫特算法。
图算法还包括许多其他的问题和算法，如最小费用流、割边和割点、有向无环图的计数等等。
图算法的设计和实现需要考虑图的数据结构表示，以及合适的搜索和遍历策略。不同图算法的原理和复杂度也各有不同，但它们都是基于对图结构的理解和运用来解决相关问题的。
六、字符串匹配算法（String Matching Algorithms）
什么是字符串匹配算法?
字符串匹配算法是用于在一个文本字符串中查找特定模式字符串的算法。它们被广泛应用于文本搜索、信息检索、数据处理、编译器和字符串处理等领域。
字符串匹配问题可以形式化地描述为：给定一个文本字符串 T 和一个模式字符串 P，要找到 P 在 T 中的所有匹配位置或找到第一个匹配位置。
以下是几种常见的字符串匹配算法：
1. Brute-Force（朴素算法）：该算法从文本字符串中的每个字符位置开始，逐个与模式字符串进行匹配。时间复杂度为 O(mn)，其中 m 和 n 分别是模式字符串和文本字符串的长度。
2. Rabin-Karp：该算法使用哈希函数对模式字符串和文本字符串的子串进行哈希计算，并逐步滑动比较。当哈希值匹配时，再逐个比较字符以确认匹配。时间复杂度为 O(m+n)，其中 m 和 n 分别是模式字符串和文本字符串的长度。
3. Knuth-Morris-Pratt（KMP）：该算法利用模式字符串的前缀和后缀信息，在匹配过程中跳过一些不可能匹配的位置，避免了一些不必要的比较。时间复杂度为 O(m+n)，其中 m 和 n 分别是模式字符串和文本字符串的长度。
4. Boyer-Moore：该算法利用模式字符串的字符出现位置和最右原则，在匹配过程中跳过多个字符，从而提高匹配效率。时间复杂度为 O(mn)，但在实践中通常表现较好。
这些算法在不同场景下有着不同的性能表现，对于长文本和长模式字符串，KMP、Boyer-Moore 和 Rabin-Karp 算法通常具有更好的性能。而对于短模式字符串，Brute-Force 算法可能仍然是一个有效的选择。
字符串匹配算法的选择取决于实际情况，需要综合考虑文本和模式字符串的长度、匹配要求、应用场景以及算法的复杂度等因素。
