мета-данные страницы
  •  

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Следующая версия		Предыдущая версия
glossary:math:algorithms:merge_sort [2025/09/21 13:25] – создано radi0devglossary:math:algorithms:merge_sort [2025/11/09 12:07] (текущий) – внешнее изменение A User Not Logged in
Строка 19: Строка 19:
  
 Таким образом, в ситуациях, где важна постоянная скорость выполнения независимо от распределения данных, лучше выбирать Merge Sort. Quick Sort может страдать от квадратичной сложности в худших случаях. Таким образом, в ситуациях, где важна постоянная скорость выполнения независимо от распределения данных, лучше выбирать Merge Sort. Quick Sort может страдать от квадратичной сложности в худших случаях.
 +
 +===== Пример реализации =====
 +
 +<code cpp>
 +#include <iostream>
 +#include <vector>
 +
 +// Рекурсивная реализация merge (слияния) двух отсортированных векторов
 +std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
 +  std::vector<int> sorted_list;
 +  sorted_list.reserve(left.size() + right.size());
 +
 +  size_t i = 0, j = 0;
 +  // Сравниваем элементы левой и правой части и сливаем их в один вектор
 +  while (i < left.size() && j < right.size()) {
 +    if (left[i] < right[j]) {
 +      sorted_list.push_back(left[i]);
 +      ++i;
 +    } else {
 +      sorted_list.push_back(right[j]);
 +      ++j;
 +    }
 +  }
 +
 +  // Добавляем оставшиеся элементы (одна из частей уже пустая)
 +  while (i < left.size()) {
 +    sorted_list.push_back(left[i]);
 +    ++i;
 +  }
 +  while (j < right.size()) {
 +    sorted_list.push_back(right[j]);
 +    ++j;
 +  }
 +
 +  return sorted_list;
 +}
 +
 +// Рекурсивная реализация merge sort, возвращающая новый вектор
 +std::vector<int> merge_sort(const std::vector<int>& arr) {
 +  if (arr.size() <= 1) return arr; // базовый случай: 0 или 1 элемент
 +
 +  size_t mid = arr.size() / 2;
 +  std::vector<int> left(arr.begin(), arr.begin() + mid);
 +  std::vector<int> right(arr.begin() + mid, arr.end());
 +
 +  // Рекурсивная сортировка левой и правой половин
 +  std::vector<int> sorted_left = merge_sort(left);
 +  std::vector<int> sorted_right = merge_sort(right);
 +
 +  // Слияние отсортированных половин
 +  return merge(sorted_left, sorted_right);
 +}
 +
 +int main() {
 +  std::vector<int> array = {12, 11, 13, 5, 6, 7};
 +  std::vector<int> sorted_array = merge_sort(array);
 +
 +  std::cout << "Отсортированный массив: ";
 +  for (size_t i = 0; i < sorted_array.size(); ++i) {
 +    if (i) std::cout << ", ";
 +    std::cout << sorted_array[i];
 +  }
 +  std::cout << std::endl;
 +  return 0;
 +}
 +</code>