Алгоритмы и структуры данных на C#: полное руководство для новичков

Введение: Почему алгоритмы и структуры данных — основа мастерства в C#

Любой разработчик, который хочет писать эффективный и масштабируемый код на C#, рано или поздно сталкивается с необходимостью понимать, как работают алгоритмы и структуры данных. Это не просто академическая теория — это инструмент, который позволяет выбирать правильное решение для конкретной задачи: будь то поиск элемента в миллионе записей, сортировка списка заказов или обработка данных в реальном времени.

В этой статье мы разберем ключевые концепции на практических примерах C# (.NET). Вы узнаете, что такое сложность алгоритмов (Big O), какие структуры данных встроены в .NET, и как их использовать. Материал рассчитан на новичков: мы начнем с простого и постепенно углубимся в детали.

1. Основы: Что такое структуры данных и алгоритмы в C#

1.1 Понятие структуры данных

Структура данных — это способ организации и хранения данных в памяти компьютера. В C# (.NET) у нас есть как встроенные структуры (массивы, списки, словари), так и возможность создавать собственные. Правильный выбор структуры напрямую влияет на производительность приложения.

1.2 Понятие алгоритма

Алгоритм — это последовательность шагов для решения задачи. Например, алгоритм сортировки пузырьком или бинарный поиск. Важно не просто знать, как написать код, но и понимать, какой алгоритм выбрать для конкретного объема данных.

1.3 Оценка сложности (Big O Notation)

Big O описывает, как время выполнения алгоритма растет при увеличении входных данных. Основные обозначения:

• O(1) — константное время (доступ к элементу массива по индексу)
• O(n) — линейное время (поиск в неотсортированном списке)
• O(log n) — логарифмическое время (бинарный поиск)
• O(n²) — квадратичное время (пузырьковая сортировка)

В C# для измерения времени выполнения можно использовать System.Diagnostics.Stopwatch.

using System.Diagnostics;

int[] data = { 5, 3, 8, 1, 9 };
Stopwatch sw = Stopwatch.StartNew();
Array.Sort(data); // Встроенная сортировка O(n log n)
sw.Stop();
Console.WriteLine($"Сортировка заняла: {sw.ElapsedMilliseconds} мс");

2. Основные структуры данных в C# (.NET)

2.1 Массивы (Array)

Массив — это фиксированный набор элементов одного типа. В C# массивы индексируются с нуля. Идеально подходят, когда количество элементов известно заранее.

int[] numbers = new int[5] { 10, 20, 30, 40, 50 };
Console.WriteLine(numbers[2]); // Вывод: 30
// Попытка выйти за границы вызовет IndexOutOfRangeException

Когда использовать: для быстрого доступа по индексу (O(1)). Не подходит для частого добавления/удаления элементов.

2.2 Список (List<T>)

Динамический массив из пространства имен System.Collections.Generic. Автоматически расширяется при добавлении элементов. Это одна из самых популярных структур в C#.

List<string> fruits = new List<string>();
fruits.Add("Яблоко");
fruits.Add("Банан");
fruits.Insert(1, "Апельсин"); // Вставка на позицию 1
Console.WriteLine(fruits.Count); // Вывод: 3

Когда использовать: когда нужно часто добавлять элементы в конец списка (амортизированная O(1)). Вставка в середину — O(n).

2.3 Словарь (Dictionary<TKey, TValue>)

Коллекция "ключ-значение", основанная на хеш-таблице. Позволяет быстро искать значение по ключу.

Dictionary<string, int> ages = new Dictionary<string, int>();
ages["Анна"] = 25;
ages["Борис"] = 30;

if (ages.ContainsKey("Анна"))
{
    Console.WriteLine($"Возраст Анны: {ages["Анна"]}"); // Вывод: 25
}

Когда использовать: для поиска по уникальному ключу (O(1) в среднем). Не гарантирует порядок хранения.

2.4 Стек (Stack<T>) и Очередь (Queue<T>)

Стек работает по принципу LIFO (последним пришел — первым ушел). Очередь — FIFO (первым пришел — первым ушел).

// Стек
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
Console.WriteLine(stack.Pop()); // Вывод: 2

// Очередь
Queue<string> queue = new Queue<string>();
queue.Enqueue("Первый");
queue.Enqueue("Второй");
Console.WriteLine(queue.Dequeue()); // Вывод: Первый

Когда использовать: стек — для алгоритмов обхода (DFS), очередь — для обработки задач в порядке поступления (BFS).

3. Классические алгоритмы на C#

3.1 Линейный и бинарный поиск

Линейный поиск (O(n)) работает на любом массиве. Бинарный (O(log n)) — только на отсортированном, но гораздо быстрее.

// Линейный поиск
int LinearSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
        if (arr[i] == target) return i;
    return -1;
}

// Бинарный поиск (массив должен быть отсортирован!)
int BinarySearch(int[] arr, int target)
{
    int left = 0, 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;
}

// Пример использования
int[] sorted = { 1, 3, 5, 7, 9 };
Console.WriteLine(BinarySearch(sorted, 7)); // Вывод: 3

3.2 Сортировка пузырьком (Bubble Sort)

Простой, но медленный алгоритм (O(n²)). Полезен для понимания принципов сортировки.

void BubbleSort(int[] arr)
{
    int