程序员常用的几种算法（原理、流程、代码等分析）_程序算法

1. 排序算法

1. 冒泡排序（Bubble Sort）

1.1 原理：

通过重复遍历待排序序列，比较相邻元素的值，若发现逆序则交换，直到没有可交换的元素为止。

1.2 算法流程：

1. 从第一个元素开始，比较相邻的元素。
2. 如果第一个比第二个大，就交换它们。
3. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
4. 针对所有的元素重复以上的步骤，除了最后一个。
5. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.3 时间复杂度：

• 最好情况：(O(n))
• 平均情况：(O(n^2))
• 最坏情况：(O(n^2))

1.4 稳定性：

稳定

1.5 Java代码实现

public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                // swap arr[j+1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

2. 选择排序（Selection Sort）

2.1 原理

首先，在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.2 算法流程

1. 初始状态：无序区为R[1..n]，有序区为空。
2. 第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
3. n-1趟结束，数组有序化了。

2.3 时间复杂度

• 最好情况：(O(n^2))
• 平均情况：(O(n^2))
• 最坏情况：(O(n^2))

2.3 稳定性

不稳定

2.4 Java代码实现

public void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIdx])
                minIdx = j;
        // Swap the found minimum element with the first element
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

3. 插入排序（Insertion Sort）

3.1 原理

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.2 算法流程

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

3.3 时间复杂度

• 最好情况：(O(n))
• 平均情况：(O(n^2))
• 最坏情况：(O(n^2))

3.4 稳定性

稳定

3.5 Java代码实现

public void insertionSort(int[] arr) {
    int n = arr.length;
    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;
    }
}

4. 归并排序（Merge Sort）

4.1 原理

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先将数据分为两半，分别对它们进行排序，然后将两个有序的部分合并在一起。

4.2 算法流程

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤3直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

4.3 时间复杂度

• 所有情况：(O(n \log n))

4.4 稳定性

稳定

4.5 Java代码实现

public void mergeSort(int[] arr, int l, int r) {
    if (l < r) {
        // Find the middle point
        int m = (l+r)/2;
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr , m+1, r);
        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}
 
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;
    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];
    /*Copy data to temp arrays*/
    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];
    /* Merge the temp arrays */
    // Initial indexes of first and second subarrays
    int i = 0, j = 0;
    // Initial index of merged subarry array
    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++;
    }
    /* Copy remaining elements of L[] if any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    /* Copy remaining elements of R[] if any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

5. 快速排序（Quick Sort）

5.1 原理

快速排序使用分治法策略来把一个序列分为两个子序列。步骤为：

1. 从序列中挑出一个元素，作为"基准"（pivot）。
2. 重新排序序列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子序列排序。

5.2 算法流程

1. 选择一个基准元素，通常选择第一个元素或者最后一个元素。
2. 通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有记录比另一部分的所有记录都小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

5.3 时间复杂度

• 最好情况：(O(n \log n))
• 平均情况：(O(n \log n))
• 最坏情况：(O(n^2))

5.4 稳定性

不稳定

5.5 Java代码实现

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        /* pi is partitioning index, arr[pi] is
          now at right place */
        int pi = partition(arr, low, high);
        // Recursively sort elements before
        // partition and after partition
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}
 
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; 
    int i = (low-1); // index of smaller element
    for (int j=low; j<high; j++) {
        // If current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++;
            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;
    return i+1;
}

6. 堆排序（Heap Sort）

6.1 原理

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

6.2 算法流程

1. 构造初始堆：将给定无序序列构造成一个大顶堆（升序排列用大顶堆，降序排列用小顶堆）。
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端。
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

6.3 时间复杂度

• 所有情况：(O(n \log n))

6.4 稳定性

不稳定

6.5 Java代码实现

public void heapSort(int arr[]) {
    int n = arr.length;
    // 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--) {
        // Move current root to end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}
 
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2*i + 1; // left = 2*i + 1
    int r = 2*i + 2; // right = 2*i + 2
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
    // If largest is not root
    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

7. 希尔排序（Shell Sort）

7.1 原理

希尔排序是插入排序的一种更高效的改进版本。希尔排序将整个序列分割成若干个子序列分别进行插入排序，从而达到使整个序列达到有序的目的。

7.2 算法流程

1. 选择一个增量序列 (t_1, t_2, ..., t_k)，其中 (t_i > t_{i+1}, t_k = 1)；
2. 按增量序列个数 (k)，对序列进行 (k) 轮排序；
3. 每轮排序，根据对应的增量 (t_i)，将待排序列分割成若干长度为 (m) 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。

7.3 时间复杂度

• 最好情况：(O(n \log n))
• 平均情况：取决于增量序列，一般为 (O(n \log^2 n))
• 最坏情况：(O(n^2))

7.4 稳定性

不稳定

7.5 Java代码实现

public void shellSort(int[] arr) {
    int n = arr.length;
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i += 1) {
            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;
        }
    }
}

8. 计数排序（Counting Sort）

8.1 原理

计数排序是一种非比较排序算法，其核心思想是将输入的数据值转换为键存储在额外开辟的数组空间中。它是通过计算一个数组中每个值的出现次数来实现排序的，适用于一定范围内的整数排序。由于计数排序不是基于比较的，它可以达到比基于比较的排序算法更快的排序速度。

8.2 算法流程

1. 找出待排序的数组中最大和最小的元素；
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。

8.3 时间复杂度

• 最好情况：(O(n+k))
• 平均情况：(O(n+k))
• 最坏情况：(O(n+k))

其中，(n) 是数组长度，(k) 是数组中数据的范围。

8.4 稳定性

计数排序是稳定的排序算法。

8.5 Java代码实现

public class CountingSort {
    public static void countingSort(int[] arr) {
        if (arr.length == 0) return;
        // 寻找数组中的最大最小值
        int maxValue = arr[0], minValue = arr[0];
        for (int value : arr) {
            if (value > maxValue) maxValue = value;
            if (value < minValue) minValue = value;
        }
        // 计数数组
        int[] countArray = new int[maxValue - minValue + 1];
        for (int value : arr) {
            countArray[value - minValue]++;
        }
        // 根据计数数组，输出结果
        int index = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i] > 0) {
                arr[index++] = i + minValue;
                countArray[i]--;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

2. 搜索算法

1. 线性搜索（Linear Search）

原理：线性搜索是最基本的搜索算法，它从数据结构的一端开始，逐个检查每个元素，直到找到所需的元素或搜索完所有元素。

算法流程：

1. 从第一个元素开始遍历数组。
2. 如果找到目标值，则返回其索引。
3. 如果遍历完整个数组仍未找到目标值，则目标值不存在于数组中。

时间复杂度：(O(n))

适用场景：线性搜索适用于小规模数据集或无序数据集的搜索。它不要求数据预先排序，因此对于结构简单的搜索任务来说是一个简便的选择。

特点：简单直接，但效率低下，特别是在处理大量数据时。

Java代码实现：

public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // 返回找到的元素的索引
        }
    }
    return -1; // 如果没有找到，返回-1
}

2. 二分搜索（Binary Search）

原理：二分搜索是一种在有序数组中查找特定元素的高效算法。它通过将目标值与数组中间元素比较，每次排除一半的搜索空间，从而缩小搜索范围。

算法流程：

1. 确定数组的中间位置。
2. 如果中间元素正好是目标值，则搜索完成。
3. 如果目标值小于中间元素，则在左半部分继续搜索。
4. 如果目标值大于中间元素，则在右半部分继续搜索。
5. 重复步骤2-4，直到找到目标值或搜索范围为空。

时间复杂度：(O(\log n))

适用场景：二分搜索适用于有序数据集。它高效地在排序数组中查找元素，通过不断将搜索范围减半来快速定位目标值。

特点：需要数据预先排序，但搜索效率高，特别适合于大规模数据集。

Java代码实现：

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 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
}

3. 深度优先搜索（DFS, Depth-First Search）

原理：深度优先搜索是一种用于遍历或搜索树或图的算法。它从一个节点开始，沿着树的深度遍历树的分支，直到找到所需的节点为止。

算法流程：

1. 从起始节点开始，将节点标记为已访问。
2. 遍历当前节点的所有未访问的邻接点，对每个邻接点递归执行DFS。
3. 回溯并继续执行步骤2，直到所有节点都被访问。

时间复杂度：(O(V + E))，其中(V)是顶点数，(E)是边数。

适用场景：深度优先搜索适用于树和图的搜索问题，，如解决迷宫问题、路径查找、拓扑排序等。它通过尽可能深地搜索树的分支，直到找到解决方案或到达叶子节点。

特点：适用于目标路径较深或需要搜索所有可能路径的情况。可能需要大量内存，因为需要维护一个栈来存储遍历路径。

Java代码实现：

4. 广度优先搜索（BFS, Breadth-First Search）

原理：广度优先搜索是另一种图和树的遍历算法，它从根节点开始，逐层遍历所有邻接的节点。

算法流程：

1. 将起始节点加入队列，并标记为已访问。
2. 从队列中取出一个节点，并访问它的所有未访问的邻接节点，将邻接节点加入队列并标记为已访问。
3. 重复步骤2，直到队列为空。

时间复杂度：(O(V + E))

适用场景：广度优先搜索也适用于树和图的搜索问题，特别是在需要找到最短路径或层次遍历时。例如，社交网络中的朋友推荐、最短路径问题等。

特点：适用于目标路径较短的情况。它需要维护一个队列来存储每一层的节点，可能会占用较多内存。

Java代码实现：

5.动态规划

动态规划适用于具有重叠子问题和最优子结构性质的问题。它通常用于求解优化问题，比如寻找最大值或最小值，计数问题等。

使用场景：

1. 最优子结构：问题的最优解包含其子问题的最优解。即可以通过组合子问题的最优解来构造整个问题的最优解。
2. 重叠子问题：在求解过程中，某些子问题会被多次计算。动态规划通过存储这些子问题的解，避免了重复计算的开销。

典型应用：

1. 斐波那契数列：使用动态规划来计算斐波那契数列是避免重复计算的经典例子。
2. 最短路径问题：如Dijkstra算法和Floyd-Warshall算法，它们可以用于计算图中的最短路径。
3. 背包问题：动态规划用于求解0-1背包问题，即给定一组物品和一个背包，如何选择物品使得背包中物品的价值最大，同时不超过背包的容量限制。
4. 编辑距离：计算两个字符串之间的最少编辑操作次数，以将一个字符串转换为另一个字符串。
5. 最长公共子序列：找出两个序列的最长公共子序列的长度。
6. 最大子数组和：找出一个数组的一个子数组，使得该子数组的和最大。

动态规划的关键步骤：

1. 定义状态：确定问题的状态，以及状态之间如何转移。
2. 确定状态转移方程：找出状态之间的关系，形成状态转移方程。
3. 初始化状态：确定初始状态的值。
4. 计算状态：根据状态转移方程计算每个状态。
5. 构造最终解：根据计算出的状态，构造问题的最终解。

6.哈希表查找（Hash Table Lookup）

原理：哈希表通过使用哈希函数将键映射到表中的一个位置来访问记录，以支持快速插入和搜索操作。

算法流程：

1. 使用哈希函数计算键的哈希值。
2. 根据哈希值找到对应的桶或槽。
3. 在桶中搜索具体的键（如果存在冲突，则可能需要遍历桶中的所有元素）。

时间复杂度：平均情况下为 (O(1))，最坏情况（所有键都映射到同一个位置）为 (O(n))。

Java代码实现：Java中的HashMap类提供了哈希表的实现。

import java.util.HashMap;
 
HashMap<Integer, String> map = new HashMap<>();
map.put(1, "one"); // 插入
String value = map.get(1); // 查找

7.顺序索引查找（Sequential Index Lookup）

原理：顺序索引查找是在有序数组中通过顺序遍历索引来查找元素的方法。

算法流程：

1. 从数组的第一个元素开始。
2. 逐个遍历元素直到找到目标元素或遍历完整个数组。

时间复杂度：(O(n))

Java代码实现：

public int sequentialIndexLookup(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i; // 返回目标元素的索引
        }
    }
    return -1; // 如果没有找到，返回-1
}

8.二叉搜索树查找（Binary Search Tree Lookup）

原理：二叉搜索树是一种特殊的二叉树，其中每个节点都含有一个键，并且每个节点的键都大于其左子树中任意节点的键，而小于其右子树中任意节点的键。

算法流程：

1. 从树的根节点开始。
2. 如果根节点的键等于要查找的键，则查找成功。
3. 如果要查找的键小于根节点的键，则在左子树中继续查找。
4. 如果要查找的键大于根节点的键，则在右子树中继续查找。
5. 重复步骤2-4，直到找到键或遍历完树。

时间复杂度：平均情况下为 (O(\log n))，最坏情况（树退化为链表）为 (O(n))。

Java代码实现：

class TreeNode {
    int val;
    TreeNode left, right;
 
    TreeNode(int x) {
        val = x;
    }
}
 
public class BinarySearchTree {
    public TreeNode search(TreeNode root, int target) {
        if (root == null || root.val == target) return root;
        if (target < root.val) return search(root.left, target);
        else return search(root.right, target);
    }
}

4. 图算法

1. 图的遍历

• • 深度优先搜索（DFS, Depth-First Search）：一种利用递归或栈实现的图遍历方法，用于探索图的顶点和边。
  • 广度优先搜索（BFS, Breadth-First Search）：一种利用队列实现的图遍历方法，用于按层次遍历图。

1. 最短路径问题

• • Dijkstra算法：用于求解加权图中单源最短路径问题。
  • Bellman-Ford算法：也用于单源最短路径问题，但能处理图中包含负权边的情况。
  • Floyd-Warshall算法：用于求解所有顶点对之间的最短路径问题。

1. 最小生成树问题

• • Prim算法：用于求解加权无向连通图的最小生成树问题。
  • Kruskal算法：也用于求解最小生成树问题，基于边的贪心选择。

1. 网络流问题

• • Ford-Fulkerson方法：用于求解最大网络流问题。
  • Edmonds-Karp算法：是Ford-Fulkerson方法的一个具体实现，用于求解最大网络流问题。

1. 拓扑排序

• • 用于有向无环图（DAG），对图中所有顶点进行线性排序，使得对每一条有向边(uv)，顶点(u)都排在顶点(v)的前面。

1. 强连通分量

• • Kosaraju算法：用于在有向图中找出所有强连通分量。
  • Tarjan算法：也用于找出有向图的强连通分量，效率通常较高。

1. 图的着色

• • 贪心着色算法：用于图着色问题，尤其是地图着色问题，通过贪心策略为图的顶点着色。

1. 二分图检测与匹配

• • 匈牙利算法：用于求解二分图的最大匹配问题。

5. 哈希算法

常用的哈希算法有多种，它们在安全性、效率、输出长度等方面有所不同，主要用于数据的快速查找、数据完整性验证、安全加密等。

1. MD5 (Message Digest Algorithm 5)

• • 产生128位的哈希值，通常用32个十六进制数表示。
  • 由于其弱碰撞抗性，不再推荐用于安全性要求高的场合。

1. SHA系列 (Secure Hash Algorithm)

• • SHA-1：产生160位的哈希值，已被证实存在安全漏洞，不推荐用于安全敏感的应用。
  • SHA-2：包括多个版本，如SHA-224、SHA-256、SHA-384和SHA-512等，哈希值长度从224位到512位不等，安全性高于MD5和SHA-1。
  • SHA-3：最新的SHA版本，提供与SHA-2不同的设计，进一步增强了安全性。

1. RIPEMD (RACE Integrity Primitives Evaluation Message Digest)

• • 包括RIPEMD-128、RIPEMD-160等版本，其中RIPEMD-160设计用来取代MD5和SHA-1，提供相似的哈希值长度但更高的安全性。

1. Whirlpool

• • 产生512位的哈希值，基于AES设计，提供很高的安全性。

1. BLAKE2

• • 旨在改进BLAKE算法，提供比SHA-2和SHA-3更高的速度，同时保持高安全性。有两种主要变体：BLAKE2s和BLAKE2b。

1. CRC系列 (Cyclic Redundancy Check)

• • 如CRC32，主要用于检测数据传输或存储过程中的偶然错误，而不是用于加密。

1. MurmurHash

• • 非加密哈希函数，主要用于一般的哈希检索操作。以其高效的处理速度和分布均匀性著称。

1. CityHash、FarmHash、xxHash

• • 这些都是高效的非加密哈希函数，适用于软件中大数据的快速哈希计算，由Google等开发。

6. 字符串匹配算法

字符串匹配算法在计算机科学中非常重要，特别是在文本编辑、搜索引擎、数据库管理、生物信息学等领域。

1. 朴素字符串匹配算法（Naive String Matching Algorithm）

• • 直接按顺序比较主字符串和模式字符串的每个字符，直到找到匹配或遍历完整个主字符串。
  • 时间复杂度为 (O(mn))，其中 (m) 是模式字符串的长度，(n) 是主字符串的长度。

1. Rabin-Karp算法

• • 使用哈希技术，先计算模式字符串的哈希值，然后计算主字符串中每个长度等于模式字符串的子串的哈希值，比较哈希值以找到匹配。
  • 平均时间复杂度为 (O(n+m))，但最坏情况下为 (O(mn))。

1. KMP算法（Knuth-Morris-Pratt）

• • 利用已匹配的部分信息，通过部分匹配表（也称为"失配表"）避免从头开始匹配，提高搜索效率。
  • 时间复杂度为 (O(n+m))。

1. Boyer-Moore算法

• • 从模式字符串的末尾开始比较，利用坏字符规则和好后缀规则跳过某些字符，提高匹配效率。
  • 最坏情况下时间复杂度为 (O(mn))，但在实践中通常比KMP更快。

1. Sunday算法

• • 类似于Boyer-Moore算法，但是通过检查主字符串中位于模式字符串后的第一个字符来决定下一步的移动距离。
  • 效率通常比Boyer-Moore算法更高。

1. Aho-Corasick算法

• • 用于多模式匹配，构建一个有限状态机来同时搜索多个模式。
  • 广泛应用于网络入侵检测系统和生物信息学中。

1. Finite State Machine（有限状态机）

• • 将模式字符串构建成一个状态机，每个状态对应于模式字符串中的位置，根据输入字符串的每个字符转换状态，直到达到接受状态表示匹配成功。

7.动态规划

动态规划是解决优化问题的一种方法，它将复杂问题分解为更小的子问题，并存储这些子问题的解，以避免重复计算。动态规划广泛应用于各种领域，如算法设计、运筹学、人工智能等。

1. 斐波那契数列：

• • 用于计算斐波那契序列的第 (n) 个数。这是动态规划的最基本应用，展示了如何将一个大问题拆分为小问题，并重用这些小问题的解。

1. 最长公共子序列（LCS）：

• • 用于找出两个序列共有的最长子序列的长度。这个问题在生物信息学和文本处理中特别有用。

1. 最长递增子序列（LIS）：

• • 用于在一个数列中找到最长递增子序列的长度。这个问题在数据分析和预测模型中有应用。

1. 编辑距离（Levenshtein距离）：

• • 用于计算将一个字符串转换成另一个字符串所需的最少编辑操作次数（包括插入、删除、替换字符）。这个算法在文本比较和自然语言处理中很有用。

1. 背包问题：

• • 有多种变体，如0-1背包问题、完全背包问题、多重背包问题等。用于在限定的总体积或总重量内，选择一些物品，使得总价值最大。

1. 最小路径和：

• • 用于在一个给定的矩阵中，找到从左上角到右下角的路径，使得路径上的数值之和最小。这个问题在图像处理和网格计算中有应用。

1. 硬币找零问题：

• • 给定不同面额的硬币和一个总金额，计算组成该金额的最少硬币数量。这个问题在经济学和支付系统中有应用。

1. 切割钢条问题：

• • 给定一根钢条和一个价格表，求切割钢条的方案，使得销售收益最大。

1. 最大子数组和问题（Kadane算法）：

• • 用于找出一个数组中和最大的连续子数组。

1. 最优二叉搜索树：

• • 给定一组键和每个键的搜索概率，构造一棵二叉搜索树，使得搜索所有键的总代价最小。

8.分治算法

分治算法是一种重要的算法设计策略，它将一个复杂的问题分解成两个或多个相似的子问题，直到这些子问题变得简单足以直接求解。然后，这些子问题的解被合并为原问题的解。

1. 快速排序：

• • 快速排序算法通过选取一个元素作为"基准"，将数组分为比基准小和比基准大的两部分，然后递归地对这两部分进行快速排序，直到整个数组排序完成。

1. 归并排序：

• • 归并排序算法将数组分成两半，递归地对每一半进行排序，然后将两个有序的半部分合并成一个有序的整体。

1. 二分搜索：

• • 二分搜索算法在一个有序的数组中查找特定元素，通过将搜索区间分成两半，逐步缩小搜索范围，直到找到目标元素或确定元素不存在。

1. 大整数乘法（Karatsuba算法）：

• • Karatsuba算法是一种快速乘法算法，它将大整数分成较小的部分，递归地计算这些部分的乘积，然后组合这些乘积以得到最终结果。

1. Strassen矩阵乘法：

• • Strassen算法是一种快速矩阵乘法算法，它通过将矩阵分成更小的子矩阵，递归地计算这些子矩阵的乘积，然后通过特定的方式组合这些乘积以得到最终的矩阵乘积。

1. 最接近点对问题：

• • 该问题要求在平面上找到一对最接近的点。通过分治算法，可以将点集分成两半，递归地在每一半中找到最接近的点对，然后在两部分的边界附近查找可能更接近的点对。

1. 快速傅里叶变换（FFT）：

• • 快速傅里叶变换是一种高效的算法，用于计算序列的离散傅里叶变换（DFT）及其逆变换。FFT通过分治策略，将DFT分解成较小的DFTs，从而减少计算复杂度。

9.贪心算法

贪心算法是一种在每一步选择中都采取当前状态下最优的选择，以期望通过局部最优的选择达到全局最优解的算法策略。它不像动态规划那样考虑整个问题的所有可能解，而是依赖于贪心选择性质，即通过局部最优选择能够产生全局最优解。

1. 分数背包问题：

• • 在背包问题的一个变体中，物品可以分割成任意大小，目标是在不超过背包容量的情况下，尽可能最大化背包中物品的总价值。贪心策略是按照单位重量价值（价值/重量）降序选择物品。

1. 霍夫曼编码：

• • 霍夫曼编码是一种用于数据压缩的贪心算法。通过构建一棵最优二叉树，将最常见的字符用较短的编码，较少见的字符用较长的编码，从而实现数据的有效压缩。

1. 活动选择问题：

• • 给定一组活动，每个活动都有一个开始时间和结束时间，目标是选择最大数量的互不重叠的活动。贪心策略是按照活动的结束时间进行排序，然后依次选择每个活动，确保它与已选择的活动不冲突。

1. 最小生成树算法：

• • 如Kruskal算法和Prim算法，这两种算法都用于在一个加权无向图中找到最小生成树。Kruskal算法按照边的权重进行排序，然后选择不形成环的边，直到生成树包含所有顶点。Prim算法从任意顶点开始，每次选择连接已选择顶点和未选择顶点且权重最小的边。

1. 迪杰斯特拉（Dijkstra）算法：

• • 用于在加权图中找到从单个源点到所有其他顶点的最短路径。算法贪心地选择未处理的顶点中具有最小距离估计的顶点，然后更新其邻居的距离估计。

1. 任务调度问题：

• • 在任务调度的不同变体中，目标是最小化完成所有任务所需的总时间或最大化完成任务的数量。例如，按照截止时间或所需时间进行贪心选择。

1. 找零问题：

• • 给定不同面额的硬币和一个总金额，计算如何用最少的硬币数凑成总金额。在硬币面额能够互相整除的情况下，贪心策略是从最大面额开始依次选择硬币。

10.回溯算法

回溯算法是一种通过尝试分步的方式寻找问题的解决方法的算法。在每一步中，当它意识到当前的选择序列不会导致一个最终解时，它将取消最近的选择，尝试下一个选项。这种方法被广泛用于解决约束满足问题，其中包括搜索、组合优化问题等。

1. N皇后问题：

• • 在一个N×N的棋盘上放置N个皇后，使得它们互不攻击（即任何两个皇后都不在同一行、同一列或同一对角线上）。回溯算法通过逐行放置皇后，并在每行中尝试所有列，以找到所有可能的解决方案。

1. 数独求解器：

• • 给定一个部分填充的9×9数独，目标是填充空格，使得每一行、每一列和每一个9宫格内的数字都是1到9且不重复。回溯算法通过尝试每个空格的所有可能数字并检查数独的约束来解决问题。

1. 组合问题：

• • 给定一组数字或字符，找出所有可能的组合方式，比如所有长度为k的组合。回溯算法通过递归地构建组合，并在达到所需长度或不满足条件时回溯。

1. 排列问题：

• • 给定一组数字或字符，找出所有可能的排列方式。回溯算法通过选择一个未使用的元素添加到当前排列中，并在完成排列或不满足条件时回溯。

1. 子集问题：

• • 给定一组不同的整数，找出所有可能的子集。回溯算法通过逐个添加元素到当前子集，并在完成子集构建或不满足条件时回溯。

1. 图的着色问题：

• • 给定一个无向图和颜色数量，目标是给图的每个顶点着色，使得任何两个相邻的顶点都不同色。回溯算法通过为每个顶点尝试所有可能的颜色并检查图的约束来解决问题。

1. 八数码问题（滑动拼图）：

• • 在一个3×3的棋盘上，有一个空格和编号为1到8的八个方块，目标是通过滑动方块使得棋盘达到目标状态。回溯算法通过移动空格并尝试所有可能的移动来寻找解决方案。