离散数学里面大家都学过群，群里面有种很基本并且很重要的叫做置换群，置换群的元素本质上就是一个排列（英文 permutation group, 直译过来应该是排列群）。大家应该都学过当初要把 (4 1 5 2 3) 分解成 (1 4 2)(3 5)，这个叫做群的 k-cycle 分解，也就是说，一个排列（置换群的一个元素）可以分解成多个 k-cycle。所以，现在问题就是：给定一个[1, n] 构成的排列，求这个排列的 k-cycle 分解，即输出每个 k-cycle，允许使用 O(n) 的额外空间。这实际上是一个循环链表问题：

由此，可以衍生出另一个问题：给定两个包含 n 个元素的平行数组 p, d， p 是下标数组，d 是值（数据）数组，p[i] 是指向 d 的下标，现在 d 已经按 p 有序了，也就是说（现在数组下标是从 0 到 n-1 ）：

对于任意的 i ∈[0, n-1)  ，d[p[i]] ≤ d[p[i+1]]，现在要求，根据 p 将 d 原地整理成有序数组，在这个过程中，允许改变 p，不允许使用额外O(n) 空间。有了前面的 k-cycle 分解，这个问题就相当容易了：

条件判断：

实际上同时还是个优化手段，如果本来就 p[i] == i，就不需要任何移动，一旦移动过后，置 p[i] = i 的作用是打标记。

如果把排列的 k-cycle 看成一个循环链表，内循环实际上是将链表元素循环左移一个单位。内循环使用 do {} while 是因为我们已经知道这个内循环至少执行一次，do {} while 在循环次数较少时比 while {} 要快不少，具体原因请参考相关资料（汇编语言或编译原理或观察编译器生成的汇编码）。

与这相同的算法，可以对排列（置换群的元素）进行原地求逆(需要标记，可以将 int 最高位用来做标记)，求逆如果不要求原地，那么就是简单地让 output[p[i]] = i ，最后返回 output 即可，原地求逆的具体代码我这里就不写了。