Question

СРОЧНО!!!ПОМОГИТЕ!!!СИРИУС!!!С++ Сортировка слиянием Отсортируйте данный массив, используя сортировку слиянием. Попробуйте написать свою реализацию, например, не создавая новые векторы при каждом рекурсивном вызове. Входные данные Первая строка входных данных содержит количество элементов в массиве N,N≤105. Далее идут N целых чисел, не превосходящих по абсолютной величине 109. Выходные данные Выведите эти числа в порядке неубывания. Примеры Ввод Вывод 2 3 1 1 3

Answer 1

#include <vector>

#include<iostream>

template <typename T>

inline void swap(T& arg1, T& arg2)

{

   T temp = arg1;

   arg1 = arg2;

   arg2 = temp;

};

template <typename T>

inline void merge(std::vector<T>& vArray, std::vector<T>& vTemp, int head, int middle, int tail)

{

   int tmp = 0, lower = head, upper = middle + 1;

 

   while (lower <= middle && upper <= tail)

   {

       if (vArray[lower] < vArray[upper])

       {

           vTemp[tmp++] = vArray[lower++];

       }

       else

       {

           vTemp[tmp++] = vArray[upper++];

       }

   }

 

   if (lower <= middle)

   {

       for (; lower <= middle; vTemp[tmp++] = vArray[lower++]);

   }

   else

   {

       for (; upper <= tail; vTemp[tmp++] = vArray[upper++]);

   }

 

   int arrayPointer = head;

   for (tmp = 0; arrayPointer <= tail; vArray[arrayPointer++] = vTemp[tmp++]);

}

template <typename T>

inline void merge_sort_helper(std::vector<T>& vArray, std::vector<T>& vTemp, int head, int tail)

{

   if (head == tail)

   {

       return;

   }

 

   int middle = (head + tail) / 2;

 

   merge_sort_helper(vArray, vTemp, head, middle);

   merge_sort_helper(vArray, vTemp, middle + 1, tail);

 

   merge(vArray, vTemp, head, middle, tail);

}

 

template <typename T>

void merge_sort(std::vector<T>& vArray)

{

   std::vector<T> v(vArray.size(), 0);

   merge_sort_helper(vArray, v, 0, vArray.size() - 1);

}

int main() {

   int n;

   std::cin >> n;

   std:: vector<int>vArray(n);

   for (int i = 0; i < n; i++) {

       std:: cin >> vArray[i];

   }

   merge_sort(vArray);

   for (int i = 0; i < n; i++) {

       std::cout << vArray[i]<<" ";

   }

}

Answer 2

Конечно, вот пример реализации сортировки слиянием на языке C++:

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> leftArr(n1);
    vector<int> rightArr(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 i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    mergeSort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Просто скопируйте этот код в файл с расширением .cpp и выполните его, вводя данные как в вашем примере. Код реализует сортировку слиянием для введенного массива чисел и выводит отсортированный массив на экран.