Сортировать массив с предопределенным порядком сортировки - PullRequest
Новая
       8

Сортировать массив с предопределенным порядком сортировки

0 голосов
/ 30 сентября 2019

Мне нужно рекурсивно отсортировать отсортированный по k массив, где массив представляет собой набор отсортированных по «сортировке» значений.

отсортированный по k массив определяется следующим уравнением A [i] <=A [i + k] для каждого i </p>

Примером этого может служить массив {6, 1, 3, 7, 2, 4}
и
k = 3
Thisпотому что A [0] <= A [3], A [1] <= A [4], A [2] <= A [3] <br>, где A [i] <= A [i + k]</p>

Как я могу начать решать эту проблему? Это нужно делать рекурсивно, и я даже не знаю, с чего начать.

1 Ответ

1 голос
/ 30 сентября 2019

Позвольте вызвать ваш массив A, с k = k_original.

Чтобы сделать это рекурсивно, вы можете разбить его на 2 меньших массива с их k = k_original / 2.

Например,: ваш k_original = 5, затем разбейте его на 2 массива с k = 3 и k = 2.

  • Сначала (k = 3), взяв элемент: A [0], A [1], A [2], A [5], A [6], A [7], A [10], A [11], A [12], ... просто возьмите 3 элемента и пропустите следующие 2 (они для другого небольшого массива), следуйте правилу задачи, A [0]

  • Остальная часть элемента переходит во второй массив(в данном случае это k = 2), и они также будут удовлетворять правилу для (k = 2).

Продолжайте ломать их, если после разрушения, (k =1) затем верните массив, и вы можете быть уверены, что он уже отсортирован.

Затем с 2 меньшими уже отсортированными массивами, просто объедините 2 отсортированных массива , чтобы объединить их.

Вот мой псевдокод: 

function sortK (A, k) :
    if (k=1) return A;
    A_first_half = A[0 ~ k/2] + A[k ~ 3k/2] + A [2k ~ 5k/2] + ...
    A_second_half = A[k/2 ~ k] + A[3k/2 ~ 2k] + A[5k/2 ~ 3k] + ...
    sorted_first_half = sortK (A_first_half, k/2);
    sorted_second_half = sortK (A_second_half, k/2);
    return merge(A_first_half, A_second_half);

Примечание: вам нужно позаботиться о случае, когда k не может делиться на 2, но это действительно не так сложно, сделайте это, как мой пример.

...