Алгоритмы сортировки в C# (.NET): подробное руководство

Что это такое и зачем? (аналогия из реальной жизни)

Представьте, что вы — учитель физкультуры, и у вас есть стопка карточек с результатами бега на 100 метров. Карточки лежат в беспорядке: сначала Петя (12.5 сек), потом Маша (11.2 сек), потом Вася (15.1 сек). Чтобы узнать, кто самый быстрый, вам нужно упорядочить эти карточки по времени — от лучшего к худшему. Это и есть сортировка.

В программировании сортировка — это процесс перестановки элементов массива или списка в определенном порядке (обычно по возрастанию или убыванию). Зачем это нужно? Представьте, что у вас есть телефонная книга с 1000 контактов, но они записаны в том порядке, в котором вы их добавляли. Найти «Иванова» будет очень сложно. А если отсортировать по алфавиту — всё становится просто.

Сортировка — это базовый навык, который используется везде: от поиска в Google до сортировки фотографий по дате в телефоне. Без неё не обходится ни одна серьёзная программа.

В реальной жизни мы постоянно сортируем: раскладываем книги по алфавиту, сортируем одежду по цветам, упорядочиваем дела по срочности. Компьютеры делают то же самое, но гораздо быстрее — миллионы элементов за доли секунды.

Теория: как это работает изнутри

Давайте заглянем «под капот» и разберемся, как компьютер понимает, какой элемент больше, а какой меньше. В основе любой сортировки лежит сравнение. Мы берем два элемента и спрашиваем: «А больше ли первый второго?» Если да — меняем их местами. Если нет — оставляем как есть.

Но просто сравнивать все подряд — неэффективно. Представьте, что у вас 1000 чисел, и вы сравниваете каждое с каждым. Это 1 000 000 операций! Умные алгоритмы делают это хитрее.

Основные виды сортировок (краткий обзор)

Название	Сложность (время)	Как работает (очень кратко)
Пузырьковая (Bubble Sort)	O(n²) — медленно	«Всплывает» самый большой элемент, как пузырек в воде
Вставками (Insertion Sort)	O(n²) — средне	Как раскладывание карт в руке: берем карту и вставляем в нужное место
Выбором (Selection Sort)	O(n²) — средне	Ищем самый маленький элемент и ставим его в начало
Быстрая (Quick Sort)	O(n log n) — быстро	Делим массив пополам, сортируем каждую половину отдельно
Слиянием (Merge Sort)	O(n log n) — быстро	Делим до одного элемента, потом собираем обратно уже отсортированным

Важно: O(n²) — это «квадратичная сложность». Если элементов 10, нужно 100 операций. Если 1000 — 1 000 000. O(n log n) — «линейно-логарифмическая». Для 1000 элементов нужно всего ~10 000 операций. Разница огромна!

Как компьютер сравнивает элементы?

В C# для сравнения используется интерфейс IComparable или делегат Comparison. По умолчанию числа сравниваются по значению, строки — по алфавиту (лексикографически). Но вы можете написать свою логику сравнения — например, сортировать людей по возрасту, а не по имени.

Синтаксис в C# (.NET): все формы и варианты

В C# есть несколько способов отсортировать данные. Давайте разберем их все — от самых простых до более сложных.

1. Встроенный метод Array.Sort()

Самый простой способ для массивов. Работает «из коробки» для чисел, строк и других встроенных типов.

int[] numbers = { 5, 3, 8, 1, 9 };
Array.Sort(numbers); // Теперь numbers = { 1, 3, 5, 8, 9 }
// Сортировка происходит "на месте" — исходный массив изменяется

2. Метод List.Sort()

Для списков (List) есть свой метод Sort(). Работает аналогично.

List<string> names = new List<string> { "Иван", "Анна", "Петр" };
names.Sort(); // Теперь: "Анна", "Иван", "Петр"

3. LINQ: OrderBy() и OrderByDescending()

Самый гибкий способ. Не изменяет исходную коллекцию, а возвращает новую отсортированную.

int[] numbers = { 5, 3, 8, 1, 9 };
var sorted = numbers.OrderBy(n => n).ToArray(); // { 1, 3, 5, 8, 9 }
var sortedDesc = numbers.OrderByDescending(n => n).ToArray(); // { 9, 8, 5, 3, 1 }

4. Сортировка с пользовательским компаратором

Когда нужно отсортировать по своим правилам (например, по длине строки).

string[] words = { "кот", "слон", "я", "бегемот" };
Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));
// Результат: "я", "кот", "слон", "бегемот" (по возрастанию длины)

5. Сортировка объектов по свойству

Чаще всего мы работаем не с числами, а с объектами. Например, сортируем список студентов по возрасту.

public class Student {
    public string Name { get; set; }
    public int Age { get; set; }
}

List<Student> students = new List<Student> {
    new Student { Name = "Петя", Age = 20 },
    new Student { Name = "Маша", Age = 18 },
    new Student { Name = "Вася", Age = 22 }
};

// Сортируем по возрасту
students.Sort((s1, s2) => s1.Age.CompareTo(s2.Age));

6. Реализация IComparable

Если вы хотите, чтобы ваш класс «умел» сортироваться по умолчанию.

public class Student : IComparable<Student> {
    public string Name { get; set; }
    public int Age { get; set; }
    
    public int CompareTo(Student other) {
        return this.Age.CompareTo(other.Age); // По возрасту
    }
}

// Теперь можно просто: students.Sort();

Примеры кода — от простого к сложному

Теперь давайте напишем 7 полноценных примеров. Каждый пример — это рабочая программа, которую можно скопировать и запустить.

Пример 1: Пузырьковая сортировка (Bubble Sort) — для понимания основ

using System;

class Program {
    static void Main() {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        
        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
        
        // Внешний цикл — сколько раз проходим по массиву
        for (int i = 0; i < arr.Length - 1; i++) {
            // Внутренний цикл — сравниваем соседние элементы
            for (int j = 0; j < arr.Length - 1 - i; j++) {
                // Если текущий больше следующего — меняем местами
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];       // Запоминаем текущий
                    arr[j] = arr[j + 1];     // На место текущего ставим следующий
                    arr[j + 1] = temp;       // На место следующего ставим текущий
                }
            }
        }
        
        Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
    }
}

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

Пример 2: Сортировка выбором (Selection Sort) — ищем минимум

using System;

class Program {
    static void Main() {
        int[] arr = { 29, 10, 14, 37, 13 };
        
        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
        
        for (int i = 0; i < arr.Length - 1; i++) {
            int minIndex = i; // Считаем, что текущий элемент — минимальный
            
            // Ищем реальный минимальный элемент в оставшейся части
            for (int j = i + 1; j < arr.Length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // Нашли элемент меньше — запоминаем его индекс
                }
            }
            
            // Меняем местами текущий элемент с найденным минимальным
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
        
        Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
    }
}

Объяснение: Мы как бы «выбираем» самый маленький элемент из оставшихся и ставим его в начало. Сначала ищем минимум среди всех элементов, ставим его на первую позицию. Потом ищем минимум среди оставшихся (со второй позиции до конца) — ставим на вторую. И так далее.

Пример 3: Сортировка вставками (Insertion Sort) — как карты в руке

using System;

class Program {
    static void Main() {
        int[] arr = { 12, 11, 13, 5, 6 };
        
        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
        
        for (int i = 1; i < arr.Length; i++) {
            int key = arr[i]; // Элемент, который нужно вставить
            int j = i - 1;    // Индекс предыдущего элемента
            
            // Сдвигаем элементы, которые больше key, вправо
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            
            arr[j + 1] = key; // Вставляем key на освободившееся место
        }
        
        Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
    }
}

Объяснение: Представьте, что вы держите в руке карты. Левая часть руки — уже отсортирована. Вы берете новую карту (key) и вставляете её в правильное место среди отсортированных, сдвигая остальные. Этот алгоритм очень эффективен для почти отсортированных массивов.

Пример 4: Быстрая сортировка (Quick Sort) — рекурсивный подход

using System;

class Program {
    static void Main() {
        int[] arr = { 10, 7, 8, 9, 1, 5 };
        
        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
        
        QuickSort(arr, 0, arr.Length - 1);
        
        Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
    }
    
    static void QuickSort(int[] arr, int left, int right) {
        if (left < right) {
            // Находим опорный элемент и разделяем массив
            int pivotIndex = Partition(arr, left, right);
            
            // Рекурсивно сортируем левую и правую части
            QuickSort(arr, left, pivotIndex - 1);
            QuickSort(arr, pivotIndex + 1, right);
        }
    }
    
    static int Partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // Опорный элемент — последний
        int i = left - 1;       // Индекс меньшего элемента
        
        for (int j = left; j < right; j++) {
            // Если текущий элемент меньше или равен опорному
            if (arr[j] <= pivot) {
                i++;
                // Меняем местами arr[i] и arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // Ставим опорный элемент на правильное место
        int temp2 = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp2;
        
        return i + 1; // Возвращаем индекс опорного элемента
    }
}

Объяснение: Это один из самых быстрых алгоритмов. Идея: выбираем «опорный» элемент (pivot). Все элементы меньше него — слева, все больше — справа. Потом повторяем то же самое для левой и правой частей. Рекурсия продолжается, пока не останутся отрезки из одного элемента (они уже отсортированы).

Пример 5: Сортировка слиянием (Merge Sort) — разделяй и властвуй

using System;

class Program {
    static void Main() {
        int[] arr = { 38, 27, 43, 3, 9, 82, 10 };
        
        Console.WriteLine("Исходный массив: " + string.Join(", ", arr));
        
        MergeSort(arr, 0, arr.Length - 1);
        
        Console.WriteLine("Отсортированный массив: " + string.Join(", ", arr));
    }
    
    static void MergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2; // Находим середину
            
            // Рекурсивно сортируем левую и правую половины
            MergeSort(arr, left, mid);
            MergeSort(arr, mid + 1, right);
            
            // Сливаем две отсортированные половины
            Merge(arr, left, mid, right);
        }
    }
    
    static void Merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // Размер левой половины
        int n2 = right - mid;    // Размер правой половины
        
        // Создаем временные массивы
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        // Копируем данные во временные массивы
        for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];
        
        // Сливаем обратно в основной массив
        int iLeft = 0, iRight = 0, k = left;
        
        while (iLeft < n1 && iRight < n2) {
            if (leftArr[iLeft] <= rightArr[iRight]) {
                arr[k] = leftArr[iLeft];
                iLeft++;
            } else {
                arr[k] = rightArr[iRight];
                iRight++;
            }
            k++;
        }
        
        // Копируем оставшиеся элементы (если есть)
        while (iLeft < n1) {
            arr[k] = leftArr[iLeft];
            iLeft++;
            k++;
        }
        
        while (iRight < n2) {
            arr[k] = rightArr[iRight];
            iRight++;
            k++;
        }
    }
}

Объяснение: Алгоритм работает по принципу «разделяй и властвуй». Делим массив пополам до тех пор, пока не останутся массивы из одного элемента (они уже отсортированы). Потом начинаем собирать их обратно, но уже в правильном порядке. Слияние двух отсортированных массивов — это как слияние двух стопок карт: берем меньшую карту из двух стопок и кладем в общую.

Пример 6: Сортировка объектов с помощью LINQ

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    // Создаем класс для примера
    public class Product {
        public string Name { get; set; }
        public double Price { get; set; }
        public int Rating { get; set; }
    }
    
    static void Main() {
        // Создаем список товаров
        List<Product> products = new List<Product> {
            new Product { Name = "Ноутбук", Price = 75000, Rating = 5 },
            new Product { Name = "Мышь", Price = 1500, Rating = 4 },
            new Product { Name = "Клавиатура", Price = 3000, Rating = 3 },
            new Product { Name = "Монитор", Price = 25000, Rating = 5 }
        };
        
        // Сортировка по цене (по возрастанию)
        var sortedByPrice = products.OrderBy(p => p.Price).ToList();
        Console.WriteLine("Товары по возрастанию цены:");
        foreach (var p in sortedByPrice) {
            Console.WriteLine($"  {p.Name}: {p.Price} руб.");
        }
        
        // Сортировка по рейтингу (по убыванию), затем по цене (по возрастанию)
        var sortedByRatingThenPrice = products
            .OrderByDescending(p => p.Rating)
            .ThenBy(p => p.Price)
            .ToList();
        
        Console.WriteLine("
Товары по рейтингу (сначала лучшие), затем по цене:");
        foreach (var p in sortedByRatingThenPrice) {
            Console.WriteLine($"  {p.Name}: рейтинг {p.Rating}, цена {p.Price} руб.");
        }
    }
}

Объяснение: LINQ (Language Integrated Query) — это мощный инструмент C#. OrderBy сортирует по возрастанию, OrderByDescending — по убыванию. ThenBy позволяет добавить второстепенную сортировку (если первичный ключ совпадает). Важно: LINQ не изменяет исходный список, а создает новый.

Пример 7: Сортировка строк с учетом культуры (для русского языка)

using System;
using System.Collections.Generic;
using System.Globalization;

class Program {
    static void Main() {
        // Строки с русскими буквами
        string[] words = { "ёлка", "еж", "яблоко", "аист", "юла" };
        
        Console.WriteLine("Исходный массив: " + string.Join(", ", words));
        
        // Обычная сортировка (может дать неправильный порядок для русского)
        Array.Sort(words);
        Console.WriteLine("Обычная сортировка: " + string.Join(", ", words));
        
        // Сортировка с учетом русской культуры
        var comparer = StringComparer.Create(new CultureInfo("ru-RU"), false);
        Array.Sort(words, comparer);
        Console.WriteLine("Сортировка с русской культурой: " + string.Join(", ", words));
        
        // Сортировка без учета регистра
        string[] mixed = { "Анна", "анна", "АННА", "аННа" };
        Array.Sort(mixed, StringComparer.OrdinalIgnoreCase);
        Console.WriteLine("Без учета регистра: " + string.Join(", ", mixed));
    }
}

Объяснение: В разных языках буквы сортируются по-разному. Например, в русском «ё» должна идти после «е», но до «ж». Обычная сортировка может этого не учитывать. CultureInfo позволяет задать правила сортировки для конкретного языка. OrdinalIgnoreCase игнорирует регистр (заглавные/строчные).

Сравнение с Python: чем похоже и чем отличается

Если вы уже знакомы с Python или планируете его изучать, вот ключевые различия в подходах к сортировке:

Характеристика	C# (.NET)	Python
Встроенная сортировка массива	Array.Sort(arr) — изменяет исходный массив	arr.sort() — изменяет исходный список
Создание новой отсортированной коллекции	arr.OrderBy(x => x).ToArray() (LINQ)	sorted(arr) — возвращает новый список
Сортировка по убыванию	Array.Sort(arr, (a,b) => b.CompareTo(a)) или OrderByDescending	arr.sort(reverse=True) или sorted(arr, reverse=True)
Пользовательский ключ сортировки	arr.OrderBy(x => x.Length) (лямбда-выражение)	sorted(arr, key=len) (функция или лямбда)
Сортировка объектов по свойству	list.OrderBy(p => p.Age)	sorted(list, key=lambda p: p.age)
Множественная сортировка	OrderBy(...).ThenBy(...)	sorted(list, key=lambda p: (p.rating, -p.price))
Стабильность сортировки	Array.Sort — нестабильная, LINQ — стабильная	sort() и sorted() — стабильные

Что такое стабильность? Если два элемента равны по ключу сортировки, стабильный алгоритм сохраняет их исходный порядок. Нестабильный — может их переставить. Для большинства задач это не важно, но иногда имеет значение.

Главное отличие: В C# больше способов сортировки, и они более строгие (типизированные). В Python всё проще и короче, но меньше контроля. Например, в C# вы не сможете отсортировать массив, содержащий разные типы (числа и строки), а в Python — сможете (но получите ошибку во время выполнения, если сравнение не определено).

Типичные ошибки и подводные камни

Даже опытные программисты иногда попадаются на этих граблях. Вот самые частые ошибки:

Ошибка 1: Забыть, что Array.Sort изменяет исходный массив

int[] original = { 3, 1, 2 };
int[] backup = original; // backup — это НЕ копия, а ссылка на тот же массив!
Array.Sort(original);
// Теперь backup тоже отсортирован! Потому что это один и тот же массив.

Решение: Создавайте копию: int[] backup = (int[])original.Clone();

Ошибка 2: Сортировка списка во время итерации по нему

List<int> numbers = new List<int> { 3, 1, 2 };
foreach (int n in numbers) {
    numbers.Sort(); // Ошибка! Нельзя изменять коллекцию во время foreach
}

Решение: Сортируйте до или после цикла, либо используйте for вместо foreach.

Ошибка 3: Сравнение объектов, которые не реализуют IComparable

public class Person {
    public string Name { get; set; }
}
List<Person> people = new List<Person> { ... };
people.Sort(); // Ошибка компиляции! Person не реализует IComparable

Решение: Либо реализуйте IComparable, либо передавайте компаратор: people.Sort((a,b) => a.Name.CompareTo(b.Name));

Ошибка 4: Путаница между OrderBy и Sort

Array.Sort() и List.Sort() изменяют исходную коллекцию и возвращают void. OrderBy() возвращает новую последовательность и не изменяет исходную. Новички часто пишут:

list.OrderBy(x => x); // Результат никуда не сохранен! Бесполезная операция.

Решение: Всегда сохраняйте результат: var sorted = list.OrderBy(x => x).ToList();

Ошибка 5: Сортировка по убыванию неправильным способом

Array.Sort(arr, (a, b) => a.CompareTo(b) * -1); // Работает, но неочевидно
// Лучше: Array.Sort(arr, (a, b) => b.CompareTo(a));

Ошибка 6: Игнорирование культуры при сортировке строк

Как мы видели в примере 7, русские буквы могут сортироваться неправильно. Особенно это заметно с буквой «ё».

Ошибка 7: Предположение, что все алгоритмы сортировки одинаково быстры

Для 10 элементов разница незаметна. Для 10 000 000 — пузырьковая сортировка будет работать часы, а быстрая — секунды. Всегда выбирайте алгоритм под задачу.

Лучшие практики и советы профессионалов

Вот что советуют опытные разработчики, которые пишут код на C# каждый день:

1. Используйте встроенные методы, когда это возможно

Не изобретайте велосипед. Array.Sort(), List.Sort() и LINQ-методы оптимизированы Microsoft и работают очень быстро. Пишите свою сортировку только в учебных целях или если у вас очень специфические требования.

2. Для сложных объектов используйте LINQ

LINQ-выражения читаются легче, чем компараторы. Сравните:

// Плохо (трудно читать)
students.Sort((a, b) => {
    int result = a.Age.CompareTo(b.Age);
    if (result == 0) result = a.Name.CompareTo(b.Name);
    return result;
});

// Хорошо (понятно с первого взгляда)
var sorted = students.OrderBy(s => s.Age).ThenBy(s => s.Name);

3. Для больших массивов — используйте параллельную сортировку

В .NET есть ParallelSort (через System.Threading.Tasks.Parallel), который использует все ядра процессора. Но помните: параллельная сортировка имеет накладные расходы, поэтому для маленьких массивов (менее 10 000 элементов) она может быть медленнее.

4. Сортируйте как можно раньше

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

5. Используйте IComparable для доменных классов

Если ваш класс имеет «естественный» порядок (например, дата для события), реализуйте IComparable. Это сделает код чище и позволит использовать ваш класс в любых сортировках без дополнительных настроек.

6. Будьте осторожны с сортировкой по нескольким ключам

Помните, что ThenBy применяется только когда предыдущие ключи равны. Если вам нужно сортировать сначала по одному полю, а потом по другому, используйте OrderBy + ThenBy.

7. Тестируйте на граничных случаях

Всегда проверяйте сортировку на:

• Пустом массиве
• Массиве из одного элемента
• Массиве, где все элементы равны
• Массиве, который уже отсортирован
• Массиве, отсортированном в обратном порядке

Вопросы для самопроверки

Проверьте, как хорошо вы усвоили материал. Ответы спрятаны под спойлером — попробуйте ответить сначала сами.

1. Что такое «стабильная сортировка» и почему это может быть важно?
2. Какая сложность у пузырьковой сортировки в лучшем, среднем и худшем случае?
3. В чем разница между Array.Sort() и Enumerable.OrderBy()?
4. Как отсортировать список строк по убыванию длины?
5. Почему быстрая сортировка называется «быстрой»? Всегда ли она самая быстрая?
6. Что произойдет, если вызвать Sort() на списке, элементы которого не реализуют IComparable?
7. Как отсортировать массив объектов сначала по возрасту (по возрастанию), а потом по имени (по убыванию)?
8. В чем отличие сортировки в C# от сортировки в Python?
9. Какая ошибка возникает при попытке изменить коллекцию во время foreach?
← Предыдущая Регулярные выражения в C# (.NET): подробное руково Вперёд → Алгоритмы поиска в C# (.NET): подробное руководств