|
Модератор
9788 / 8352 / 5087
Регистрация: 18.12.2011
Сообщений: 22,328
|
|
13.09.2018, 09:57
|
2
|
 Сообщение было отмечено Sangvuba как решение
Решение
Википедия
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <algorithm>
#include <cstddef>
#include <iterator>
#include <memory>
template<typename T>
void merge_sort(T array[], std::size_t size) noexcept
{
if (size > 1)
{
std::size_t const left_size = size / 2;
std::size_t const right_size = size - left_size;
merge_sort(&array[0], left_size);
merge_sort(&array[left_size], right_size);
std::size_t lidx = 0, ridx = left_size, idx = 0;
std::unique_ptr<T[]> tmp_array(new T[size]);
while (lidx < left_size || ridx < size)
{
if (array[lidx] < array[ridx])
{
tmp_array[idx++] = std::move(array[lidx]);
lidx++;
}
else
{
tmp_array[idx++] = std::move(array[ridx]);
ridx++;
}
if (lidx == left_size)
{
std::copy(std::make_move_iterator(&array[ridx]),
std::make_move_iterator(&array[size]),
&tmp_array[idx]);
break;
}
if (ridx == size)
{
std::copy(std::make_move_iterator(&array[lidx]),
std::make_move_iterator(&array[left_size]),
&tmp_array[idx]);
break;
}
}
std::copy(std::make_move_iterator(tmp_array),
std::make_move_iterator(&tmp_array[size]),
array);
}
} |
|
| C | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| /**
* Сортирует массив, используя рекурсивную сортировку слиянием
* up - указатель на массив, который нужно сортировать
* down - указатель на массив с, как минимум, таким же размером как у 'up', используется как буфер
* left - левая граница массива, передайте 0, чтобы сортировать массив с начала
* right - правая граница массива, передайте длину массива - 1, чтобы сортировать массив до последнего элемента
* возвращает: указатель на отсортированный массив. Из-за особенностей работы данной реализации
* отсортированная версия массива может оказаться либо в 'up', либо в 'down'
**/
int* merge_sort(int *up, int *down, unsigned int left, unsigned int right)
{
if (left == right)
{
down[left] = up[left];
return down;
}
unsigned int middle = (left + right) / 2;
// разделяй и властвуй
int *l_buff = merge_sort(up, down, left, middle);
int *r_buff = merge_sort(up, down, middle + 1, right);
// слияние двух отсортированных половин
int *target = l_buff == up ? down : up;
unsigned int l_cur = left, r_cur = middle + 1;
for (unsigned int i = left; i <= right; i++)
{
if (l_cur <= middle && r_cur <= right)
{
if (l_buff[l_cur] < r_buff[r_cur])
{
target[i] = l_buff[l_cur];
l_cur++;
}
else
{
target[i] = r_buff[r_cur];
r_cur++;
}
}
else if (l_cur <= middle)
{
target[i] = l_buff[l_cur];
l_cur++;
}
else
{
target[i] = r_buff[r_cur];
r_cur++;
}
}
return target;
} |
|
1
|
(
Сообщение было отмечено Sangvuba как решение
