k循环右移有序数组的插入排序时间复杂度分析

首先简化问题：循环右移k次等价于右移k % n次（右移n次数组回到初始状态），记k' = k % n，只需分析0≤k'<n的情况。

数组结构分析 #

原有序数组循环右移k'次后，会拆分为两个递增子数组：

• 前k'个元素（记为S1）：原数组末尾k'个元素，满足a_{n-k'+1} < a_{n-k'+2} < ... < a_n
• 后n-k'个元素（记为S2）：原数组前n-k'个元素，满足a_1 < a_2 < ... < a_{n-k'}
  且S2的所有元素都小于S1的所有元素（原数组整体递增）。

插入排序过程拆解 #

插入排序的核心是逐个将元素插入到前面已排序序列中，按子数组分别分析：

1. 处理S1的元素：
   S1本身递增，从第2个元素到第k'个元素，每个元素都比前面已排序元素大，因此每个元素仅需1次比较，无需移动。这部分总操作数为O(k')。

2. 处理S2的元素：
   S2共有m = n - k'个元素，每个元素x ∈ S2的特点是：比S2中已处理的元素大（S2递增），但比S1的所有元素小。
   插入x时，需要将前面已排序序列中的S1部分（共k'个元素）全部后移一位，再插入到合适位置。每个元素的操作数为O(k')，这部分总操作数为O(m*k') = O((n - k')*k')。

时间复杂度总结 #

合并两部分操作数：

• 当k'=0时，数组完全有序，插入排序仅需O(n)操作（每个元素仅1次比较，无移动）。
• 当1≤k'<n时，总操作数为O(k' + (n - k')*k') = O(k'(n - k') + n)。由于当k'(n - k') ≥n时，量级由k'(n - k')主导；当k'(n - k') <n时，量级为O(n)，因此可统一表述为O(k(n - k))（k取模n后的值），或更严谨的O(n + k(n - k))。

典型例子验证：

• 当k=1（或k=n-1）时，k(n-k)=n-1，时间复杂度O(n)：数组仅开头1个大元素，插入排序只需将后面每个元素与该大元素比较1次、移动1次，总操作数O(n)。
• 当k=n/2时，k(n-k)=n²/4，时间复杂度O(n²)：数组拆分为两个等长有序子数组，插入排序需将每个后半部分元素移动n/2次，总操作数接近n²/2，属于O(n²)量级。

内容的提问来源于stack exchange，提问作者Baran