在編程開(kāi)發(fā)中，算法是用于解決特定問(wèn)題或完成特定任務(wù)的一組指令或過(guò)程。算法可以用任何編程語(yǔ)言表示，可以像一系列基本操作一樣簡(jiǎn)單，也可以像涉及不同數(shù)據(jù)結(jié)構(gòu)和邏輯的多步驟過(guò)程一樣復(fù)雜。
在編程開(kāi)發(fā)中，算法是用于解決特定問(wèn)題或完成特定任務(wù)的一組指令或過(guò)程。算法可以用任何編程語(yǔ)言表示，可以像一系列基本操作一樣簡(jiǎn)單，也可以像涉及不同數(shù)據(jù)結(jié)構(gòu)和邏輯的多步驟過(guò)程一樣復(fù)雜。
算法的主要目標(biāo)是接收輸入、處理它并提供預(yù)期的輸出。算法可以根據(jù)時(shí)間和空間復(fù)雜性、用于解決問(wèn)題的技術(shù)以及解決問(wèn)題的類型進(jìn)行分類。算法的例子有排序、搜索、圖形遍歷、字符串操作、數(shù)學(xué)運(yùn)算等等。
?這些算法廣泛用于各種應(yīng)用程序，程序員對(duì)它們有深刻的理解很重要，所以我會(huì)盡力解釋它們。
我們將要討論的8大算法如下：
1、排序算法：
1).Quicksort：Quicksort 是一種分而治之的算法，它從數(shù)組中選擇一個(gè)“主元”元素，然后根據(jù)其他元素是小于還是大于主元將它們分成兩個(gè)子數(shù)組。然后對(duì)子數(shù)組進(jìn)行遞歸排序。
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).歸并排序：歸并排序算法是一種分而治之的算法，它將一個(gè)數(shù)組一分為二，對(duì)兩半進(jìn)行排序，然后將它們歸并在一起。
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).堆排序：堆排序算法是一種基于比較的排序算法，它將輸入元素構(gòu)建一個(gè)堆，然后從堆中反復(fù)提取最大元素，并將其放在排序后的輸出數(shù)組的末尾。
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).二分搜索：二分搜索是一種從已排序的項(xiàng)目列表中查找項(xiàng)目的有效算法。它的工作原理是將要搜索的數(shù)組部分重復(fù)def binary_search(arr, x):
分成兩半，直到找到目標(biāo)值。
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).哈希表：哈希表是一種將鍵映射到值的數(shù)據(jù)結(jié)構(gòu)，使用哈希函數(shù)計(jì)算到桶或槽數(shù)組的索引，從中可以找到所需的值。
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 最短路徑算法是一種尋找圖中節(jié)點(diǎn)之間最短路徑的算法。
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.動(dòng)態(tài)規(guī)劃：
斐波那契數(shù)列：斐波那契數(shù)列是可以使用動(dòng)態(tài)規(guī)劃解決的問(wèn)題的經(jīng)典示例。
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. 貪婪算法：
霍夫曼編碼：霍夫曼編碼是一種無(wú)損數(shù)據(jù)壓縮算法，它使用貪婪算法為給定的一組符號(hào)構(gòu)造前綴碼。
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.分治法：
歸并排序：上面已經(jīng)解釋過(guò)了
7.回溯：
The N-Queens Problem：這是一個(gè)可以使用回溯法解決的經(jīng)典問(wèn)題。 目標(biāo)是將 N 個(gè)問(wèn)題放在 NxN 的棋盤(pán)上，使得任何皇后都不能攻擊任何其他皇后。
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))
該算法開(kāi)始將皇后放置在第一行，并且對(duì)于每個(gè)放置的皇后，它檢查它是否受到任何先前皇后的攻擊。
如果不是，它將繼續(xù)到下一行并重復(fù)該過(guò)程。 如果將皇后置于受到攻擊的位置，算法會(huì)回溯并嘗試不同的位置。 這一直持續(xù)到所有皇后都被放置在棋盤(pán)上且沒(méi)有任何相互攻擊。
8. 隨機(jī)算法：— 隨機(jī)快速排序：隨機(jī)選擇主元的快速排序算法的一種變體。
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]))
這些是每個(gè)程序員都應(yīng)該熟悉的一些最常用的算法。 了解這些算法與它的實(shí)現(xiàn)可以幫助程序員在設(shè)計(jì)和實(shí)現(xiàn)高效解決方案時(shí)做出更好的決策。
