Самый быстрый алгоритм для сдвига окружности массива N размера для позиции М

Question

Какой самый быстрый алгоритм для массива сдвига окружности для M позиций?
Например, [3 4 5 2 3 1 4] смещение M = 2 позиции должно быть [1 4 3 4 5 2 3].

Большое спасибо.

Answer 1

Теоретически, самым быстрым является такой цикл:

if (begin != middle && middle != end)
{
    for (i = middle; ; )
    {
        swap(arr[begin++], arr[i++]);
        if (begin == middle && i == end) { break; }
        if (begin == middle) { middle = i; }
        else if (i == end) { i = middle; }
    }
}

На практике вы должны профилировать его и посмотреть.

Answer 2

static int [] shift(int arr[], int index, int k, int rem)
{
    if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length)
    {
        return arr;
    }

    int temp = arr[index];

    arr = shift(arr, (index+k) % arr.length, k, rem - 1);

    arr[(index+k) % arr.length] = temp;

    return arr;
}

Answer 3

Посмотрите, если вы заинтересованы в реализации Java:

Программирование жемчужин: круговое переключение влево / вправо