在编程开发中，算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示，可以像一系列基本操作一样简单，也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。
算法的主要目标是接收输入、处理它并提供预期的输出。算法可以根据时间和空间复杂性、用于解决问题的技术以及解决问题的类型进行分类。算法的例子有排序、搜索、图形遍历、字符串操作、数学运算等等。
这些算法广泛用于各种应用程序，程序员对它们有深刻的理解很重要，所以我会尽力解释它们。
我们将要讨论的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).归并排序：归并排序算法是一种分而治之的算法，它将一个数组一分为二，对两半进行排序，然后将它们归并在一起。
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)
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 result
print(merge_sort([3,6,8,10,1,2,1]))
3).堆排序：堆排序算法是一种基于比较的排序算法，它将输入元素构建一个堆，然后从堆中反复提取最大元素，并将其放在排序后的输出数组的末尾。
heap_sort(arr):
n= len(arr)
for iin range(n,-1,-1):
heapify(arr, n, i)
for iin range(n-1, 0,-1):
arr[i], arr[0]= arr[0], arr[i]
heapify(arr, i, 0)
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):
分成两半，直到找到目标值。
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-1
print(binary_search([1,2,3,4,5,6,7], 4))
2).哈希表：哈希表是一种将键映射到值的数据结构，使用哈希函数计算到桶或槽数组的索引，从中可以找到所需的值。
class HashTable:
__init__(self):
self.size= 10
self.keys= [None]* self.size
self.values= [None]* self.size
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
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
hash_function(self, key):
sum= 0
for posin 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
dijkstra(graph, start):
heap= [(0, start)]
visited= set()
while heap:
(cost, v)= heapq.heappop(heap)
if v notin visited:
visited.add(v)
for u, cin graph[v].items():
if u notin 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.动态规划：
斐波那契数列：斐波那契数列是可以使用动态规划解决的问题的经典示例。
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 collectionsimport Counter, namedtuple
huffman_encoding(data):
"""
Generates a Huffman encoded string of the input data
"""
# Create a frequency counterfor the data
freq_counter= Counter(data)
# Create a namedtuplefor the Huffman tree nodes
HuffmanNode= namedtuple("HuffmanNode", ["char", "freq"])
# Create a priority queuefor the Huffman tree
priority_queue= PriorityQueue()
# Add all characters to the priority queue
for char, freqin 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 codefor each character
huffman_code= {}
generate_code(priority_queue.get(), "", huffman_code)
# Encode the input data
encoded_data= ""
for charin data:
encoded_data+= huffman_code[char]
return encoded_data, huffman_code
print(huffman_encoding("aaaaabbbcccc"))
6.分治法：
归并排序：上面已经解释过了
7.回溯：
The N-Queens Problem：这是一个可以使用回溯法解决的经典问题。 目标是将 N 个问题放在 NxN 的棋盘上，使得任何皇后都不能攻击任何其他皇后。
solveNQueens(n):
could_place(row, col):
# checkif a queen can be placed on board[row][col]
# checkifthis row is not under attack from any previous queenin that column
for iin range(row):
if board[i]== col or abs(board[i]- col)== abs(i- row):
return False
return True
backtrack(row=0, count=0):
for colin 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= [-1for xin range(n)]
return backtrack()
print(solveNQueens(4))
该算法开始将皇后放置在第一行，并且对于每个放置的皇后，它检查它是否受到任何先前皇后的攻击。
如果不是，它将继续到下一行并重复该过程。 如果将皇后置于受到攻击的位置，算法会回溯并尝试不同的位置。 这一直持续到所有皇后都被放置在棋盘上且没有任何相互攻击。
8. 随机算法：— 随机快速排序：随机选择主元的快速排序算法的一种变体。
import random
randomized_quicksort(arr):
if len(arr)<= 1:
return arr
pivot= random.choice(arr)
left= [xfor xin arrif x< pivot]
middle= [xfor xin arrif x== pivot]
right= [xfor xin arrif x> pivot]
return randomized_quicksort(left)+ middle+ randomized_quicksort(right)
print(randomized_quicksort([3,6,8,10,1,2,1]))
这些是每个程序员都应该熟悉的一些最常用的算法。 了解这些算法与它的实现可以帮助程序员在设计和实现高效解决方案时做出更好的决策。
