汉诺塔问题， 用递归方法求集合中的中位数

 1 void Move(int n, int start, int goal, int temp)
 2 {
 3     if (n >= 1)
 4     {
 5         Move(n - 1, start, temp, goal);        //将最上面的n-1个盘子移到temp柱子上
 6         printf("Move disk %d from %d to %d.\n", n, start, goal);    //将第n个柱子移到goal柱子上
 7         Move(n - 1, temp, goal, start);        //将temp柱子上的n - 1个柱子移到goal柱子上
 8     }
 9         
10     
11 }

 1 void Swap(ElementType *X, ElementType *Y)
 2 {
 3     ElementType temp;
 4     temp = *X;
 5     *X = *Y;
 6     *Y = temp;
 7 }
 8 
 9 ElementType FindKthLargest(ElementType s[], int K, int Left, int Right)
10 {    //在s[Left]……s[Right]中找第K大的元素
11     ElementType e = s[Left];        //简单取首元素为基准
12     int L = Left, R = Right;
13     
14     while (1)
15     {
16         while ((Left <= Right) && (e <= s[Left])) Left++;    
17         while ((Left < Right) && (e > s[Right])) Right--;
18         if (Left < Right)
19             Swap(&s[Left], &s[Right]);
20         else
21             break;    //最终brak退出时，Left一定指向第二个集合的第一个元素
22     }
23     Swap(&s[Left - 1], &s[L]);
24     if ((Left - L - 1) >= K)
25         return FindKthLargest(s, K, L, Left - 2);    //Left - 1是基准，所以下一次递归的右边界应该是Left - 2
26     else
27     if ((Left - L - 1) < K - 1)
28         return FindKthLargest(s, K - (Left - L - 1) - 1, Left, R);    //K 先减去第一个集合的Left - L - 1个元素，在减去基准元素，所以下一次递归应该是在第二个集合中求第K - (Left - L - 1) - 1个元素
29     else
30         return e;        //找到，返回
31 }
32 
33 //封装前面这个查找函数
34 ElementType Median(ElementType s[], int N)
35 {
36     return FindKthLargest(s, (N + 1) / 2, 0, N - 1);
37 }