史上最全算法总结程序员必学算法 每个程序员都应该知道的

在编程中，算法是用于解决特定问题或实现特定任务的一组指令或过程。算法可以用任何编程语言来表达，可以像一系列基本操作一样简单，也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。算法的主要目标是接收输入、处理它并提供预期的输出。算法可以根据时间和空间复杂度、解决问题所使用的技术以及所解决问题的类型进行分类。算法的示例有排序、搜索、图形遍历、字符串操作、数学运算等等。

我们将讨论的算法：

1. 排序算法：排序是计算机科学中的基本操作，有多种有效的算法，例如快速排序、合并排序和堆排序。
2. 搜索算法：在大型数据集中搜索元素是一项常见任务，有多种有效的算法，例如二分搜索和哈希表。
3. 图算法：图算法用于解决与图相关的问题，例如查找两个节点之间的最短路径或确定图是否连通。
4. 动态编程：动态编程是一种通过将问题分解为更小的子问题并存储这些子问题的解决方案以避免冗余计算来解决问题的技术。
5. 贪心算法：贪心算法用于通过在每一步做出局部最优选择来解决优化问题，以期找到全局最优值。
6. 分而治之：分而治之是一种基于多分支递归的算法设计范式。分治算法将问题分解为相同或相关类型的子问题，直到这些问题变得简单到可以直接解决。
7. 回溯：回溯是一种通用算法技术，它考虑以系统的方式搜索所有可能的组合，并在确定特定路径不能成为解决方案的一部分时立即放弃该路径。
8. 随机算法：随机算法利用随机性来解决问题。它对于解决无法确定性解决的问题或提高问题的平均情况复杂性很有用。

这些算法广泛应用于各种应用中，对于程序员来说，对它们有深入的了解非常重要。所以我会尽力解释它们。

1. 排序算法：

• 快速排序：快速排序是一种分而治之的算法，它从数组中选择一个“主元”元素，并根据其他元素是否小于或大于主元将它们划分为两个子数组。然后对子数组进行递归排序。

Python:

def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) middle quicksort(right)print(quicksort([3,6,8,10,1,2,1]))

Java:

import java.util.ArrayList;import java.util.List;public class QuickSort { public static List<Integer> quicksort(List<Integer> arr) { if (arr.size() <= 1) { return arr; } int pivot = arr.get(arr.size() / 2); List<Integer> left = new ArrayList<>(); List<Integer> middle = new ArrayList<>(); List<Integer> right = new ArrayList<>(); for (int x : arr) { if (x < pivot) { left.add(x); } else if (x == pivot) { middle.add(x); } else { right.add(x); } } List<Integer> sorted = new ArrayList<>(); sorted.addAll(quicksort(left)); sorted.addAll(middle); sorted.addAll(quicksort(right)); return sorted; } public static void main(String[] args) { List<Integer> input = new ArrayList<>(); input.add(3); input.add(6); input.add(8); input.add(10); input.add(1); input.add(2); input.add(1); List<Integer> sorted = quicksort(input); System.out.println(sorted); }}

• 归并排序：归并排序算法是一种分而治之的算法，它将数组一分为二，对两半进行排序，然后将它们合并在一起。

Pytion:

def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right)def merge(left, right): result = [] i = 0 j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i = 1 else: result.append(right[j]) j = 1 result = left[i:] result = right[j:] return resultprint(merge_sort([3,6,8,10,1,2,1]))Java:

Java：

import java.util.Arrays;public class MergeSort { public static void main(String[] args) { int[] arr = {3, 6, 8, 10, 1, 2, 1}; mergeSort(arr); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr) { if (arr.length <= 1) { return; } int mid = arr.length / 2; int[] left = Arrays.copyOfRange(arr, 0, mid); int[] right = Arrays.copyOfRange(arr, mid, arr.length); mergeSort(left); mergeSort(right); merge(arr, left, right); } public static void merge(int[] arr, int[] left, int[] right) { int i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[i] < right[j]) { arr[k ] = left[i ]; } else { arr[k ] = right[j ]; } } while (i < left.length) { arr[k ] = left[i ]; } while (j < right.length) { arr[k ] = right[j ]; } }}

• 堆排序：堆排序算法是一种基于比较的排序算法，它从输入元素构建堆，然后重复从堆中提取最大元素并将其放置在排序后的输出数组的末尾。

Python：

def heap_sort(arr): n = len(arr) for i in range(n, -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)def heapify(arr, n, i): largest = i l = 2 * i 1 r = 2 * i 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)print(heap_sort([3,6,8,10,1,2,1]))

Java：

public class HeapSort { public static void heapSort(int[] arr) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int i) { int largest = i; int l = 2 * i 1; int r = 2 * i 2; if (l < n && arr[l] > arr[largest]) { largest = l; } if (r < n && arr[r] > arr[largest]) { largest = r; } if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } public static void main(String[] args) { int[] arr = {3, 6, 8, 10, 1, 2, 1}; heapSort(arr); for (int num : arr) { System.out.print(num " "); } }}

2. 搜索算法：

• 二分搜索：二分搜索是一种从排序的项目列表中查找项目的有效算法。它的工作原理是重复将正在搜索的数组部分分成两半，直到找到目标值。

Python：

def Binary_search(arr, x): low = 0 high = len(arr) - 1 mid = 0 while low <= high: mid = (high low) // 2 if arr[mid] < x: low = mid 1 elif arr[mid] > x: high = mid - 1 else: return mid return -1print(binary_search([1,2,3,4,5,6,7], 4))

Java：

public class BinarySearch { public static int binarySearch(int[] arr, int x) { int low = 0; int high = arr.length - 1; int mid = 0; while (low <= high) { mid = (high low) / 2; if (arr[mid] < x) { low = mid 1; } else if (arr[mid] > x) { high = mid - 1; } else { return mid; } } return -1; } public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7}; int x = 4; int result = binarySearch(arr, x); System.out.println(result); }}

• 哈希表：哈希表是一种将键映射到值的数据结构，使用哈希函数计算存储桶或槽数组的索引，从中可以找到所需的值。

Python：

class HashTable: def __init__(self): self.size = 10 self.keys = [None] * self.size self.values = [None] * self.size def put(self, key, data): index = self.hash_Function(key) while self.keys[index] is not None: if self.keys[index] == key: self.values[index] = data # update return index = (index 1) % self.size self.keys[index] = key self.values[index] = data def get(self, key): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: return self.values[index] index = (index 1) % self.size return None def hash_function(self, key): sum = 0 for pos in range(len(key)): sum = sum ord(key[pos]) return sum % self.sizet = HashTable()t.put("apple", 10)t.put("orange", 20)t.put("banana", 30)print(t.get("orange"))

Java：

public class HashTable { private int size = 10; private String[] keys = new String[size]; private int[] values = new int[size]; public void put(String key, int data) { int index = hashFunction(key); while (keys[index] != null) { if (keys[index].equals(key)) { values[index] = data; // update return; } index = (index 1) % size; } keys[index] = key; values[index] = data; } public int get(String key) { int index = hashFunction(key); while (keys[index] != null) { if (keys[index].equals(key)) { return values[index]; } index = (index 1) % size; } return -1; // or 任何适当的默认值 } private int hashFunction(String key) { int sum = 0; for (int i = 0; i < key.length(); i ) { sum = sum (int) key.charAt(i); } return sum % size; } public static void main(String[] args) { HashTable t = new HashTable(); t.put("apple", 10); t.put("orange", 20); t.put("banana", 30); System.out.println(t.get("orange")); }}

3.图算法：

• Dijkstra最短路径算法：Dijkstra最短路径算法是一种寻找图中节点之间最短路径的算法。

Python：

import heapqdef dijkstra(graph, start): heap = [(0, start)] visited = set() while heap: (cost, v) = heapq.heappop(heap) if v not in visited: visited.add(v) for u, c in graph[v].items(): if u not in visited: heapq.heappush(heap, (cost c, u)) return visitedgraph = { 'A': {'B': 2, 'C': 3}, 'B': {'D': 4, 'E': 5}, 'C': {'F': 6}, 'D': {'G': 7}, 'E': {'G': 8, 'H': 9}, 'F': {'H': 10}, 'G': {}, 'H': {}}print(dijkstra(graph, 'A'))

Java:

import java.util.*;public class DijkstraAlgorithm { public static Map<String, Integer> dijkstra(Map<String, Map<String, Integer>> graph, String start) { PriorityQueue<Node> heap = new PriorityQueue<>(); Map<String, Integer> distances = new HashMap<>(); Set<String> visited = new HashSet<>(); heap.offer(new Node(0, start)); distances.put(start, 0); while (!heap.isEmpty()) { Node current = heap.poll(); String vertex = current.vertex; int cost = current.cost; if (!visited.contains(vertex)) { visited.add(vertex); Map<String, Integer> neighbors = graph.get(vertex); if (neighbors != null) { for (Map.Entry<String, Integer> entry : neighbors.entrySet()) { String neighbor = entry.getKey(); int edgeCost = entry.getValue(); int newCost = cost edgeCost; if (!visited.contains(neighbor) && (!distances.containsKey(neighbor) || newCost < distances.get(neighbor))) { distances.put(neighbor, newCost); heap.offer(new Node(newCost, neighbor)); } } } } } return distances; } public static void main(String[] args) { Map<String, Map<String, Integer>> graph = new HashMap<>(); graph.put("A", Map.of("B", 2, "C", 3)); graph.put("B", Map.of("D", 4, "E", 5)); graph.put("C", Map.of("F", 6)); graph.put("D", Map.of("G", 7)); graph.put("E", Map.of("G", 8, "H", 9)); graph.put("F", Map.of("H", 10)); graph.put("G", new HashMap<>()); graph.put("H", new HashMap<>()); Map<String, Integer> distances = dijkstra(graph, "A"); System.out.println(distances); } static class Node implements Comparable<Node> { int cost; String vertex; public Node(int cost, String vertex) { this.cost = cost; this.vertex = vertex; } @Override public int compareTo(Node other) { return Integer.compare(cost, other.cost); } }}

4.动态规划：

• 斐波那契数列：可以使用动态规划解决的问题的典型示例是斐波那契数列。

Python：

def fibonacci(n): if n <= 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) fibonacci(n-2) print(fibonacci(10))

Java：

public class Fibonacci { public static int fibonacci(int n) { if (n <= 0) { return 0; } else if (n == 1) { return 1; } else { return fibonacci(n - 1) fibonacci(n - 2); } } public static void main(String[] args) { int result = fibonacci(10); System.out.println(result); }}

5. 贪心算法：

• 霍夫曼编码：霍夫曼编码是一种无损数据压缩算法，它使用贪心算法为给定的符号集构造前缀码。

Python：

from collections import Counter, nametuple def huffman_encoding(data): """ 生成输入数据的霍夫曼编码字符串 """ # 为数据创建频率计数器 freq_counter = Counter(data) # 为霍夫曼树节点创建命名元组 HuffmanNode = nametuple("HuffmanNode", ["char", "freq"]) # 为哈夫曼树创建优先级队列priority_queue = PriorityQueue() # 将所有字符添加到优先级队列 for char, freq in freq_counter.items() ： priority_queue.put（HuffmanNode（字符，freq)) # 合并节点，直到仅保留根节点 ，同时priority_queue.qsize() > 1: left_node =priority_queue.get() right_node =priority_queue.get() combined_freq = left_node.freq right_node.freqcombined_node = HuffmanNode(None,combined_freq) priority_queue.put(combined_node) # 为每个字符生成霍夫曼码 huffman_code = {} generate_code (priority_queue.get(), "", huffman_code) # 对输入数据进行编码 encoded_data = "" for char in data: encoded_data = huffman_code[char] returnencoded_data, huffman_code print(huffman_encoding("aaaaabbbcccc"))

Java：

import java.util.*;class HuffmanNode { char character; int frequency; HuffmanNode left; HuffmanNode right; public HuffmanNode(char character, int frequency) { this.character = character; this.frequency = frequency; left = null; right = null; }}public class HuffmanEncoding { public static String huffmanEncoding(String data) { // 创建字符频率计数器 Map<Character, Integer> freqCounter = new HashMap<>(); for (char c : data.toCharArray()) { freqCounter.put(c, freqCounter.getOrDefault(c, 0) 1); } // 创建优先队列 PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>((a, b) -> a.frequency - b.frequency); for (Map.Entry<Character, Integer> entry : freqCounter.entrySet()) { priorityQueue.offer(new HuffmanNode(entry.getKey(), entry.getValue())); } // 合并节点直到只剩下根节点 while (priorityQueue.size() > 1) { HuffmanNode leftNode = priorityQueue.poll(); HuffmanNode rightNode = priorityQueue.poll(); HuffmanNode combinedNode = new HuffmanNode('\0', leftNode.frequency rightNode.frequency); combinedNode.left = leftNode; combinedNode.right = rightNode; priorityQueue.offer(combinedNode); } // 生成霍夫曼编码 Map<Character, String> huffmanCode = new HashMap<>(); generateCode(priorityQueue.poll(), "", huffmanCode); // 编码输入数据 StringBuilder encodedData = new StringBuilder(); for (char c : data.toCharArray()) { encodedData.append(huffmanCode.get(c)); } return encodedData.toString(); } private static void generateCode(HuffmanNode node, String code, Map<Character, String> huffmanCode) { if (node == null) { return; } if (node.left == null && node.right == null) { huffmanCode.put(node.character, code); } generateCode(node.left, code "0", huffmanCode); generateCode(node.right, code "1", huffmanCode); } public static void main(String[] args) { String data = "aaaaabbbcccc"; String encodedData = huffmanEncoding(data); System.out.println(encodedData); }}

6.分而治之：

• 归并排序：上面已经解释过

7. 回溯：

• N-皇后问题：N-皇后问题是一个可以使用回溯法解决的经典问题。目标是将 N 个皇后放置在 NxN 棋盘上，使得任何皇后都不能攻击其他皇后。

Python：

def solveNQueens(n): defcould_place(row,col): # 检查是否可以将皇后放置在棋盘上[row][col] # 检查该行是否没有受到该列中任何先前皇后的攻击 for i in range (row): if board[i] == col or abs(board[i] - col) == abs(i - row): return False return True def backtrack(row=0, count=0): for col in range(n): if Could_place(row, col): board[row] = col if row 1 == n: count = 1 else: count = backtrack(row 1, count) return count board = [-1 for x in range(n)] return backtrack() print(solveNQueens(4))

Java：

public class NQueens { public static int solveNQueens(int n) { int[] board = new int[n]; return backtrack(0, 0, n, board); } private static int backtrack(int row, int count, int n, int[] board) { for (int col = 0; col < n; col ) { if (couldPlace(row, col, board)) { board[row] = col; if (row 1 == n) { count ; } else { count = backtrack(row 1, count, n, board); } } } return count; } private static boolean couldPlace(int row, int col, int[] board) { for (int i = 0; i < row; i ) { if (board[i] == col || Math.abs(board[i] - col) == Math.abs(i - row)) { return false; } } return true; } public static void main(String[] args) { int n = 4; int count = solveNQueens(n); System.out.println(count); }}

该算法开始将皇后放置在第一行，并且对于每个放置的皇后，它都会检查它是否受到任何先前皇后的攻击。如果没有，它将继续到下一行并重复该过程。如果皇后被放置在受到攻击的位置，算法会回溯并尝试不同的位置。这一直持续到所有皇后都被放置在棋盘上且没有任何皇后互相攻击为止。

8. 随机算法：

• 随机快速排序：快速排序算法的一种变体，其中随机选择主元。

Python：

import randomdef randomized_quicksort(arr): if len(arr) <= 1: return arr pivot = random.choice(arr) left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return randomized_quicksort(left) middle randomized_quicksort(right)print(randomized_quicksort([3,6,8,10,1,2,1]))

Java：

import java.util.ArrayList;import java.util.List;import java.util.Random;public class RandomizedQuickSort { public static List<Integer> randomizedQuicksort(List<Integer> arr) { if (arr.size() <= 1) { return arr; } Random random = new Random(); int pivotIndex = random.nextInt(arr.size()); int pivot = arr.get(pivotIndex); List<Integer> left = new ArrayList<>(); List<Integer> middle = new ArrayList<>(); List<Integer> right = new ArrayList<>(); for (int num : arr) { if (num < pivot) { left.add(num); } else if (num == pivot) { middle.add(num); } else { right.add(num); } } List<Integer> sortedLeft = randomizedQuicksort(left); List<Integer> sortedRight = randomizedQuicksort(right); List<Integer> sortedArr = new ArrayList<>(); sortedArr.addAll(sortedLeft); sortedArr.addAll(middle); sortedArr.addAll(sortedRight); return sortedArr; } public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add(3); arr.add(6); arr.add(8); arr.add(10); arr.add(1); arr.add(2); arr.add(1); List<Integer> sortedArr = randomizedQuicksort(arr); System.out.println(sortedArr); }}

这些是每个程序员都应该熟悉的一些最常用的算法。了解这些算法及其实现可以帮助程序员在设计和实现高效解决方案时做出更好的决策。

延伸阅读：