n=10,k=4,d=gcd(10,4)=2 环状循环右移原始数组 0123456789 右移后的:6789012345 i-k i+k d为n和k的最大公约数d=gcd(n,k) 十步后,当前元素下标为:j三(+十k)%n 并且,1=J之味着本轮移位结束。那么 (1)d=1时,当且仅当n水k时ji,得h|t。最小的值 为n,即本轮已遍历到了所有n个元素,移位已完成 。本轮移动了∏d个元素。正好用。最小的值为n/ 2)dφ1时,同样n水k,得(n/d)lt 元素,即可完成整个数组的循环移动·每轮移动n/d个 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 d为n和k的最大公约数 d = gcd(n, k) t 步后，当前元素下标为：j = (i + t*k) ％ n 并且，i＝j意味着本轮移位结束。那么： （1）d=1时，当且仅当 n | tk 时 j=i，得 n|t 。最小的t值 为n，即本轮已遍历到了所有n个元素，移位已完成 （2）d<>1时，同样 n | tk，得(n/d) | t。最小的t值为n/d 。本轮移动了n/d个元素。正好用d轮，每轮移动n/d个 元素，即可完成整个数组的循环移动。 环状循环右移 … i-k … i … i+k n=10, k=4, d=gcd(10, 4)=2 原始数组： 0 1 2 3 4 5 6 7 8 9 右移后的： 6 7 8 9 0 1 2 3 4 5
海豚算法 void Dolphin(int *Array, int n, int k) t nt ij, d; int X; k=k%n:if(k=0) return://边界 d=gcd(nk);,/d为n和k的最大公约数 for ti=1:k=d: i++) X= Array[n-i]∥先保存最尾部的元素 ∥步长为循环,视数组为环状。 for gj=n-i-k j=n-i; j=(n+j-k)%on) Ary(+k)%nAry:/移动 Aray(n-+k)%n]=x;/回x 口箅法共循环了d次,每次完成Md个元素 口例如,n=10,k=4,d=gd(10,4)=2 0123456789 67012345 89 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 海豚算法 void Dolphin(int *Array, int n, int k) { int i,j,d; int X; k = k % n; if (k == 0) return; // 边界 d = gcd(n,k); // d为n和k的最大公约数 for (i=1; i<=d; i++) { X = Array[n-i]; //先保存最尾部的元素 // 步长为k循环，视数组为环状。 for (j=n-i-k; j!=n-i; j=(n+j-k)%n) Array[(j+k)%n] = Array[j]; //移动 Array[(n-i+k)%n] = X; //补回x } } 算法共循环了d次，每次完成n/d个元素 例如， n=10, k=4, d=gcd(10, 4)=2 0 1 2 3 4 5 6 7 8 9 6 7 0 1 2 3 4 5 8 9
口其复杂性为O(n ■每个元素只用了一步便到位 ■每一轮循环多了一个对x的赋值 ■O(n+d)=O(n) 口算法的正确性可以用数论方法证明。此 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 其复杂性为O(n) ◼ 每个元素只用了一步便到位 ◼ 每一轮循环多了一个对x的赋值 ◼ O (n+d)=O(n); 算法的正确性可以用数论方法证明。此 略
巧妙利用数学特性 口利用置逆 先把计j=n1的一对元素〔j对调(置逆),然后 把A[0.k-1左k个元素)序列置逆 ■把AK.n-1右边nk个元素)这子序列置逆 日n=10.k=3,0123456789 多■整体置逆:9876543210 口位置02,3-9分两组置逆 789 10123456 口解为:7890123456 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 巧妙利用数学特性 利用置逆 ◼ 先把i+j = n-1的一对元素(i, j)对调(置逆)，然后： ◼ 把A[0..k-1](左k个元素) 序列置逆 ◼ 把A[k..n-1](右边n-k个元素)这子序列置逆 n=10, k=3，0 1 2 3 4 5 6 7 8 9 ◼ 整体置逆：9 8 7 6 5 4 3 2 1 0 位置0-2，3-9分两组置逆 ◼ 7 8 9 ◼ 0 1 2 3 4 5 6 解为：7 8 9 0 1 2 3 4 5 6
小算法:置逆 口0123456789 9876543210 口对数组元索置逆 for (int i=o: kn/2; i++) swap(Array, i, n-i-1) +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 小算法：置逆 0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 对数组元素置逆 for (int i=0; i<n/2; i++) swap(Array, i, n-i-1);