在编程开发中，算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示，可以像一系列基本操作一样简单，也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。
算法的主要目标是接收输入、处理它并提供预期的输出。算法可以根据时间和空间复杂性、用于解决问题的技术以及解决问题的类型进行分类。算法的例子有排序、搜索、图形遍历、字符串操作、数学运算等等。
这些算法广泛用于各种应用程序，程序员对它们有深刻的理解很重要，所以我会尽力解释它们。
我们将要讨论的 8 大算法如下：
1、排序算法：
1).Quicksort：Quicksort 是一种分而治之的算法，它从数组中选择一个“主元”元素，然后根据其他元素是小于还是大于主元将它们分成两个子数组。然后对子数组进行递归排序。
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]))
复制代码
2).归并排序：归并排序算法是一种分而治之的算法，它将一个数组一分为二，对两半进行排序，然后将它们归并在一起。
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]))
复制代码
3).堆排序：堆排序算法是一种基于比较的排序算法，它将输入元素构建一个堆，然后从堆中反复提取最大元素，并将其放在排序后的输出数组的末尾。
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]))
复制代码
2.搜索算法：
1).二分搜索：二分搜索是一种从已排序的项目列表中查找项目的有效算法。它的工作原理是将要搜索的数组部分重复 def binary_search(arr, x):分成两半，直到找到目标值。
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))
复制代码
2).哈希表：哈希表是一种将键映射到值的数据结构，使用哈希函数计算到桶或槽数组的索引，从中可以找到所需的值。
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.size
t = HashTable()t.put("apple", 10)t.put("orange", 20)t.put("banana", 30)print(t.get("orange"))
复制代码
3.图算法：
1).Dijkstra 最短路径算法：Dijkstra 最短路径算法是一种寻找图中节点之间最短路径的算法。
import heapq
def 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 visited
graph = { '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'))
复制代码
4.动态规划：
斐波那契数列：斐波那契数列是可以使用动态规划解决的问题的经典示例。
def fibonacci(n): if n <= 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))
复制代码
5. 贪婪算法：
霍夫曼编码：霍夫曼编码是一种无损数据压缩算法，它使用贪婪算法为给定的一组符号构造前缀码。
from collections import Counter, namedtuple
def huffman_encoding(data): """ Generates a Huffman encoded string of the input data """ # Create a frequency counter for the data freq_counter = Counter(data) # Create a namedtuple for the Huffman tree nodes HuffmanNode = namedtuple("HuffmanNode", ["char", "freq"]) # Create a priority queue for the Huffman tree priority_queue = PriorityQueue() # Add all characters to the priority queue for char, freq in freq_counter.items(): priority_queue.put(HuffmanNode(char, freq)) # Combine nodes until only the root node remains while priority_queue.qsize() > 1: left_node = priority_queue.get() right_node = priority_queue.get() combined_freq = left_node.freq + right_node.freq combined_node = HuffmanNode(None, combined_freq) priority_queue.put(combined_node) # Generate the Huffman code for each character huffman_code = {} generate_code(priority_queue.get(), "", huffman_code) # Encode the input data encoded_data = "" for char in data: encoded_data += huffman_code[char] return encoded_data, huffman_codeprint(huffman_encoding("aaaaabbbcccc"))
复制代码
6.分治法：
归并排序：上面已经解释过了
7.回溯：
The N-Queens Problem：这是一个可以使用回溯法解决的经典问题。 目标是将 N 个问题放在 NxN 的棋盘上，使得任何皇后都不能攻击任何其他皇后。
def solveNQueens(n): def could_place(row, col): # check if a queen can be placed on board[row][col] # check if this row is not under attack from any previous queen in that column 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))
复制代码
该算法开始将皇后放置在第一行，并且对于每个放置的皇后，它检查它是否受到任何先前皇后的攻击。
如果不是，它将继续到下一行并重复该过程。 如果将皇后置于受到攻击的位置，算法会回溯并尝试不同的位置。 这一直持续到所有皇后都被放置在棋盘上且没有任何相互攻击。
8. 随机算法：— 随机快速排序：随机选择主元的快速排序算法的一种变体。
import random
def 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]))
复制代码
这些是每个程序员都应该熟悉的一些最常用的算法。 了解这些算法与它的实现可以帮助程序员在设计和实现高效解决方案时做出更好的决策。
文章转载自：古道轻风
原文链接：https://www.cnblogs.com/88223100/p/top-8-algorithms-every-programmer-should-know.html
体验地址：http://www.jnpfsoft.com/?from=001
评论