http:///p/?p=171 作者: csdn-whinah
发表日期: 2013年03月24日 在我以前的这篇文章中:原地排序与链表翻转 解决这个问题是先把链表翻转,然后再循环左移,原理是清楚了,可是稍显繁琐。今天得知该问题的另一个解法: C++ 算法的证明: 将 swap(a[i], a[j]) 展开,即得: C++ 在原地排序与链表翻转中提到的定理:一个全排列中,包含多个循环链表。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 所属的那个大环状链表中删除!该算法的本质是:每次碰到一个结点,就将该结点的后继结点从循环链表中删除,删除的同时,被删除的那个结点就归位了。 |
|