在編程開發中，算法是用于解決特定問題或完成特定任務的一組指令或過程。算法可以用任何編程語言表示，可以像一系列基本操作一樣簡單，也可以像涉及不同數據結構和邏輯的多步驟過程一樣復雜。
在編程開發中，算法是用于解決特定問題或完成特定任務的一組指令或過程。算法可以用任何編程語言表示，可以像一系列基本操作一樣簡單，也可以像涉及不同數據結構和邏輯的多步驟過程一樣復雜。
算法的主要目標是接收輸入、處理它并提供預期的輸出。算法可以根據時間和空間復雜性、用于解決問題的技術以及解決問題的類型進行分類。算法的例子有排序、搜索、圖形遍歷、字符串操作、數學運算等等。
?這些算法廣泛用于各種應用程序，程序員對它們有深刻的理解很重要，所以我會盡力解釋它們。
我們將要討論的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 result
print(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 -1
print(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_code
print(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]))
這些是每個程序員都應該熟悉的一些最常用的算法。 了解這些算法與它的實現可以幫助程序員在設計和實現高效解決方案時做出更好的決策。
