Сортировки
Сводная таблица алгоритмов сортировки по уровням сложности.
🟢 Начальный уровень
| Алгоритм | Сложность | In-Place | Stable | Лучший | Средний | Худший | Память | Примечание |
|---|
| Bubble Sort | O(n²) | ✅ | ✅ | O(n) | O(n²) | O(n²) | O(1) | Самый простой |
| Selection Sort | O(n²) | ✅ | ❌ | O(n²) | O(n²) | O(n²) | O(1) | Минимум swap |
| Insertion Sort | O(n²) | ✅ | ✅ | O(n) | O(n²) | O(n²) | O(1) | Для малых массивов |
🟡 Средний уровень
| Алгоритм | Сложность | In-Place | Stable | Лучший | Средний | Худший | Память | Примечание |
|---|
| Shell Sort | O(n^1.5) | ✅ | ❌ | O(n log n) | O(n^1.5) | O(n²) | O(1) | Улучшенный Insertion |
| Tree Sort | O(n log n) | ❌ | ❌ | O(n log n) | O(n log n) | O(n²) | O(n) | Использует BST |
| Merge Sort | O(n log n) | ❌ | ✅ | O(n log n) | O(n log n) | O(n log n) | O(n) | Гарантированная сложность |
| Quick Sort | O(n log n) | ✅ | ❌ | O(n log n) | O(n log n) | O(n²) | O(log n) | Быстрый на практике |
| Heap Sort | O(n log n) | ✅ | ❌ | O(n log n) | O(n log n) | O(n log n) | O(1) | Для real-time систем |
| Counting Sort | O(n+k) | ❌ | ✅ | O(n+k) | O(n+k) | O(n+k) | O(k) | Малый диапазон |
| Bucket Sort | O(n+k) | ❌ | ✅ | O(n+k) | O(n+k) | O(n²) | O(n+k) | Равномерное распределение |
🔴 Продвинутый уровень
| Алгоритм | Сложность | In-Place | Stable | Лучший | Средний | Худший | Память | Примечание |
|---|
| Radix Sort | O(d·(n+b)) | ❌ | ✅ | O(d·(n+b)) | O(d·(n+b)) | O(d·(n+b)) | O(n+b) | Поразрядная сортировка |
| IntroSort | O(n log n) | ✅ | ❌ | O(n log n) | O(n log n) | O(n log n) | O(log n) | C++ STL std::sort |
| TimSort | O(n log n) | ❌ | ✅ | O(n) | O(n log n) | O(n log n) | O(n) | Python/Java встроенный |
| Cube Sort | O(n log n) | ❌ | ❌ | O(n log n) | O(n log n) | O(n log n) | O(n) | Параллельный алгоритм |
Обозначения:
- In-Place: не требует дополнительной памяти O(n)
- Stable: сохраняет относительный порядок равных элементов
- k: размер диапазона значений (для Counting/Bucket Sort)
- d: количество разрядов (для Radix Sort)
- b: основание системы счисления (для Radix Sort)
Дерево решений: какой алгоритм выбрать?
Начало
│
├─ Учебная задача?
│ └─ ДА → 🟢 Bubble/Insertion Sort
│
├─ Целые числа в малом диапазоне (k ≈ n)?
│ └─ ДА → 🟡 Counting Sort
│
├─ Целые числа с малым d разрядов?
│ └─ ДА → 🟠 Radix Sort
│
├─ Float [0,1) равномерные?
│ └─ ДА → 🟡 Bucket Sort
│
├─ Массив < 50?
│ └─ ДА → 🟢 Insertion Sort
│
├─ Массив 50-1000?
│ └─ ДА → 🟡 Shell Sort
│
├─ Динамические вставки + поиск?
│ └─ ДА → 🟠 Tree Sort (с балансировкой)
│
├─ Параллельные вычисления?
│ └─ ДА → 🔴 Cube Sort
│
├─ Почти отсортированный?
│ └─ ДА → 🔴 TimSort или 🟢 Insertion Sort
│
├─ Нужна стабильность?
│ ├─ Есть память → 🟠 Merge Sort
│ └─ Нет памяти → НЕТ стабильных in-place O(n log n)
│
├─ Гарантированная O(n log n)?
│ ├─ Есть память → 🟠 Merge Sort
│ └─ Нет памяти → 🔴 IntroSort или 🟡 Heap Sort
│
├─ Production код C++?
│ └─ ДА → 🔴 IntroSort (std::sort)
│
├─ Production код Python/Java?
│ └─ ДА → 🔴 TimSort (встроенная)
│
└─ Общий случай?
└─ 🟠 Quick Sort или 🔴 IntroSort
См. также
Полезные ссылки