JavaScript является важнейшим языком веб-разработки и по-прежнему пользуется большим спросом. Разработчику JavaScript важно постоянно улучшать свои навыки и быть в курсе новейших методов и алгоритмов.
В этой статье мы познакомим вас с 10 лучшими алгоритмами, которые мгновенно улучшат ваши навыки работы с JavaScript и выведут ваши навыки программирования на новый уровень. От алгоритмов сортировки, таких как быстрая сортировка и сортировка слиянием, до динамического программирования и поиска с возвратом, вы получите более глубокое понимание того, как решать сложные вычислительные задачи и писать эффективный код. Независимо от того, являетесь ли вы новичком или опытным разработчиком, эти алгоритмы помогут вам стать лучшим программистом на JavaScript и достичь своих карьерных целей. Итак, давайте погрузимся!
1. Алгоритмы сортировки:
Алгоритмы сортировки являются важным аспектом информатики и широко используются в различных приложениях.
Пузырьковая сортировка. Пузырьковая сортировка — это простой алгоритм сортировки, который работает путем многократной замены соседних элементов, если они расположены в неправильном порядке.
Алгоритм продолжается до тех пор, пока массив не будет отсортирован. Пузырьковая сортировка имеет временную сложность O(n²), что делает ее неэффективной для больших массивов. Однако он может быть полезен для небольших массивов и в качестве учебного пособия.
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
const arr = [10, 7, 8, 9, 1, 5];
console.log(bubbleSort(arr));
Быстрая сортировка. Быстрая сортировка — это алгоритм «разделяй и властвуй», который работает путем выбора опорного элемента и разделения других элементов на два подмассива в зависимости от того, меньше они или больше опорного.
Затем подмассивы сортируются рекурсивно. Быстрая сортировка имеет среднюю временную сложность O (n log n), что делает ее одним из самых быстрых алгоритмов сортировки.
function quickSort(arr, low, high) {
if (low < high) {
let pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
function partition(arr, low, high) {
let pivot = arr[high];
let i = low - 1;
for (let j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
let temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
const arr = [10, 7, 8, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);
console.log(arr);
Сортировка слиянием: Сортировка слиянием — это еще один алгоритм «разделяй и властвуй», который работает путем деления несортированного списка на n подсписков, каждый из которых содержит один элемент, а затем многократного слияния подсписков для создания новых отсортированных подсписков, пока не останется только один оставшийся подсписок.
Сортировка слиянием имеет временную сложность O(n log n), что делает его стабильным и эффективным алгоритмом сортировки.
function mergeSort(arr) {
if (arr.length === 1) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
const arr = [10, 7, 8, 9, 1, 5];
console.log(mergeSort(arr));
2. Алгоритмы поиска:
Линейный поиск: простой алгоритм поиска, последовательно проверяющий каждый элемент массива до тех пор, пока не будет найдено нужное значение или не будет достигнут конец массива.
function linearSearch(arr, x) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === x) {
return i;
}
}
return -1;
}
Двоичный поиск: более быстрый алгоритм поиска, который делит массив пополам с каждой итерацией, пока не будет найдено нужное значение или не станет ясно, что значение отсутствует в массиве.
function binarySearch(arr, x) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((right + left) / 2);
if (arr[mid] === x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
3. Алгоритмы динамического программирования:
Ряд Фибоначчи: классическая задача динамического программирования, чтобы найти n-е число в последовательности Фибоначчи.
function fibonacci(n) {
var f = [];
f[0] = 0;
f[1] = 1;
for (var i = 2; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
Объяснение: Решение использует массив для хранения промежуточных результатов, чтобы избежать пересчета значений.
Самая длинная общая подпоследовательность (LCS): Алгоритм динамического программирования, который находит самую длинную последовательность, общую для двух или более строк.
function lcs(str1, str2) {
let m = str1.length;
let n = str2.length;
let dp = new Array(m + 1);
for (let i = 0; i <= m; i++) {
dp[i] = new Array(n + 1).fill(0);
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
4. Графические алгоритмы:
Поиск в ширину: алгоритм обхода графа для посещения всех вершин на одном уровне перед посещением вершин на более глубоком уровне.
function BFS(graph, start) {
var queue = [];
var visited = new Set();
queue.push(start);
visited.add(start);
while (queue.length != 0) {
var node = queue.shift();
console.log(node);
for (var i = 0; i < graph[node].length; i++) {
var neighbor = graph[node][i];
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
Объяснение: Решение использует очередь для хранения вершин и набор для хранения посещенных вершин.
Использование в реальных условиях: можно использовать для поиска кратчайшего пути на невзвешенном графе, например, при сетевой коммуникации или для нахождения минимального количества шагов в игре.
Поиск в глубину: алгоритм обхода графа для посещения вершины, а затем посещения всех вершин на более глубоком уровне перед возвратом.
function DFS(graph, node, visited) {
visited[node] = true;
console.log(node);
for (var i = 0; i < graph[node].length; i++) {
var neighbor = graph[node][i];
if (!visited[neighbor]) {
DFS(graph, neighbor, visited);
}
}
}
Объяснение: В решении используется рекурсивный подход и массив для хранения посещенных вершин.
Использование в реальных условиях: может использоваться для топологической сортировки, обнаружения циклов и поиска сильно связанных компонентов в графе.
5. Алгоритмы дерева:
Двоичное дерево поиска (BST): древовидная структура данных, в которой значение каждого узла больше, чем все значения в его левом поддереве, и меньше, чем все значения в его правом поддереве.
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
insert(data) {
var newNode = new Node(data);
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
if (newNode.data < node.data) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
}
}
}
Объяснение: Решение реализует класс для Node и BST, где каждый узел имеет данные и свойства left/right. Класс BST имеет методы для вставки узла и рекурсивной вставки узла.
Использование в реальных условиях: может эффективно использоваться для поиска, сортировки и нахождения k-го наименьшего/наибольшего элемента в наборе данных.
6. Алгоритмы «разделяй и властвуй»
Алгоритмы «разделяй и властвуй» — это класс алгоритмов, которые разбивают проблему на более мелкие подзадачи, а затем решают каждую подзадачу независимо.
//Example: Merge Sort using Divide and Conquer Algorithm in JavaScript
function mergeSort(arr) {
if (arr.length === 1) {
return arr;
}
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
while (i < left.length) {
result.push(left[i]);
i++;
}
while (j < right.length) {
result.push(right[j]);
j++;
}
return result;
}
В приведенном выше примере алгоритм сортировки слиянием использует этот метод для сортировки массива, разделяя его на более мелкие массивы и затем объединяя их в отсортированном виде.
Использование в реальных условиях: используется во многих алгоритмах, таких как быстрая сортировка, двоичный поиск, умножение матриц Штрассена, ближайшая пара точек и т. д.
7. Жадные алгоритмы:
Жадные алгоритмы — это класс алгоритмов, которые делают лучший выбор на каждом шаге в надежде найти глобальный оптимум. Идея жадного алгоритма состоит в том, чтобы на каждом этапе выбирать локально оптимальное решение в надежде найти глобально оптимальное решение.
В JavaScript жадные алгоритмы могут использоваться для решения различных задач оптимизации, таких как задача о дробном рюкзаке и задача выбора действий.
Вот пример того, как вы можете использовать жадный алгоритм для решения задачи выбора действий:
function activitySelection(start, finish) {
let i = 0;
let j;
const result = [i];
for (j = 1; j < start.length; j++) {
if (start[j] >= finish[i]) {
result.push(j);
i = j;
}
}
return result;
}
const start = [1, 3, 0, 5, 8, 5];
const finish = [2, 4, 6, 7, 9, 9];
console.log(activitySelection(start, finish));
В этом примере функция activitySelection принимает два массива, start и finish, представляющие время начала и окончания действий. Функция реализует жадный алгоритм для нахождения максимального количества действий, которые может выполнить один человек, предполагая, что человек может выполнять только одно действие за раз. Функция сначала выбирает первое действие и добавляет его к результату. Затем он выполняет итерацию по остальным действиям и выбирает действие, если его время начала больше или равно времени окончания последнего выбранного действия.
Это базовый пример того, как можно использовать жадный алгоритм для решения задачи выбора действий. Этот метод можно применять для решения более сложных задач оптимизации, определяя локально оптимальное решение на каждом этапе и находя глобально оптимальное решение, делая наилучший выбор на каждом этапе.
В реальных приложениях жадные алгоритмы широко используются для планирования задач, поиска кратчайшего пути в графе и для решения различных других задач оптимизации.
8. Алгоритмы обратного отслеживания
Поиск с возвратом — это алгоритмический метод, используемый для постепенного поиска всех (или некоторых) решений проблемы путем перебора возможностей и «возврата», когда решение не может быть найдено. В JavaScript поиск с возвратом можно использовать для решения различных задач, таких как поиск всех возможных комбинаций элементов в массиве или поиск решения такой головоломки, как задача N-ферзей или средство решения судоку.
Вот пример того, как вы можете использовать поиск с возвратом для поиска всех возможных комбинаций элементов в массиве: scssСкопировать код
function backtrack(arr, curr, result) {
if (curr.length === arr.length) {
result.push([...curr]);
return;
}
for (let i = 0; i < arr.length; i++) {
if (!curr.includes(arr[i])) {
curr.push(arr[i]);
backtrack(arr, curr, result);
curr.pop();
}
}
}
function findCombinations(arr) {
const result = [];
backtrack(arr, [], result);
return result;
}
const arr = [1, 2, 3];
console.log(findCombinations(arr));
В этом примере функция backtrack принимает массив arr, массив curr для хранения текущей комбинации и массив result для хранения всех найденных комбинаций. Сначала функция проверяет, равна ли длина curr длине arr, и в этом случае она помещает копию curr в массив result. Если нет, он перебирает arr и помещает элемент в curr, если он еще не находится в curr, а затем снова вызывает backtrack. Если решение не может быть найдено, он извлекает последний элемент из curr и переходит к следующему элементу в arr.
Это базовый пример того, как можно использовать поиск с возвратом для поиска всех возможных комбинаций элементов в массиве. Технику можно применять для решения более сложных задач, определяя условия решения и критерии того, когда следует «возвратиться».
9. Алгоритмы битовых манипуляций
Алгоритмы обработки битов используют побитовые операции для управления отдельными битами числа.
//Example: Bit Manipulation Algorithm to Check if a Number is a Power of Two in JavaScript
function isPowerOfTwo(n) {
return (n & (n - 1)) === 0;
}
В приведенном выше примере алгоритм проверяет, является ли число степенью двойки, используя побитовый оператор И для сравнения числа и числа минус один. Если результат равен нулю, то число является степенью двойки.
//Example: Bit Manipulation Algorithm to Count Set Bits in a Number in JavaScript
function countSetBits(n) {
let count = 0;
while (n > 0) {
count += n & 1;
n = n >> 1;
}
return count;
}
//Example: Bit Manipulation Algorithm to Multiply Two Numbers Without Using * Operator in JavaScript
function multiply(a, b) {
let result = 0;
while (b > 0) {
if (b & 1) {
result += a;
}
a <<= 1;
b >>= 1;
}
return result;
}
Объяснение: В первом примере алгоритм использует цикл while и побитовый оператор И для подсчета количества установленных битов в числе. Во втором примере алгоритм использует побитовые операторы сдвига влево и вправо для умножения двух чисел без использования оператора *.
Реальное использование: Алгоритмы Bit Manipulation используются в различных областях, таких как компьютерная графика, сжатие данных, криптография, обнаружение и исправление ошибок и многое другое.
10. Строковые алгоритмы
Строковые алгоритмы — это алгоритмы, предназначенные для обработки и управления строками, представляющими собой последовательности символов.
//Example: Longest Palindromic Substring Algorithm in JavaScript
function longestPalindromicSubstring(s) {
let longest = "";
for (let i = 0; i < s.length; i++) {
let sub1 = expandAroundCenter(s, i, i);
let sub2 = expandAroundCenter(s, i, i + 1);
let longestSub = sub1.length > sub2.length ? sub1 : sub2;
if (longestSub.length > longest.length) {
longest = longestSub;
}
}
return longest;
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.slice(left + 1, right);
}
В приведенном выше примере используется вариант алгоритма Манахера для поиска самой длинной палиндромной подстроки в строке.
//Example: Rabin-Karp Algorithm for Pattern Searching in JavaScript
function rabinKarp(text, pattern) {
let q = 101;
let d = 256;
let n = text.length;
let m = pattern.length;
let h = 1;
let p = 0;
let t = 0;
let result = [];
for (let i = 0; i < m - 1; i++) {
h = (h * d) % q;
}
for (let i = 0; i < m; i++) {
p = (d * p + pattern.charCodeAt(i)) % q;
t = (d * t + text.charCodeAt(i)) % q;
}
for (let i = 0; i <= n - m; i++) {
if (p === t) {
let j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) !== pattern.charAt(j)) {
break;
}
}
if (j === m) {
result.push(i);
}
}
if (i < n - m) {
t = (d * (t - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % q;
if (t < 0) {
t = (t + q);
}
}
}
return result;
}
В приведенном выше примере используется алгоритм Рабина-Карпа для поиска всех вхождений шаблона в тексте. Алгоритм использует хеш-функцию для быстрого сравнения хеш-значений шаблона и подстрок текста.
Реальное использование: строковые алгоритмы используются в различных приложениях, таких как редактирование текста, распознавание образов, сжатие данных и многое другое.
Помните, что путь к тому, чтобы стать лучшим разработчиком, никогда не заканчивается, и всегда есть место для роста и совершенствования. Удачи на пути к тому, чтобы стать мастером JavaScript!
Дополнительные материалы на PlainEnglish.io.
Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter, LinkedIn, YouTube и Discord .
Заинтересованы в масштабировании запуска вашего программного обеспечения? Ознакомьтесь с разделом Схема.
