原地排序-更简洁的算法
在我以前的这篇文章中：原地排序与链表翻转
解决这个问题是先把链表翻转，然后再循环左移，原理是清楚了，可是稍显繁琐。今天得知该问题的另一个解法：
|
1 2 3 4 5 6 |
void rearrange(KeyVal* a, int n) { for (int i = 0; i < n; ++i) { int j; while ((j=a[i].key) != i) swap(a[i], a[j]); } } |
算法的证明:
将 swap(a[i], a[j]) 展开，即得：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int j = a[i].key; // swap(a[i], a[j]); // 相当于： int tmpk = a[i].key; Val tmpv = a[i].val; a[i].key = a[j].key; a[i].val = a[j].val; a[j].key = tmpk; a[j].val = tmpv; // 而 前面 j = a[i].key, 于是简化为： Val tmpv = a[i].val; a[i].key = a[j].key; // 从 k-cycle 中删除 j a[i].val = a[j].val; a[j].key = j; // 这个才是重点，a[j] 归位了！ a[j].val = tmpv; |
在原地排序与链表翻转中提到的定理：一个全排列中，包含多个循环链表。a[i].key 可以理解为是 a[i].next，于是 a[i].key = a[j].key 就是链表操作中的： p->next = p->next->next，这是一个删除链表结点的操作！swap(a[i], a[j]) 实际上是将 a[j] 从 j 所属的那个大环状链表中删除！该算法的本质是：每次碰到一个结点，就将该结点的后继结点从循环链表中删除，删除的同时，被删除的那个结点就归位了。
