Какие алгоритмы сортировки ты знаешь в контексте C++?

А, ну вот, сортировки, говоришь? Да я с ними, блядь, как с родными братьями, ёпта. Всю жизнь их на C++ пишу, то стандартными пользуюсь, то сам с нуля выёбываюсь, когда задача специфическая. Сейчас тебе всё по полочкам разложу, только не усни.

1. Ну, первое — это стандартная библиотека, там всё готовое.

#include <algorithm>
#include <vector>

std::vector<int> data = {5, 2, 8, 1, 9};

// Обычная быстрая сортировка, хитрая жопа, внутри там гибрид
std::sort(data.begin(), data.end());

// Стабильная — если порядок равных элементов важен, чтоб не перепутались
std::stable_sort(data.begin(), data.end());

// Частичная — когда тебе надо только топ-3, а на остальное похуй
std::partial_sort(data.begin(), data.begin() + 3, data.end());

// N-th element — типа разделил массив, чтоб слева были меньше, справа больше. Удобно для медиан.
std::nth_element(data.begin(), data.begin() + 2, data.end());

2. Базовые алгоритмы, которые самому писать приходилось.

Bubble Sort (O(n²), медленный как черепаха):

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break; // оптимизация для почти отсортированных
    }
}

Этот, конечно, для учебников, на практике его используют, только если мозгов не хватает или данных овердохуища мало.

Quick Sort (O(n log n) в среднем, но может и в O(n²) скатиться, если не повезёт):

template<typename T>
int partition(std::vector<T>& arr, int low, int high) {
    T pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

template<typename T>
void quick_sort(std::vector<T>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

Вот это уже серьёзная вещь, основа основ. Только опорный элемент (pivot) надо умно выбирать, а то будет тебе хиросима.

Merge Sort (O(n log n), стабильный, но памяти жрёт):

template<typename T>
void merge(std::vector<T>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<T> L(n1), R(n2);

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i++];
        } else {
            arr[k] = R[j++];
        }
        k++;
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

Стабильный, надёжный, как швейцарские часы. Для связных списков — вообще красота.

3. Специализированные штуки для C++.

Heap Sort через std::make_heap:

void heap_sort(std::vector<int>& arr) {
    // Делаем из вектора кучу (max-heap)
    std::make_heap(arr.begin(), arr.end());

    // Вытаскиваем максимальный и перестраиваем
    for (auto it = arr.end(); it != arr.begin(); --it) {
        std::pop_heap(arr.begin(), it);
    }
}

Элегантно, блядь, и не надо городить свой велосипед.

4. А вот табличка, чтоб не ебать себе мозг при выборе:

5. Из практики — как оптимизировать, чтоб летало.

• Insertion Sort для мелких подмассивов внутри Quick Sort — так std::sort и делает, умные ребята.
• Introsort — это гибрид, который в STL и используется: Quick Sort, а если рекурсия глубоко пошла — переключается на Heap Sort, чтоб не скатиться в O(n²). Хитрая жопа, я тебе скажу.
• Сортировать указатели, а не целые объекты, если они размером с хуй в пальто.

• Radix Sort для целых чисел, если диапазон известен — быстрее некуда:

  void radix_sort(std::vector<int>& arr) {
  const int BASE = 10;
  int max_val = *std::max_element(arr.begin(), arr.end());
  
  for (int exp = 1; max_val / exp > 0; exp *= BASE) {
      std::vector<int> output(arr.size());
      std::array<int, BASE> count = {0};
  
      for (int num : arr) {
          count[(num / exp) % BASE]++;
      }
  
      for (int i = 1; i < BASE; i++) {
          count[i] += count[i - 1];
      }
  
      for (int i = arr.size() - 1; i >= 0; i--) {
          int digit = (arr[i] / exp) % BASE;
          output[count[digit] - 1] = arr[i];
          count[digit]--;
      }
  
      arr = std::move(output);
  }
  }

6. Фишки C++, без которых никуда.

• Свой компаратор запихнуть — вообще ерунда:

  
  struct Person {
  std::string name;
  int age;
  };

std::vector people; // Сортируем по возрасту, старики вперёд std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) { return a.age < b.age; });

*   В C++20 появился `std::ranges::sort` — ещё красивее.
*   Move-семантика для тяжёлых объектов — чтоб не копировать их, как дуракам.
*   В C++17 можно параллельную сортировку включить через execution policies — если ядер много, то вали, ебать колотить.

В общем, инструментов — овердохуища. Главное — понимать, что за задача, а там уже выбирай: или `std::sort` рулит, или надо свою мартышлюшку писать.