C 語言陣列循環右移優化：取模減少實際移動次數

原始 O(m×n) 算法

for (i = 1; i <= m; i++) {
    last = a[n-1];
    for (j = n-1; j > 0; j--) a[j] = a[j-1];
    a[0] = last;
}

優化觀察：週期性

陣列長度 len，右移 m 位等價於右移 m % len 位。
更進一步：m % len == 0 → 無變化；m % len == len/2 (若 len 偶數) → 逆序等價。

O(n) 三步逆序法 (標準最優)

void rotateRight(int a[], int n, int k) {
    k %= n;
    if (k < 0) k += n;
    if (k == 0) return;
    reverse(a, 0, n-1);       // 整體逆序
    reverse(a, 0, k-1);       // 前 k 個逆序
    reverse(a, k, n-1);       // 後 n-k 個逆序
}

void reverse(int a[], int l, int r) {
    while (l < r) { int t = a[l]; a[l] = a[r]; a[r] = t; l++; r--; }
}

複雜度

• 時間 O(n)，空間 O(1)。
• 無視 m 大小，僅遍歷陣列 3 次。

範例驗證

int a[] = {1,2,3,4,5}; // len=5
rotateRight(a, 5, 1); // → {5,1,2,3,4}
rotateRight(a, 5, 6); // 6%5=1 → 同上
rotateRight(a, 5, 2); // → {4,5,1,2,3}

進階：區塊交換法 (Juggling Algorithm)

同樣 O(n)、O(1)，利用 GCD 分組交換，適合無法隨機存取的結構 (如單向鏈表)。