原地排序与链表翻转

http://blog.csdn.net/whinah/article/details/7448477

2012

有这样一个问题：

有个长度为 n 的 (key,val) 数组 a，其中 key 是 int 类型，并且其值在 [0, n) 之间（前闭后开，包括 0 不包括 n），该数组按 key 是乱序的，但没有重复 key。

要求：对 a 原地按 key 排序，可以使用常数个临时变量，不允许使用其它额外空间，时间复杂度必须是O(n)

我曾经写过另外一个问题：排列的分解（必须看），与此有点类似：但其实不同。

本质的不同在于：那个问题是对循环链表逆时针旋转1个单位，而该问题是要对循环链表顺时针旋转1个单位。逆时针旋转很容易，因为是 forward copy。但是顺时针旋转需要 backward copy，对数组（更 general 一点，是 bidirectional iterator）的 backward copy 很容易，但是对单链表的 backward copy，就比较困难了。

为了解决 backward copy 的问题，我们可以把这个循环链表先进行翻转，然后再 forward copy，思路有了，代码如下：

[cpp] view plain copy

1. #include <stdio.h>  
2. #include <algorithm>  
3. #include <vector>  
4.   
5. struct A {  
6.     int key; // must be one kind of integer type  
7.     int val; // should be any type, use int for demo  
8. };  
9.   
10. void reorder(A* a, int n) {  
11.     for (int i = 0; i < n; ++i) {  
12.         if (a[i].key == i) continue;  
13.         int j = i;  
14.         int k = a[i].key;  
15.         do { // reverse the list  
16.             int next = a[k].key;  
17.             a[k].key = j;  
18.             j = k; k = next;  
19.         } while (k != i);  
20.         a[i].key = j;  
21.         int tmp = a[i].val;  
22.         do { // reorder: move to right place  
23.             a[k].key = k;  
24.             a[k].val = a[j].val;  
25.             k = j; j = a[j].key;  
26.         } while (j != i);  
27.         a[k].key = k;  
28.         a[k].val = tmp;  
29.     }  
30. }  
31.   
32. int main() {  
33.     int n = 20;  
34.     std::vector<A> a(n);  
35.     for (int i = 0; i < n; ++i)  
36.         a[i].key = a[i].val = i;  
37.     std::random_shuffle(a.begin(), a.end());  
38.     for (int i = 0; i < n; ++i)  
39.         printf("%d %d\n", a[i].key, a[i].val);  
40.     printf("----------------\n");  
41.     reorder(&a[0], (int)a.size());  
42.     for (int i = 0; i < n; ++i)  
43.         printf("%d %d\n", a[i].key, a[i].val);  
44.     return 0;  
45. }  

• 如果 val 类型的拷贝代价很低（比如象上面demo中的int），可以也可以不用翻转链表，多拷贝两次即可：

[cpp] view plain copy

1. void reorder(A* a, int n) {  
2.     for (int i = 0; i < n; ++i) {  
3.         if (a[i].key == i) continue;  
4.         int j = i;  
5.         int k = a[i].key;  
6.         int t = a[i].val;  
7.         do {  
8.             int t2 = a[k].val;  
9.             a[j].key = j;  
10.             a[k].val = t;  
11.             j = k;  
12.             t = t2;  
13.             k = a[k].key;  
14.         } while (k != i);  
15.         a[j].key = j;  
16.         a[i].val = t;  
17.     }  
18. }  

在最坏情况下，这个版本对 val 的拷贝次数是上个版本的3倍，但是因为避免了翻转链表，也就减少了多一个循环的开销，这样的循环开销也许会造成大量的cpu cache 失效…… 各有利弊