原地排序

http://nark.cc/p/?p=171

     作者: csdn-whinah 发表日期: 2013年03月24日

在我以前的这篇文章中：原地排序与链表翻转

解决这个问题是先把链表翻转，然后再循环左移，原理是清楚了，可是稍显繁琐。今天得知该问题的另一个解法：

C++

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]) 展开，即得：

C++

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 所属的那个大环状链表中删除！该算法的本质是：每次碰到一个结点，就将该结点的后继结点从循环链表中删除，删除的同时，被删除的那个结点就归位了。