Вот несколько методов, обычно используемых в информатике и технике, а также примеры кода:
- Пузырьковая сортировка.
Пузырьковая сортировка – это простой алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Вот пример на Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print(sorted_arr)
- Двоичный поиск.
Двоичный поиск – это эффективный алгоритм поиска, используемый для поиска определенного целевого значения в отсортированной последовательности. Вот пример на Java:
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
// Example usage
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int result = binarySearch(arr, target);
System.out.println("Element found at index: " + result);
}
}
- Поиск в глубину (DFS).
DFS — это алгоритм для обхода или поиска в структурах данных в виде дерева или графа. Он исследует как можно дальше каждую ветвь, прежде чем вернуться назад. Вот пример на C++:
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited) {
visited[node] = true;
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
dfs(graph, neighbor, visited);
}
}
}
// Example usage
int main() {
int numNodes = 7;
vector<vector<int>> graph(numNodes);
graph[0] = {1, 2};
graph[1] = {0, 3, 4};
graph[2] = {0, 5, 6};
graph[3] = {1};
graph[4] = {1};
graph[5] = {2};
graph[6] = {2};
vector<bool> visited(numNodes, false);
cout << "DFS traversal: ";
dfs(graph, 0, visited);
return 0;
}